Optimisation en informatique
RCP104
Chapitre .. : Programmation
Linéaire en Nombres Entiers
Sourour Elloumi
Définition PLNE
(cid:124) Programmation linéaire où certaines
variables ne peuvent prendre que des
valeurs entières
Programmation pure (resp. mixte) en NE : la totalité
(resp. un sous-ensemble) des variables sont entières
Programmation 0-1 ou binaire : les variables entières ne
peuvent être que 0 ou 1
2
Exemple 1
max
x
1
+
64.0
x
2
s.c.
:
50
+
x
31
≤
250
2
4
−≥
x
1
−
3
x
1
xx
,
1
2
x
2
0
≥
2
et
entiers
3
Exemple 1-suite
point optimal continu (1.95, 4.92)
objectif 5.0628
point optimal entier (5, 0)
objectif 5
4
(cid:124) PL et PLNE sont TRES différentes
(cid:124) Optimisation continue convexe /
Optimisation discrète
Suite de ce cours :
(cid:124) Utilité de la PLNE
(cid:124) Résolution des PLNE
5
Application 1 : choix
d’usines et d’entrepôts
(cid:124) But : choisir de nouveaux emplacements pour
construire des usines et des entrepôts
(cid:124) Deux emplacements : Lyon et Toulouse
(cid:124) On ne peut construire plus d’un entrepôt
(cid:124) On ne peut construire un entrepôt que dans une
ville où l’on a aussi une usine
(cid:124) On connaît, pour chaque ville :
(cid:122) Coefficient de rentabilité usine ou entrepôt
(cid:122) Coût de construction usine ou entrepôt
(cid:124) Le coût total de construction ne peut pas dépasser
10
(cid:124) Objectif : maximiser la rentabilité
6
Application 1 : données
Rentabilité Coût
Usine à L
Usine à T
Entrepôt à L
Entrepôt à T
9
5
6
4
6
3
5
2
7
Application 1 : modèle
(cid:124) Variables (de décision):
x1=1 si une usine est construite à Lyon et 0 sinon
x2=1 si une usine est construite à Toulouse et 0 sinon
y1=1 si un entrepôt est construit à Lyon et 0 sinon
y2=1 si un entrepôt est construit à Toulouse et 0 sinon
8
Application 1 : modèle
(cid:124) Contraintes
1- On ne peut construire plus d’un entrepôt
y1 +y2≤1
2- On ne peut construire un entrepôt que dans une
ville où l’on a aussi une usine
y1 ≤ x1
y2 ≤ x2
9
Application 1 : modèle
3- Le coût total de construction ne peut pas
dépasser 10
6x1 +3x2 +5y1 +2y2≤10
(cid:124) Objectif :
max 9x1 +5x2 +6y1 +4y2
10
Application 1 : résumé du
modèle et mise sous forme
standard
min
Z
−=
9
x
1
−
5
x
2
−
6
y
1
−
4
y
2
C’est notre
exemple de
base
s.c.
:
y
1
y
1
y
≤
1
+
≤
≤
y
2
x
1
x
2
x
3
2
+
xx
,
1
2
,
2
x
1
≤
6
0
+
2
y
2
≤
10
+
5
y
1
yy
,
1
2
≤
1
et
entiers
11
Exemple de base: résolution
par Mosel et xpress-mp
model ExempleBase
uses "mmxprs" ! utilise le solveur Xpress-Optimizer
declarations
x1, x2, y1, y2 : mpvar ! variables
end-declarations
! le modèle
Z:= (-9)x1 -5x2 -6y1 -4y2 !fonction objectif
! les contraintes
y1 +y2<=1
y1 <= x1
y2 <= x2
6x1 +3x2 +5y1 +2y2 <= 10
x1 is_binary
x2 is_binary
y1 is_binary
y2 is_binary
! résolution du problème
minimize (Z)
writeln("Solution: ", getobjval) ! affichage de la valeur de 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
12
Exemple de base: résolution
par Mosel et xpress-mp
Solution: -14
valeur de x1 : 1
valeur de x2 : 1
valeur de y1 : 0
valeur de y2 : 0
13
Résolution des PLNE
(cid:124) Nous allons voir comment résoudre
les PLNE
1. Dans le cas particulier des
problèmes purement binaires PL01
2. Dans le cas général des PLNE
14
Résolution des PL01-
Exemple de base
min
Z
Publicité
9
−=
x
1
−
5
x
−
6
y
1
2
−
4
y
2
s.c.
:
≤
1
y
2
x
1
x
+
≤
y
1
y
1
y
2
x
1
≤
6
0
≤
+
2
x
3
2
xx
,
1
2
,
+
5
y
1
yy
,
1
2
+
2
y
2
≤
10
≤
1
et
entiers
15
1ere idée :
énumération
Résolution des PL01-
Enumération
(cid:124) Idée : il existe un nombre fini de
solutions. Enumérons-les !
0
1
1
0
1
0
1
0
1
0
1
0
1
0
0
Z=0
1
!
0
!
1
0
1
!
Z=-5
Z=-9
0
!
1
!
0
1
Z=-9 !
0
!
1
0
1
0
1
!
Z=-14
!
!
!
x1
x2
y1
y2
17
Résolution des PL01-
Enumération
(cid:124) Pour n variables binaires, 2n cas
possibles
(cid:124) Pour n=20, plus d’un million
(cid:124) Pour n=30, plus d’un milliard …
(cid:124) Idée d’énumération de tous les cas
possibles impraticable en
Optimisation Discrète en général
18
2ème idée :
encadrement de la
valeur optimale
Relaxation continue-
exemple de base
(cid:124) Relaxation continue = on « oublie » le
caractère entier des variables
(cid:124) On obtient un programme linéaire
(continu) qu’on sait résoudre, par
exemple par la méthode du simplexe :
(cid:122)Solution (x1, x2, y1, y2)=(5/6, 1, 0, 1)
(cid:122)Valeur optimale : Z=-33/2=-16.5
20
Relaxation continue:
interprétation
+∞
-∞
-16,5
Valeurs possibles de toutes les solutions
admissibles, entières ou non
21
Relaxation continue:
interprétation
Conclusion :
Propriété générale :
la valeur optimale (en entier) ≥ -16.5
• Pour un problème de maximisation, la valeur optimale en entier ≤ la valeur
optimale en continu
• Pour un problème de minimisation, la valeur optimale en entier ≥ la valeur
optimale en continu
On dit que la valeur optimale de la relaxation continue est
• une borne supérieure (si objectif de maximisation) ou
• une borne inférieure (si objectif de minimisation)
de la valeur optimale en entier
22
Exemple 1-rappel (max)
point optimal continu (1.95, 4.92)
objectif 5.0628
point optimal entier (5, 0)
objectif 5
23
Connaissance d’une solution
admissible
(cid:124) Question : quelle information a-t-
on si l’on dispose d’une solution
admissible ?
24
Connaissance d’une solution
admissible- exemple de base
(cid:124) Admettons que l’on connaisse la solution
(x1, x2, y1, y2)=(1, 0, 0, 0) de valeur Z=-9
25
Connaissance d’une solution
admissible- exemple de base
-9
-16,5
+∞
-∞
Valeurs possibles de
toutes les solutions
entières optimales
Valeurs possibles de toutes les solutions
admissibles, entières ou non
26
Connaissance d’une solution
admissible- exemple de base
Conclusion : la valeur d’une solution optimale est comprise entre
-16.5 et -9
Propriété générale :
• Pour un problème de minimisation,
val. optimale en continu ≤ val. optimale en entier ≤ val. d’une solution admissible
borne inférieure
borne supérieure
• Pour un problème de maximisation,
val. d’une solution admissible ≤ val. optimale en entier ≤ val. optimale en continu
27
Algorithme Branch-and-Bound
pour résoudre un PLNE
(cid:124) Ingrédients de base :
(cid:122)encadrement de la valeur optimale
(borne inférieure, borne supérieure)
(cid:122) énumération limitée dans le but
d’obtenir un encadrement de plus en
plus fin
28
B&B- Exemple de base
(cid:124) Dans la solution de la
relaxation continue : (x1, x2, y1,
y2)=(5/6, 1, 0, 1), x1 n’est pas
entier. On va « brancher »
selon les deux valeurs
possibles de x1 : 0 et 1
29
B&B- Exemple de base
Solution
courante : -9
S : toutes les
solutions entières
opt≥-16.5
x1=0
S1 : toutes les
solutions entières
telles que x1=0
x1=1
S2 : toutes les
Publicité
solutions entières
telles que x1=1
30
B&B- Exemple de base
Sous-ensemble S1 : x1=0
min
Z
−=
5
x
2
−
6
y
1
−
4
y
2
s.c.
:
≤
1
+
≤
y
2
0
y
1
y
1
y
2
x
2
≤
3
0
≤
x
2
y
5
1
yy
,
1
+
,
+
x
2
2
2
≤
y
2
1
≤
10
et
entiers
Solution de la relaxation continue : (x2, y1, y2)=(1, 0, 1) et Z=-9,
et c’est une solution entière !
31
B&B- Exemple de base
S : toutes les
solutions entières
opt≥-16.5
Solution
courante : -9
x1=1
S2 : toutes les
solutions entières
telles que x1=1
x1=0
S1 : toutes les
solutions entières
telles que x1=0
opt= -9
32
B&B- Exemple de base
Sous-ensemble S2 : x1=1
min
Z
−−=
59
x
2
−
6
y
1
−
4
y
2
s.c.
:
+
y
2
≤
1
≤
1
y
1
y
1
y
2
x
2
≤
3
0
≤
x
2
y
5
1
yy
,
1
+
,
+
x
2
2
2
≤
y
2
1
≤
4
et
entiers
Solution de la relaxation continue : (x2, y1, y2)=(4/5, 0, 4/5) et Z=-16.2
33
B&B- Exemple de base
Solution
courante : -9
x1=0
S1 : toutes les
solutions entières
telles que x1=0
Opt= -9
S : toutes les
solutions entières
opt≥ -16.5
x1=1
S2 : toutes les
solutions entières
telles que x1=1
opt≥ -16.2
34
B&B- Exemple de base
(cid:124) Conclusion actuelle :
(cid:122)Meilleure solution admissible connue
(solution courante) de valeur -9
(cid:122)Meilleure borne inférieure connue : -16.2
(cid:122)La valeur optimale est donc comprise entre
-9 et -16.2
(cid:124) Comment continuer ?
35
B&B- Exemple de base
Le noeud S1 peut être élagué
car on connaît la valeur d’une
solution entière optimale dans
cet ensemble (valeur solution
courante ≥ relaxation continue)
S1 : toutes les
solutions entières
telles que x1=0
Opt= -9
36
B&B- Exemple de base
Pour le noeud S2, on applique le
même traitement que pour S
S2 : toutes les
solutions entières
telles que x1=1
opt≥ -16.2
Solution de la relaxation continue : (x1,x2, y1, y2)=
(1,4/5, 0, 4/5) et Z=-16.2. On va brancher sur x2
37
B&B- Exemple de base
(cid:124) Sous-ensemble S3 : x1=1 et x2=0
Solution de la relaxation continue :
(x1,x2, y1, y2)= (1,0,4/5,0) et Z=-13.8
(cid:124) Sous-ensemble S4 : x1=1 et x2=1
Solution de la relaxation continue :
(x1,x2, y1, y2)= (1,1,0,0.5) et Z=-16
38
B&B- Exemple de base
S
opt≥ -16.5
Solution
courante : -9
x1=0
S1
Opt= -9
x1=1
S2
opt ≥ -16.2
x2=0
S3
opt ≥ -13.8
x2=1
S4
opt ≥ -16
39
B&B- Exemple de base
(cid:124) Conclusion actuelle :
(cid:122)Valeur meilleure solution connue : -9
(cid:122)Meilleure borne inférieure connue :-16
(cid:124) On ne peut élaguer ni S3 ni S4
(cid:124) On « repart » avec S4 qui a la plus petite
borne inférieure. On branche sur y1
40
B&B- Exemple de base
(cid:124) Sous-ensemble S5 : x1=1, x2=1 et y1=0
Solution de la relaxation continue :
(x1,x2, y1, y2)= (1,1,0,0.5) et Z=-16
(cid:124) Sous-ensemble S6 : x1=1, x2=1 et y1=1
impossible. S6 peut donc être élagué
41
B&B- Exemple de base
x1=0
S1
Opt= -9
S
opt ≥ - 16.5
x1=1
Publicité
Solution
courante : -9
S2
opt ≥ - 16.2
x2=0
x2=1
S3
opt ≥ - 13.8
S4
opt ≥ - 16
y1=0
y1=1
S5
opt ≥ -16
S6
impossible
42
B&B- Exemple de base
(cid:124) Conclusion actuelle :
(cid:122)Valeur meilleure solution connue : -9
(cid:122)Meilleure borne inférieure connue : -16
(cid:124) On peut repartir soit avec S3 soit avec
S5, on repart avec S5, on branche sur y2
43
B&B- Exemple de base
(cid:124) Sous-ensemble S7 : x1=1, x2=1, y1=0 et
y2=0 Solution unique entière et Z=-14 (<-9
donc Nouvelle solution courante)
(cid:124) Sous-ensemble S8 : x1=1, x2=1, y1=0 et
y2=1 impossible. S8 peut donc être élagué
44
B&B- Exemple de base
x1=0
S1
Opt= -9
S
opt≥ -16.5
x1=1
Solution
courante : -14
S2
opt ≥ -16.2
x2=0
x2=1
Peut être élagué car
borne inférieure > à
val. sol courante
S3
opt ≥ -13.8
S4
opt ≥ -16
y1=0
y1=1
S5
opt ≥ -16
y2=0
y2=1
Peut être élagué car
sol optimale connue
S7
Opt= -14
S8
impossible
S6
impossible
45
B&B- Exemple de base
(cid:124) Conclusion : on peut s’arrêter car tous
les noeuds ont été élagués. On prouve
ainsi que la solution de valeur -14 est
optimale !
46
B&B- Exemple de base, gain
par rapport à l’énumération
complète
0
1
1
0
1
0
1
0
1
0
1
0
1
0
0
Z=0
1
!
0
!
1
0
1
!
Z=-5Z=-9
0
!
1
!
0
1
Z=-9 !
0
!
1
0
1
0
1
!
Z=-14
!
!
!
x1
x2
y1
y2
47
Algorithme B&B (min)-
Résumé
(cid:124) Initialisation
(cid:122) Calculer une solution admissible de
valeur Z ou poser Z=+∞
(cid:122) Résoudre la relaxation continue et mettre
à jour éventuellement Z*
(cid:122) Appliquer les tests d’élagage
(cid:124) Tant qu’il reste des noeuds non élagués
(cid:122) Choisir un noeud non élagué
(cid:122) Brancher sur une des variables
(cid:122) Pour chacun des 2 nouveaux noeuds,
résoudre la relaxation continue et mettre
à jour éventuellement Z*
(cid:122) Appliquer les tests d’élagage
(cid:124) Fin tant que
(cid:124) La solution courante Z* est optimale
48
Algorithme B&B (min)-
Résumé- suite
(cid:124) Un noeud est élagué si:
(cid:122) La relaxation continue n’a pas de solution
(cid:122) La valeur optimale de la relaxation continue ≥ Z*
(cid:124) La mise en place de l’algorithme nécessite de
préciser :
(cid:122) La règle de sélection : quel noeud non élagué
choisir ?
(cid:122) La règle de branchement : sur quelle variable
brancher ?
49
Algorithme B&B (min)-
Résumé- suite
(cid:124) Dans le cas général des variables entières
(non seulement 0-1), on choisit une variable
de valeur fractionnaire dans la solution
optimale de la relaxation continue et on
branche sur l’arrondi supérieur et inférieur de
cette valeur
Exemple : x5=132.48
x5≤132
x5≥133
50
Problème des solutions
admissibles
(cid:124) Ce n’est pas toujours facile (pb général NP-
complet)
(cid:124) Il n’existe pas de méthode générale rapide
(cid:124) On peut se contenter de celles qu’on trouve
lors de la résolution des relaxations
continues
(cid:124) Il existe des algorithmes qui fonctionnent
bien dans des cas particuliers, par exemple
l’arrondi
51
Problème d’efficacité
(cid:124) C’est le nombre de nœuds explorés qui
déterminera le temps de calcul. A chaque
nœud, on résout un programme linéaire
(continu)
(cid:124) On ne peut pas prévoir à l’avance le nombre
maximal de nœuds qu’il faudra explorer
52
Problème d’efficacité
(cid:124) En règle générale, un programme
linéaire continu se résout « vite »
(cid:124) Un PLNE nécessite du temps …
53
Efficacité- Exemple
n
∑
xc
j
j
1
=
j
min
Z
=
s.c.
:
n
∑
xa
j
1
j
1
=
≤
b
1
j
≤
b
2
j
n
∑
xa
j
2
j
1
=
x
j
variables
binaires
• Problème avec n=1000 variables données engendrées
aléatoirement
• Relaxation continue : 0.03 secondes
• Résolution en entier : 43 secondes (251402 nœuds)
54