Optimisation en informatique

Ce document traite de l'optimisation en informatique, plus précisément de la programmation linéaire en nombres entiers (PLNE). Il s'adresse aux étudiants et chercheurs en optimisation et informatique, souhaitant comprendre les principes, modèles et méthodes de résolution des problèmes d'optimisation combinatoire avec contraintes d'intégralité.

Programmation Linéaire en Nombres Entiers (PLNE)

La programmation linéaire en nombres entiers est une forme de programmation linéaire dans laquelle certaines variables doivent prendre des valeurs entières. On distingue :

• La programmation pure en nombres entiers : toutes les variables sont entières.
• La programmation mixte en nombres entiers : un sous-ensemble des variables est entier.
• La programmation 0-1 ou binaire : les variables entières ne peuvent prendre que les valeurs 0 ou 1.

Exemple simple de PLNE

Maximiser :

  x1 + 64.0 x2

Sous contraintes :

  50 + x31 ≤ 250
  2 4 − ≥ x1 − 3
  x1, x2 ≥ 0 et entiers

Le point optimal continu est (1.95, 4.92) avec un objectif de 5.0628, tandis que le point optimal entier est (5, 0) avec un objectif de 5.

Différences entre PL et PLNE

La programmation linéaire (PL) et la programmation linéaire en nombres entiers (PLNE) sont très différentes :

• La PL est une optimisation continue convexe.
• La PLNE est une optimisation discrète.

Ce cours abordera l'utilité de la PLNE et les méthodes de résolution des PLNE.

Application : Choix d’usines et d’entrepôts

Objectif : choisir les emplacements pour construire des usines et entrepôts dans deux villes, Lyon et Toulouse.

• On ne peut construire plus d’un entrepôt.
• Un entrepôt ne peut être construit que dans une ville où une usine est aussi construite.
• Les coefficients de rentabilité et coûts de construction sont connus pour chaque ville et type d'installation.
• Le coût total de construction ne doit pas dépasser 10.
• On cherche à maximiser la rentabilité.

Données

	Rentabilité	Coût
Usine à Lyon	9	6
Usine à Toulouse	5	3
Entrepôt à Lyon	6	5
Entrepôt à Toulouse	4	2

Modèle mathématique

Variables de décision :

• x1 = 1 si une usine est construite à Lyon, 0 sinon
• x2 = 1 si une usine est construite à Toulouse, 0 sinon
• y1 = 1 si un entrepôt est construit à Lyon, 0 sinon
• y2 = 1 si un entrepôt est construit à Toulouse, 0 sinon

Contraintes :

• On ne peut construire plus d’un entrepôt : y1 + y2 ≤ 1
• Un entrepôt ne peut être construit que si une usine est présente : y1 ≤ x1, y2 ≤ x2
• Coût total ≤ 10 : 6x1 + 3x2 + 5y1 + 2y2 ≤ 10

Objectif :

max 9x1 + 5x2 + 6y1 + 4y2

Mise sous forme standard

min Z = -9x1 - 5x2 - 6y1 - 4y2
s.c.
  y1 + y2 ≤ 1
  y1 ≤ x1
  y2 ≤ x2
  6x1 + 3x2 + 5y1 + 2y2 ≤ 10
  x1, x2, y1, y2 ∈ {0,1}

Exemple de résolution avec Mosel et Xpress-MP

model ExempleBase

uses "mmxprs"                ! utilise le solveur Xpress-Optimizer
declarations
  x1, x2, y1, y2 : mpvar              ! variables
end-declarations

! fonction objectif
Z:=  (-9)*x1 -5*x2 -6*y1 -4*y2        

! contraintes
y1 + y2 <= 1
y1 <= x1
y2 <= x2
6*x1 + 3*x2 + 5*y1 + 2*y2 <= 10

! variables binaires
x1 is_binary
x2 is_binary
y1 is_binary
y2 is_binary

! résolution
minimize (Z)

writeln("Solution: ", getobjval) ! affichage valeur Z
writeln("valeur de x1 : ", getsol(x1))
writeln("valeur de x2 : ", getsol(x2))
writeln("valeur de y1 : ", getsol(y1))
writeln("valeur de y2 : ", getsol(y2))

end-model

Solution obtenue :

• Valeur optimale Z = -14
• x1 = 1, x2 = 1, y1 = 0, y2 = 0

Résolution des PLNE

On distingue deux cas :

• Problèmes purement binaires (PL01)
• Cas général des PLNE

1ère idée : Énumération

Pour n variables binaires, il existe 2^n solutions possibles. Par exemple :

• Pour n=20, plus d’un million de cas
• Pour n=30, plus d’un milliard de cas

L'énumération complète est donc impraticable en optimisation discrète.

2ème idée : Relaxation continue

On « oublie » la contrainte d’intégralité et on résout le problème en variables continues. Cela donne un programme linéaire classique, résoluble par exemple par la méthode du simplexe.

Exemple sur le modèle de base :

• Solution relaxation continue : (x1, x2, y1, y2) = (5/6, 1, 0, 1)
• Valeur optimale relaxation : Z = -16.5

Interprétation :

• Pour un problème de minimisation, la valeur optimale en entier est toujours supérieure ou égale à la valeur optimale en continu.
• La valeur optimale de la relaxation continue est donc une borne inférieure de la valeur optimale entière.

Connaissance d’une solution admissible

Si l’on connaît une solution admissible (entière) de valeur Z', alors la valeur optimale entière est comprise entre la valeur optimale de la relaxation continue et Z'.

Exemple :

