View
2
Download
0
Category
Preview:
Citation preview
Recherche OpérationnelleDeuxième Partie
Paul Feautrier
Paul.Feautrier@ens-lyon.fr.
ENS Lyon
RO-MIM2 – 1/63
Plan
Introduction et principaux concepts
Optimisation continue sans contrainte
Programmation linéaire
Optimisation continue sous contrainte
Optimisation combinatoire
Programmation linéaire en nombres entiers.
Exploration
Métaheuristiques
Programmation dynamique
Eléments de Complexité
RO-MIM2 – 2/63
Optimisation sous contraintes
courbes de niveau dela fonction objectif
optimum
contraintes
Résoudre :
� ��� � ��� �(1) �� ��� � � � � �� � � �(2) � � �� �(3)
L’ensemble des points faisables est
� � ��� � � �� ��� � � � � � � � � � �
. Les fonctions �
sont les contraintes.
La programmation linéaire est le cas particulieroù
�et les � � sont linéaires. On obtient des pro-
blèmes plus ou moins difficiles suivant que l’unou l’autre ou les deux de ces éléments sont nonlinéaires (resp. non convexes).
RO-MIM2 – 3/63
Généralisation
Certaines contraintes peuvent être difficiles à mettre sous laforme �� ��� !"
.
Exemple : on veut que � soit entier (i.e. à coordonnées entières).
On remplace la dernière contrainte par :
� # $ %& ' (*)
RO-MIM2 – 4/63
Organisation de l’exposé
Conditions nécessaires de Kuhn-Tucker
Méthodes directes ; linéarisation.Méthode des plans sécants.
Fonction de Lagrange, point-col.
Méthodes dualesMéthodes de pénalité
Méthodes lagrangiennes
RO-MIM2 – 5/63
Caractérisation de l’optimum, I
On suppose les fonctions
+
et �� continues et à dérivéescontinues.
L’optimum � ,
peut être à l’intérieur de
-. Dans ce cas. + �� , /" .
L’optimum peut être sur les frontières de-
. Dans ce cas�� �� , /" pour un certain nombres de contraintes (lescontraintes saturées) et
. + �� , n’est pas nécessairement nul.
On note
0 % 1243 ) ) )3 5 6l’ensemble des indices des contraintes
saturées.
En particulier, si les contraintes sont toutes des contraintesd’égalité, l’intérieur de
-est vide et l’on est toujours dans le
dernier cas (dit de Lagrange).
RO-MIM2 – 6/63
Caractérisation de l’optimum, II
En programmation linéaire,
+ ��� / 7) � ,
. + / 7 n’est jamais nul(ou bien le problème est trivial), donc l’optimum est sur lafrontière de
-
.
Une direction
8
est admissible en un point � , # -si il existe9 : "
tel que
; < 9 = � ,> ; 8 # -.� ,
est un minimum si, pour toute direction admissible
8
,; < 9 = + ��� ,> ; 8 ? + �� , )
La condition d’admissibilité peut s’écrire :
�� �� ,> ; 8 / �� �� , > ; 8) . �� �� , !" 3 @ # 03
soit encore8) . �� �� , !" 3 @ # 0
.
RO-MIM2 – 7/63
Caractérisation de l’optimum, III
Les directions admissibles en � ,
appartiennent au coneA / 1 8 B 8) . �� ��� , !" 3 @ # 0 63avec
0 / 1 @ B �C� �� , /" 6
.
La réciproque est fausse, sauf dans quelques cas particuliers :
Les fonctions �� sont linéaires ou convexes ;
Les gradients sont linéairements indépendants.
Si
A
est l’ensemble des directions admissibles, alors unecondition nécessaire d’optimalité est :8 # A = + ��� ,> ; 8 ED + �� , ? " 3
8 # A = 8) . + ��� , ? " )
RO-MIM2 – 8/63
Conditions de Kuhn et Tucker
D’après le lemme de Farkas, il existe donc des
F � GHJI KL Mtels que :NOQP R OTS �U V F �S WYX � Z\[ ] ^ OTS W _ Z\[ ` ]I(4)
W _ Z\[ ` ] R �U V F � WYX � Z\[ ] ^ H S(5)
On peut étendre la sommation à toutes les valeurs de
Kà condition de poserF � ^H pour les contraintes non saturées. Une condition nécessaire pour que [ `
soit un minimum est donc :aF � GH I K ^ bI S S S I c(6) W _ Z\[ ` ] R ��ed f F � WYX � Z\[ ` ] ^HI(7)
F �S X � Z\[ ` ] ^ H S(8)
Les
F � sont les multiplicateurs de Kuhn-Tucker.
RO-MIM2 – 9/63
Conditions de Lagrange
Un contrainte d’égalité �� /" peut se représenter par deuxcontraintes d’inégalité �� ? "
et �� !"
.
Il lui correspond deux multiplicateurs de Kuhn-Tucker,
; g� et
;h �
positifs.
On peut les regrouper en un seul dont le signe est quelconque. Aune contrainte d’égalité correspond un multiplicateur noncontraint en signe.
Si toutes les contraintes sont des égalités, les multiplicateurspeuvent être de signe arbitraire. Ils prennent le nom demultiplicateurs de Lagrange.
Dans ce cas particulier, toutes les contraintes doivent êtresaturées.
RO-MIM2 – 10/63
Méthode des plans sécants
Soit à calculer :
i jlk + �� 3(9) �� ��� ! " 3 @ / 23 ) ) )3 5(10) � # & ' ((11)
où on suppose que les fonctions+
et �� sont convexes.
On remarque que l’on peut supposer
+linéaire. Sinon, on peut
remplacer le problème ci-dessus par le problème équivalent :i jlk m3(12) mD + ��� ? " 3(13) �� ��� ! " 3 @ / 243 ) ) )3 5(14) � # & ' (
(15)
RO-MIM2 – 11/63
Plans sécants, II
On procède de façon itérative. A l’étape
n
, on suppose que l’on connaît un polyèdre convexeo pq r
tel que : o pq rts uwv xQy zQ{ |y }~ � ���On résoud le programme linéaire :
� ��� � |y }��(16) y � o pq r �(17)
Soit y p q r
le point obtenu.
Si y pq r � u
, c’est le minimum cherché. Sinon, il existe
�
tel que{� |y pq r }� �
. On forme :
o pq �� r v o pq r� xQy z{� |y pq r } g �{� |y pq r } � � |y h y pq r }~ � ��
et on recommence.
RO-MIM2 – 12/63
Plans sécants, III
Lemme 1 Si
+
est convexe, alors
+ ��� ? + ��� > . + � � � ) ��� D �
.
Pour simplifier on va supposer que � est un scalaire. Soitpar exemple
� : � . Par définition,+ �� D + ��� ! ��� D � � |� } h � |Q� }� h � . En faisant tendre � vers� on en déduit
+ � � � ! � |� } h � |Q� }� h � , ce qui n’est autre que le
résultat cherché. La démonstration est analogue pour� < � .
RO-MIM2 – 13/63
Plans sécants, IV
Lemme 2
� | n g� }Y� -
.
Soit en effet � un point de
�
. Puisque � � est convexe, on a� � ��� �� �� � � �� � �� �� ��� �� � � ¡� ��� ¢ � �� � �. Or � � ��� � �
, donc� � £ ��¤ f �
.
Lemme 3 � | n }e¥ # � | n ¦ }3 § � : §Il suffit d’observer que � �� �
ne satisfait pas la contrainte� � ��� � � � �� �� ��� �� � � ¡� ��� ¢ � �� � � �.
Lemme 4 Si � | n } # -, c’est le minimum cherché.
En effet, d’une part � �� � � �, et d’autre part,
� � � ¨ � � £ �� � ¨ � ��� � � � ��� � � � ��
RO-MIM2 – 14/63
Plans sécants, V
Théorème 5 Si
-
est borné, tout point d’accumulation de la suite� | n }
est un optimum.
Soit © ` un point d’accumulation, et soit © �� �une suite extraite de [ `
etconvergeant vers © ` . Montrons d’abord que © ` L ª
. On supposera pourfixer les idées que à chaque pas, la contrainte utilisée pour construire unecoupe est celle qui est la moins satisfaite, c’est à dire celle pour laquelleX � Z\[ �e« ] ]¬ H
est maximum. Supposons que © ` ne soit pas dans
ª
, et
soit X � la contrainte la moins satisfaite. Puisque © �� �converge vers © il
existe un
« `
suffisamment grand pour queX � soit la contrainte la moinssatisfaite en © �� �
. On ajoute la contrainte :
X � Z © �� � ] WYX � Z © � � � ] ¡S Z\[ R © �� � ]® H S
RO-MIM2 – 15/63
Plans sécants, VI
Il est facile de voir que la distance
¯ ¯ © °� ¦ � R © �� � ¯ ¯I « ±¬ «ne peut
être inférieure à
²�³� ��´ µq r ²²¶ ³� ��´ µq r ² , ce qui contredit le fait que © ` est limite des© � � �
.Supposons maintenant qu’il existe dans
ªun autre point © ± tel que_ Z © ± ]· _ Z © ` ] . Comme © ± L ¸ �� � N«
, il s’en suit que l’algorithme de
programmation linéaire devrait toujours construire un point [ � � �
tel que_ Z\[ �� � ] ® _ Z © ± ] . Par suite de la continuité de
_, toute limite [ `
de la
suite [ �� �
doit être telle que
_ Z\[ ` ] ® _ Z © ± ] ce qui est contradictoire.
RO-MIM2 – 16/63
Méthodes de pénalités
Principe : au lieu d’exclure les points qui violent les contraintes,ajouter à la fonction économique une pénalité d’autant plusélevée que la contrainte est moins respectée. Si la fonction depénalité est régulière, on peut utiliser les méthodes d’optimisationsans contrainte.
En général, la pénalité dépend d’un paramétre qui permet derégler son importance. Quand la pénalité devient très grandedevant la fonction objectif, on tend vers l’optimum souscontrainte. Mais la fonction à optimiser devient de plus en plusmal conditionnée.
Deux variétés :La fonction de pénalité est nulle dans le domaine faisable. L’optimumpénalisé n’est pas faisable. C’est une méthode extérieure.
La fonction de pénalité devient infinie quand on sort du domaine faisable.L’optimum est faisable, mais la méthode a besoin d’un point faisable initial.
RO-MIM2 – 17/63
Méthodes extérieures
On considère la fonction
¹ ���
égale à
"
si � !"et à � º
sinon. Ilest facile de voir qu’elle est continue et à dérivé continue.
On remplace le problème :»\¼ i jlk + �� 3(18) �C� ��� ! " 3 @ / 23 ) ) )3 5(19) � # & ' ((20)
par la suite de problèmes :» n ¼ i jk + �� > $ n (� v � ¹ � �� ��� )
où les
$ n forment une suite croissante tendant vers l’infini.
On note
½ �� / (� v � ¹ � �� ���
et � n la solution de
» n .RO-MIM2 – 18/63
Convergence, I
Théorème 6 Si
+
est continue, si l’ensemble des points faisables estfermé et si soit
+ ��
soit
½ ��
tend vers l’infini quand � tend versl’infini, alors tout point d’accumulation de la suite � n est une solutionde
»
.On note
¾ n / + ��� n > $ n ½ �� n , et � ,une solution de
»
.Lemme 7 Les
¾ n forment une suite décroissante.
On a
_ Z\[ �¤ f ] ¿�¤ f À Z\[ � ¤ f ]¬ _ Z\[ �¤ f ] ¿� À Z\[ � ¤ f ] parceque
¿� ¤ f ¬ ¿� et
_ Z\[ �¤ f ] ¿� À Z [ �¤ f ] G _ Z\[ � ] ¿� À Z\[ � ]
puisque [ � est la solution de
Á� . CQFD.De plus,
Â� ® _ Z\[ ` ] ¿� À Z\[ ` ]. Mais comme [ `
est faisable, lapénalité est nulle. On a donc l’encadrement_ Z\[ � ]® Â� ® _ Z\[ ` ]S
RO-MIM2 – 19/63
Convergence, II
Lemme 8 Les
½ ��� n forment une suite décroissante.
Comme chaque � n est la solution d’un problème deminimum, on a :+ ��� n > $ n ½ �� n ! + �� n g� > $ n ½ �� n g� 3(21) + �� n g � > $ n g� ! + �� n > $ n g� ½ �� n )(22)
En additionnant et simplifiant :� $ nD $ n g� � ½ �� n g� D ½ �� n ? " )
Comme le premier terme est négatif, l’autre l’est aussi.
RO-MIM2 – 20/63
Convergence,III
Les � n appartiennent à un ensemble borné, soit parce que+ �� n ! + �� ,
et que
+
tend vers l’infini à l’infini, soit parce que½ �� n ! ½ �2
et que
½
tend vers l’infini à l’infini. On peut doncextraire de � n une sous-suite �à 3 Ä # Å
qui converge vers
� .
Par continuité,
+ ��Ã
tend vers
+ � � , et comme
+ �� n ! + �� ,
,+ � � ! + ���
.
Comme
¾ n ! + �� ,
,
¾ n a une limite Ç ¹ @ , ! + ��� ,
.È j i $à ½ ��à / ¾ ,D + � Æ� . Donc
½ ��Ã
tend vers 0, et parcontinuité
½ � Æ� /" .
Donc
� est un point faisable, donc
+ � � ? + �� ,
, donc+ � � / + ��� , et
� est un optimum.
RO-MIM2 – 21/63
Méthodes intérieures
On prend comme fonction de pénalité une fonction qui tend versl’infini au voisinage de 0, par exemple
¹ ��� /CD 2 É�� .
On minimise
+ �� > Ê (� v � ¹ � �� ��� .
Dans les mêmes conditions que ci-dessus, on montre quel’optimum du problème
»ÌË tend vers l’optimum de
»
quand
Ê
tend vers 0.
Toutes les solutions intermédiaires sont faisables, mais il fautdisposer d’un point faisable pour commencer les calculs.
RO-MIM2 – 22/63
Exemple
Le problème du cas le pire de Fourier-Motzkin :i ÍÎ � Ï> m3(23) � > Ï> m / 5(24)
On élimine m à l’aide de la dernière contrainte et on applique laméthode des pénalités :
i ÍÎ � Ï> 5D � D Ï> $ � 5D � D Ï º )
On utilise un système de calcul algébrique pour achever lescalculs.
RO-MIM2 – 23/63
Fonction de Lagrange, point-col
Soit à résoudre :
i jlk + �� 3(25) �� ��� ! " 3 @ / 23 ) ) )3 5(26) � # $ %& ' ((27)
La fonction de Lagrange associée est :Å �� 3 ; / + �� > ;) � �� 3 ;? " )
� est le vecteur dont les composantes sont les �� .
RO-MIM2 – 24/63
Point-col
� � ` Ð ` �
est un point-col ssi :
� ` � Ñ Ð ` � ��
Ò� � ÑÔÓ Õ � � ` Ð ` � Õ ��� Ð ` �
Ò Ð� � Ó Õ ��� ` Ð ` �� Õ ��� ` Ð ��
Caractérisation d’un point-col :Õ ��� ` Ð ` � � � ���×ÖU Ø Õ ��� Ð ` �(28) � ��� ` � �(29) Ð `� � ��� � � ��(30)
RO-MIM2 – 25/63
Preuve, I
Soit
��� ` Р` �
un point-col. La première propriété est une conséquence directede la définition.La deuxième propriété entraine :� � � ` �� Ð `� � ��� ` �� � � � ` �� Ð� � � � ` �
� Ð ¢ Ð ` �� � ��� ` � ��S’il existait un � � ��� ` �
positif, il suffirait de prendre le
Ð � correspondantsuffisamment grand pour violer cette inégalité. Donc
Ò �Ó �� ��� ` � �
.Pour
Ð � �
on trouve : ¢ Ð `� � ��� ` � ��
Mais les deux termes du produit sont non négatifs, donc le produit est nul.
RO-MIM2 – 26/63
Preuve, réciproque
La première caractéristique entraine directement la première propriétédu point-col.On déduit de la troisième caractéristique que
Š��� ,3 ; , / + �� ,
.Enfin : Š�� ,3 ; / + �� , > ;) � �� , ! + ��� , / Š��� ,3 ; , 3
puisque � ��� , !"
.
RO-MIM2 – 27/63
Intérêt
Théorème 9 Si
�� ,3 ; ,
est un point-col, alors � ,est un minimum
global.
D’après la définition, � , # $
et � �� , !", donc � ,
estfaisable.
D’autre part :
N[ L ¿I X Z\[ ] ® H P _ Z\[ ` ] ^ Ù Z\[ `I F ` ] ® Ù Z\[I F ` ] ^ _ Z\[ ] F ` X Z\[ ] ® _ Z\[ ]S
puisque
; , ? "
et � ��� !".� ,
est donc bien minimum global.
Mais il existe des problèmes qui n’ont pas de point-col.
RO-MIM2 – 28/63
Fonction de Lagrange et pénalités
La fonction de Lagrange est une fonction de pénalité.Å ��� 3 ; / + �� > ;) � ��� 3 ;? " )
En effet, dans la région infaisable, � ��� : ", donc le second
terme augmente la valeur de
Å, alors qu’on recherche un
minimum.
Toutefois, ce terme est négatif dans la région faisable, ce quidiminuerai artificiellement la valeur du minimum, si l’on n’avaitpas la contrainte
Ú @ ¼ ; � ) �� �� , /" .
Comme les méthodes de pénalité, l’emploi de la fonction deLagrange permet de remplacer un problème avec contraintes parun problème sans contrainte.
RO-MIM2 – 29/63
Une mauvaise idée
Maximiser
Š�� 3 ;
par rapport à
;? "
pour � fixé. Soit
Ä ��� le
résultat. Minimiser ensuite
Ä ���
sans contraintes.
Il est facile de trouver le maximum.Si X � Z\[ ]¬ H
, il suffit de faire tendre
F � ÛÜ pour obtenir un maximuminfini.
Sinon, le maximum est égal à
_ Z\[ ].
Ceci revient donc à étendre
+en une fonction discontinue non
dérivable, ce qui ne se prète pas à l’optimisation.
RO-MIM2 – 30/63
Une bonne idée
Minimiser Ý � ; / i jlk Å �� 3 ;
sans contrainte. MaximiserÝ � ;
sous la contrainte
;? "
.
Lemme 10 Ý � ;
est une fonction concave.
Soit
F fI FßÞ deux valeurs de
F
, à et
ádeux nombres positifs tels queà á ^ b
, et [ un point arbitraire. Par définition des minima :_ Z\[ ] F f X Z\[ ] G â Z F f ]I(31) _ Z\[ ] F�Þ X Z\[ ] G â Z F�Þ ]I(32) _ Z [ ] Z à F f á F�Þ ] X Z\[ ] G à â Z F f ] á â Z F Þ ]S(33)
et cette propriété vraie partout s’étend au minimum â Z à F f á F Þ ]
.
RO-MIM2 – 31/63
Application à la programmation linéaire
Il ne faut cependant pas croire que l’optimisation de ã est toujours sans contrainte. Soit parexemple le programme linéaire : � ��� ä� y �(34) åy h � æ ��(35) y æ ��(36)
La fonction de Lagrange associée est :ç |y � è } v ä� y h è | åy h � } h éy v | ä h è å h é } � y g è� �(37)
Il est facile de voir que si ä h è å h é n’est pas nul, la valeur du minimum est h ê. Sinon,c’est
è�
. Comme ä h è å h év �est équivalent à ä h è å æ �
, on voit que l’on estamené à résoudre : � ëì è� � �(38) ä h è å æ ��(39) è æ ��(40)
C’est le dual du problème original !
RO-MIM2 – 32/63
Et s’il n’y a pas de point col ?
Théorème 11 Soit � ,
la solution du problème avec contraintes. Ona : i ÍÎ è æ � Ý � ; ! + ��� ,
.
Comme [ `
est faisable, X Z\[ ` ] ® H
. DoncÙ Z [ `I F ] ^ _ Z\[ ` ] FX Z\[ ` ] ® _ Z [ ` ]I(41) â Z F ] ^ í îQï Ö Ù Z\[I F ] ® Ù Z [ `I F ] ® _ Z\[ ` ]S(42)
Cette propriété vraie pour tout
Fs’étend au maximum.
La solution du problème dual fournit une borne inférieure de lasolution du primal.
Il y a « saut de dualité » quand les deux solutions ne sont paségales.Ý est dérivable à l’optimum, ssi le saut de dualité est nul.
RO-MIM2 – 33/63
Méthode de génération de colonnes, I
Si l’ensemble
$ / 1 � �3 ) ) )3 � ( 6
est fini, le problème s’écrit :
i Í Îè æ � (i jlk� v � + ��� � > ; � �� � (43)
se ramène à un problème de programmation linéaire :» � 5 ¼ i ÍÎ m(44) m ! + ��� � > ; � �� � 3 @ / 243 ) ) )3 5(45) ; ? " )(46)
Soit � (3 ; (la solution de
» � 5 .
RO-MIM2 – 34/63
Génération de colonnes, II
Si
$
est infini, on suppose que l’on a déja construit les points1 � �3 ) ) )3 � ( 6
.
On résoud le problème linéaire ci-dessus.
On détermine le point � ( g � comme solution de :
i jlky � ð Å �� 3 ; ( / + �� > ; ( � ��
par une méthode d’optimisation sans contraintes.
Soit Ý � ; (
le minimum obtenu.
On recommence avec 5> 2points, jusqu’à convergence.
RO-MIM2 – 35/63
Génération de colonnes, III
Lemme 12 Soit � ,
la solution du problème avec contrainte :Ý � ; ( ! + ��� ,
.
Puisque � , # $
, Ý � ; ( ! + �� , > ; � �� , ! + ��� ,
puisque que � ,
est faisable.
Lemme 13
+ ��� , ! m (
.
Il est évident que
ñ + �� , 3 ; ( òest un point faisable pour» � 5 .
Lemme 14 m ( g� ! m (.
Evident parce que tout point faisable pour
» � 5> 2
est
faisable pour
» � 5 .
RO-MIM2 – 36/63
Convergence
On a l’encadrement Ý � ; ( ! + �� , ! m (
.
Comme la suite m (
est décroissante, elle converge.
Mais la convergence de Ý � ; (
vers
+ �� , impliquerait que le
saut de dualité est nul, ce qui n’est pas toujours le cas.
RO-MIM2 – 37/63
Optimisation Combinatoire
RO-MIM2 – 38/63
Optimisation combinatoire
Problème d’optimisation sous contraintes où l’ensemble despoints faisables est non pas continu mais discret.
Forme du problème : i jk + ��� (47) � # $(48)
Les inconnues sont les 5 composantes du vecteur � .
$
estl’ensemble discret des points faisables.
En général,
$
est produit cartésien d’ensembles plus petits, et sataille est le produit des tailles de ces petits ensembles (d’où lenom : optimisation combinatoire).
Chaque composant de
$correspond à un choix ; il faut trouver la
bonne suite de choix, sachant que ceux-ci ne sont pasindépendants en général.
RO-MIM2 – 39/63
Exemple, I
On considère un ordinateur sur lequel on doit exécuteró
algorithmes enchaînés
ô �3 @ / 243 ) ) )3 ó
. Chaque algorithme apour données les résultats de l’algorithme précédent.
Pour implémenter chaque algorithme, on doit choisir unestructure pour ses données. On suppose qu’il y a õ structurespossibles,
$ n3 § / 243 ) ) )3 õ et que le temps d’exécution del’algorithme dépend de la structure choisie. Par exemple, unematrice peut être rangée par ligne ou par colonne, et, par suitedes effets de cache, le temps d’exécution du produit matricielvarie suivant la structure choisie. On supposera qu’un algorithmene modifie pas la structure des ses données. On note
ö� n letemps d’exécution de l’algorithme
@
quand les données on lastructure
$ n .
RO-MIM2 – 40/63
Exemple, II
On suppose qu’il est possible de modifier les structure dedonnées (par exemple, de transposer une matrice). On note
÷ nÃ
le temps nécessaire pour passer de la structure$ n à la structure$Ã . Remarquer que
÷ n n /" .
La structure du programme est alors :$ nùø Ê � $ n� ô� $ n� ) ) ) ô�ú $ nùû Êú $ n û ��
On suppose que
§ � et
§ú g� sont fixés par le cahier des charges.
Trouver la séquence de restructurations donnant le temps totalminimum.
RO-MIM2 – 41/63
Quelques méthodes de solution, I
Une heuristique gloutonne.
On remarque que souvent
÷ nü ý ö� n . Pour l’exemple matriciel, letemps de transposition est
þ � 5 º alors que le temps du produitest
þ � 5 ÿ .On choisit donc
$ n� de façon que
ö� n� soit minimum, et onrajoute des redistributions si nécessaire.
RO-MIM2 – 42/63
Méthodes de solution, II
Programmation dynamique. On remarque que le problème a unestructure analogue à celle d’un problème de plus court chemin.
On note
» ( � §
le problème d’optimiser le programme analogueau programme initial, mais ou on s’arrête juste après laredistribution
Ê ( avec une structure de données
$ n . Leproblème initial est
»ú � §ú g�
. Soit� ( � §
le meilleur tempsd’exécution de
» ( � §
. On a la relation de récurrence :� ( � § / i jlkà � (h � � Ä > ö (à > ÷à n3(49) � � � § / ÷ nùø n )(50)
On peut calculer toutes les valeurs de
� ( n à l’aide de cetterécurrence, lire la valeur de
� ú � §ú g�
et reconstituer le chemin àsuivre par retour arrière.
RO-MIM2 – 43/63
Méthodes de solution, III
Codage en variables 0-1. On pose
�� � � �
si la distribution desdonnées à l’étape
�
est la distribution
� , et 0 sinon.
A chaque étape, il y a une et une seule distribution :�� d f �� � � ��(51)
Le temps de calcul total est :
��� � � ��ed f � �� d f �� �� �� � .
Le temps de redistribution de l’étape�
à
�� �
est donné par
�� tel que�� � � �
et
� � �¤ f � � �, ce qui peut s’écrire :�� � �
�ed � �� d f
�d f �� � � � �¤ f � �� �(52)
Il s’agit de minimiser la somme
� � � � sous les contraintes (51) et�� � � � � � �. C’est un problème de programmation quadratique en
nombres entiers.
RO-MIM2 – 44/63
Méthodes de résolution, IV
Quand les variables sont 0/1 il est possible de représenter le produit [ S © par unsystème de contraintes linéaires. En fait, [ S © ^ í îQï Z [I © ] !Pour chaque terme í îï Z\[I © ] , on introduit deux variables 0-1, �, qui donne lavaleur du produit, et
�
, qui sert à choisir quelle est la plus petite variable de [ oude ©.Le système de contrainte est :�® [ I �® ©� � G [ I � b R � G ©S
Il est facile de montrer que ces contraintes suffisent à fixer la valeur de � :x y z t
0 0 0 0/1
0 1 0 1
1 0 0 0
1 1 1 0/1
RO-MIM2 – 45/63
Programmation linéaire en entiers
Définition. � @ 5�� � 3(53) ô� > � ? " 3(54) � # & �)(55)
(56)
Noter que � #& �
implique � ? ". Il s’agit donc de l’analogue
exact du problème résolu par l’algorithme dual, à ceci près qu’il ya une contrainte d’intégrité en plus.
On suppose en général que
ôet
�
ont des coefficients entiers.
RO-MIM2 – 46/63
Coque entière
Soit
$
un ensemble de
& ' (
. La coque entière de$
, notée
Æ $est
la coque convexe de l’ensemble des points entiers de
$.� # � � (�� $ = � # Æ $3(57) � 3 Ï # Æ $3 ;3 �? " 3 ;> � / 2 = ;� > � Ï # Æ $)(58)
RO-MIM2 – 47/63
Propriétés de la coque entière
Lemme 15
Æ ô % ô
.
Lemme 16
ô % � = Æ ô % Æ �
.
Lemme 17 Si
� � (�� » % $
convexe, alors
Æ » % $.
Un point de
Æ ô
est combinaison convexe d’un certainsnombres de points de
� � (�� », qui appartiennent par
hypothèse à
$
. Or
$
contient toutes les combinaisons
convexes de ses points, CQFD.
RO-MIM2 – 48/63
Caractérisation de la solution entiére
Théorème 18 La coque entière d’un polyèdre est un polyèdre.
Soit
» / �> A
un polyèdre, où
�
est borné et
Aun
cone. On peut supposer que les vecteurs générateurs � � deA
sont entiers, et il est facile de voir queÆ A / A
.Soit
� / 1 � � � � � B " ! � � ! 2 6. Il est clair que
�
estun polyèdre borné inclu dans
A. On va montrer queÆ » / ��> �> A
. Or
�> �est borné, et pour un polyèdre
borné le théorème est évident, puisque la coque entière estenveloppe convexe de ses points entiers qui sont en nombre
finis. CQFD.
RO-MIM2 – 49/63
Coque entière, II
Lemme 19
Æ » % ��> �> A
.
D’après un lemme ci-dessus, il suffit de considérer unpoint � entier de
»
. On peut l’écrire� / �> 73 � # �3 7 # A
. Il en résulte 7 / � � � � � . Onpose 7 � / � � � � � � � et
� / 7D 7 �. Il est clair que
� # �
,donc que �> � # �> �
, que 7 � # Aest entier, et que�> � / � D 7 est entier, donc que �> � # ��> �
.
Lemme 20
��> �> A % Æ ».
Puisque
�> � % »,��> �> A % Æ »> A / Æ »> Æ A / �»> A / Æ »
.
RO-MIM2 – 50/63
Minimum entier
Lemme 21 Le minimum entier d’un polyèdre est le minimum rationelde sa coque entière.
Le minimum entier [ `
appartient à la coque entière. Supposons qu’ilexiste dans la coque entière un point [ ±� [ `
. Ce point estnécessairement à coordonnées non entières (puisque la coque entière estcontenue dans le poyèdre). [ ±
est donc combinaison convexe d’un certainnombre de points entiers qui lui sont tous supérieurs dans l’ordre
lexicographique, ce qui est impossible.
Le problème sera résolu si on sait construire la coque entière.
Malheureusement, la complexité de la coque entière peut êtreénorme.
Heureusement, il n’est pas nécessaire de la construireentièrement. on peut se contenter de construire quelquescoupes : des contraintes affines qui excluent une partie de
»
mais aucun point de
Æ »
.
RO-MIM2 – 51/63
Coupe de Gomory
Construction d’une coupe : soit� É ) � > � É ? "
(59)
une des contraintes du problème.
est le dénominateur
commun des coefficients de � et du terme constant.
Par construction de l’algorithme dual, la valeur de cette contrainteest l’une des variables d’écart du problème initial, qui doit êtreentière. Comme les � sont entiers :� � > � i ! " / " 3(60) ��� i ! " � # �D � i ! " � i ! " 3(61) ��� i ! " � / �D � i ! " > § 3(62)
§
est nécessairement positif, d’où :��� i ! " � D �D � i ! " ? " )(63)
RO-MIM2 – 52/63
Algorithme de Gomory
On a mis le problème sous la forme : í îï%$ [(64) © ^ ¿ � � G H(65) � G H(66)
(67)
où la matrice
¿
et le vecteur
�
sont entiers, ainsi que les variables © et �. � est unextrait de ©, et les c premières composantes de © sont les variables originales.
On procède comme dans l’algorithme du Simplex jusqu’à obtenir
� GH
. Sil’algorithme échoue, il n’y a pas de solution entière.
Si les c premières composantes de
�sont entiières, c’est la solution.
Sinon, on choisit le premier� � non entier, on construit une coupe comme
ci-dessus à l’aide de la contrainte
¿� � � � GH
, et on l’ajoute au tableau.
Le nouveau tableau n’est pas faisable puisque le terme constant de la coupe estnégatif. On reprend donc l’algorithme du simplex jusqu’à terminaison.
RO-MIM2 – 53/63
Preuve, I
Théorème 22 Si l’algorithme se termine, ou bien on a trouvé lasolution entière, ou bien le problème n’a pas de solution.
Soit
» ( le polyèdre obtenu après la 5ième coupe. Parconstruction, tous les points entiers de
» / » � sont dans» (. Si donc
» ( est vide,
»
ne contient aucun point entier.Sinon, soit � ,
le minimum lexicographique de
» (, etsupposons qu’il est entier. Si
»contenait un point entier
plus petit, il serait dans
» ( ce qui serait une contradiction.
RO-MIM2 – 54/63
Preuve, II
Lemme 23 On peut toujours supposer que l’ensemble des solutions est nonvide.
On considère le problème étendu � ��� $ & �(68) &� '� � ( � �(69) & � �(70) � � �(71)
Il est clair que ce problème a toujours une solution : il suffit deprendre � nul et & très grand. Si le problème initial a un minimum� `
, alors
� � `
est le minimum du problème étendu. Inversement,si le problème initial n’a pas de solution, alors & ne peut être nuldans la solution du problème étendu. Les deux problèmes sont
donc équivalents.
RO-MIM2 – 55/63
Preuve, III
Lemme 24 Les minima successifs � � forment une suite croissante dansl’ordre lexicographique.
Evident, puisque
) �¤ f * ) � .A une certaine étape de l’algorithme, soit
�,+ �-. � + � �. � �
la ligne quiva fournir la coupe.
A l’étape qui suit, l’algorithme du Simplex exécute un pivot. Soit � + lavariable éliminée.
Soit :
�+ � ¦- . � + � � ¦. � �la ligne après l’exécution du pivot.
RO-MIM2 – 56/63
Preuve, IV
Lemme 25 Il existe un nombre entier
�
tel que
ú/ < � ! ú ¦/ .
La coupe est :
+ 0+ í 1 233 [ + R R � í 1 233 G H(72)
Les formules de changement de base donnent :� ±3 ^ �3 0+3 R � í 1 2 33 30+ í 1 2 3 ® �3 R � í 1 233 S(73)
Soit 4 le quotient entier par défaut de
�par
3:
� ^ 43 � í 1 23
.� ±3 G 4 � í 1 2 3 Z R � í 1 2 3 ]3 S(74)
Le deuxième terme est égal à 1, il suffit donc de prendre
¸ ^ 4 b
.D’autre part
� 53 ^ Z 4 b ] R Z3 R � í 1 23 ] 53 · 4 b
. L’inégalité
est stricte puisque
�n’est pas entier.
RO-MIM2 – 57/63
Preuve, V
A un instant donné du déroulement de l’algorithme, on dit qu’uneligne est active si lors d’une opération ultérieure, la valeur de sonsecond membre changera.
Lemme 26 La première ligne ne peut être active qu’un nombre fini defois.
Soit 6 f � 78 f 9 . On a l’encadrement 6 f ¢ :; 8 f < 6= .Considérons l’évolution de 6= après une coupe.
Si la source de la coupe est la ligne 1, après le changement debase qui suit, 6= augmente au moins d’une unité. Si la source estune autre ligne, c’est que
8 = est entier. Une autre ligne est sourcede la coupe, et si la première ligne est active, c’est que
Ñ = + est nonnul. La valeur de
8 = augmente. Qu’elle prenne une valeur entièreou fractionnaire, la valeur de 6= augmente au moins d’une unité.
Or la valeur de8 = et donc celle de 6= est bornée par la solution
optimale > ?= . CQFD.
RO-MIM2 – 58/63
Preuve, VI
Théorème 27 L’algorithme des coupes de Gomory converge.
Nous avons vu que la première ligne ne peut être activequ’un nombre fini de fois. Aprés la dernière modification,tout se passe comme si le problème à résoudre avait unecontrainte et une inconnue de moins (méthode de déflation).On peut donc prouver que la deuxième ligne n’est activequ’un nombre fini de fois. De proche en proche, on voit que
l’algorithme se termine.
RO-MIM2 – 59/63
Complexité
Comme il faut pouvoir distinguer entre nombres entiers etnombres fractionnaires, les calculs doivent être menés enarithmétique exacte.
Les nombres à manipuler sont des déterminants desous-matrices @ A @ de la matrice des contariantes. Leur taille(nombre de bits) est donc bornée par @ fois le nombre de bits duplus grand coefficient.
Le nombre maximum de coupes est borné par le nombre decoupes nécessaires pour caractériser la coque entière del’ensemble des solutions. Résultat de Chvatal.
RO-MIM2 – 60/63
Techniques de codage, I
On peut coder un choix entre @ possibilités à l’aide de @variables 0-1,
BDCFEG G G E B,H .
Chaque variable entière ne peut prendre que les valeurs 0 ou 1 :I JLK JM
.
Les choix sont exclusifs :
HONQP C BRN SM .
Si à chaque choix est associé une quantité T N , la quantitéassociée à un jeu de variables est
HONQP C BUN V N .On peut considérer les
BRN comme des booléens et coder lesopérateurs :W # BX Y[Z Z W\ BE W\ YE WJ B] YE(75) W_^ B` Y[Z Z WJ BE WJ YE W\ B] Yba M E(76) W_^Fc B Z Z WSM a BG(77)
RO-MIM2 – 61/63
Techniques de codage, II
Problèmes de graphe. On peut représenter un graphe denombreuses façons : matrice d’incidence, matrice de connexion,WNd SM ssi il existe un arc
egf h
.
Chemin :
BNd SM ssi le chemin emprunte l’arc
egf h.
Contrainte :
BNd J WNd .
Loi de Kirchoff : N BRNd S i Bdi , pour tout
hexcepté le début
et la fin du chemin.
Chemin simple : ne passe qu’une fois par chaque sommet.N BjNd J M
.
Pour le début, d BNd SM , et pour la fin N BRNd SM .
Minimiser la somme N d BUNd assure que le chemin n’a pas deboucles isolées.
RO-MIM2 – 62/63
Techniques de codage, III
Techniques de grands nombres. Soit
k S lK mn K ] o \ I petq S lK mr K ] s \ I p
deux polyèdres dont on doit explorer lespoints entiers. Soit t une nouvelle variable 0-1.
Si
k
et
q
sont bornés, alors pour
usuffisamment grand, le
poylèdre :vw xzy {[|z} ~ �� ~ � � � �| �� } � ~ � � � � ���� | � � � �
(78)
est l’union disjointe de
ketq
.
On peut mener l’exploration sur
k� qen une seule fois.u
doit être choisi de telle façon queK � k
entrainer K ] s] u \ Iet réciproquement.
RO-MIM2 – 63/63
Recommended