• Solution admissible : (1, 0, 0, 0) avec Z = -9
• Valeur optimale relaxation continue : -16.5
• Donc valeur optimale entière ∈ [-16.5, -9]

Algorithme Branch-and-Bound (B&B)

Le B&B est une méthode efficace pour résoudre les PLNE. Elle combine :

• Un encadrement de la valeur optimale (bornes inférieure et supérieure)
• Une énumération limitée visant à affiner cet encadrement

Principe du B&B sur l'exemple de base

La solution de la relaxation continue n’est pas entière (x1=5/6). On « branche » sur x1 en deux cas :

• x1 = 0
• x1 = 1

Chaque cas définit un sous-ensemble de solutions entières à explorer.

Exploration des sous-ensembles

• S1 (x1=0) : relaxation continue donne solution entière (x2=1, y1=0, y2=1) avec Z=-9.
• S2 (x1=1) : relaxation continue donne solution fractionnaire (x2=4/5, y1=0, y2=4/5) avec Z=-16.2.

On peut élaguer S1 car la solution entière est connue et meilleure que la borne inférieure. Pour S2, on continue à brancher, par exemple sur x2 :

• S3 (x1=1, x2=0) : relaxation continue Z=-13.8
• S4 (x1=1, x2=1) : relaxation continue Z=-16

On poursuit avec S4, en branchant sur y1 :

• S5 (x1=1, x2=1, y1=0) : relaxation continue Z=-16
• S6 (x1=1, x2=1, y1=1) : solution impossible, élaguée

Ensuite, on branche sur y2 dans S5 :

• S7 (x1=1, x2=1, y1=0, y2=0) : solution entière unique Z=-14 (meilleure solution courante)
• S8 (x1=1, x2=1, y1=0, y2=1) : impossible, élaguée

Les autres noeuds sont élagués car leurs bornes inférieures sont supérieures à la meilleure solution courante.

Conclusion sur l'exemple

La solution optimale est trouvée avec Z = -14, après avoir exploré un nombre limité de noeuds, bien inférieur à l'énumération complète.

Résumé de l’algorithme Branch-and-Bound (minimisation)

1. Initialiser une solution admissible Z* ou poser Z* = +∞.
2. Résoudre la relaxation continue, mettre à jour Z* si meilleure solution.
3. Appliquer les tests d’élagage :
• Élaguer un noeud si la relaxation continue n’a pas de solution.
• Élaguer un noeud si la valeur optimale de la relaxation continue ≥ Z*.
4. Tant qu’il reste des noeuds non élagués :
• Choisir un noeud non élagué.
• Brancher sur une variable fractionnaire.
• Résoudre la relaxation continue pour chaque branche, mettre à jour Z*.
• Appliquer les tests d’élagage.
5. Fin : la solution courante Z* est optimale.

Cas général des variables entières

Pour des variables entières non binaires, on choisit une variable fractionnaire x5 = 132.48 par exemple, et on crée deux branches :

• x5 ≤ 132
• x5 ≥ 133

Problèmes et efficacité

Le principal défi est la recherche de solutions admissibles, ce qui est un problème NP-complet en général. Il n’existe pas de méthode rapide générale. Souvent, on se contente des solutions trouvées lors de la résolution des relaxations continues. Des heuristiques comme l’arrondi peuvent être utilisées dans certains cas.

Le temps de calcul dépend du nombre de noeuds explorés, chaque noeud nécessitant la résolution d’un programme linéaire continu.

En général, la résolution d’un programme linéaire continu est rapide, mais la résolution d’un PLNE peut être longue.

Exemple d'efficacité

Problème avec n=1000 variables binaires générées aléatoirement :

• Relaxation continue résolue en 0.03 secondes
• Résolution entière en 43 secondes, explorant 251 402 noeuds

Glossaire des termes clés

• Programmation linéaire en nombres entiers (PLNE) : optimisation linéaire avec contraintes d’intégralité sur certaines variables.
• Programmation 0-1 (binaire) : PLNE où les variables entières ne prennent que les valeurs 0 ou 1.
• Relaxation continue : version du problème où la contrainte d’intégralité est ignorée, permettant aux variables d’être continues.
• Borne inférieure : pour un problème de minimisation, la valeur optimale de la relaxation continue qui est inférieure ou égale à la valeur optimale entière.
• Borne supérieure : pour un problème de maximisation, la valeur optimale de la relaxation continue qui est supérieure ou égale à la valeur optimale entière.
• Solution admissible : solution respectant toutes les contraintes, notamment d’intégralité.
• Branch-and-Bound (B&B) : algorithme combinant énumération partielle et bornes pour résoudre efficacement les PLNE.
• Élagage : élimination de sous-ensembles de solutions ne pouvant pas contenir la solution optimale.
• NP-complet : classe de problèmes pour lesquels il n’existe pas de méthode connue efficace en temps polynomial.

Points clés à retenir

• La PLNE impose des contraintes d’intégralité sur certaines variables, rendant le problème beaucoup plus complexe que la PL classique.
• La relaxation continue fournit une borne utile pour encadrer la valeur optimale entière.
• L’énumération complète des solutions binaires est impraticable pour un grand nombre de variables.
• L’algorithme Branch-and-Bound permet de résoudre les PLNE en explorant un nombre limité de solutions grâce à des bornes et à l’élagage.
• La recherche de solutions admissibles est un défi majeur, souvent abordé via des heuristiques ou solutions issues des relaxations.
• Le temps de calcul dépend fortement du nombre de noeuds explorés, chaque noeud nécessitant la résolution d’un programme linéaire continu.