Recherche Op´erationnelle Deuxi`eme Partie

Recherche OperationnelleDeuxieme Partie

Paul Feautrier

ENS Lyon

29 novembre 2005

Plan

I Introduction et principaux concepts

I Optimisation continue sans contrainte

I Programmation lineaire

I Optimisation continue sous contrainteI Optimisation combinatoire

I Programmation lineaire en nombres entiers.I ExplorationI MetaheuristiquesI Programmation dynamique

I Elements de Complexite

Optimisation sous contraintes

courbes de niveau dela fonction objectif

optimum

contraintes

I Resoudre :min f (x),

gi (x) 6 0, i = 1, . . . , nx ∈ Rn

I L’ensemble des points faisables estx ∈ Rn | gi (x) 6 0, i = 1, . . . n. Lesfonctions g sont les contraintes.

I La programmation lineaire est le casparticulier ou f et les gi sont lineaires.On obtient des problemes plus oumoins difficiles suivant que l’un oul’autre ou les deux de ces elementssont non lineaires (resp. nonconvexes).

Generalisation

I Certaines contraintes peuvent etre difficiles a mettre sous laforme gi (x) 6 0.

I Exemple: on veut que x soit entier (i.e. a coordonneesentieres).

I On remplace la derniere contrainte par :

x ∈ S ⊆ Rn.

Organisation de l’expose

I Conditions necessaires de Kuhn-TuckerI Methodes directes ; linearisation.

I Methode des plans secants.

I Fonction de Lagrange, point-col.I Methodes duales

I Methodes de penaliteI Methodes lagrangiennes

Plan

Kuhn-Tucker

Une methode directe

Methodes duales

Fonction de Lagrange, point-col

Optimisation combinatoirecoque entiereAlgorithme de GomoryTechniques de codage

Caracterisation de l’optimum I / III

I On suppose les fonctions f et gi continues et a deriveescontinues.

I L’optimum x∗ peut etre a l’interieur de F . Dans ce cas∇f (x∗) = 0 .

I L’optimum peut etre sur les frontieres de F . Dans ce casgi (x

∗) = 0 pour un certain nombres de contraintes (lescontraintes saturees) et ∇f (x∗) n’est pas necessairement nul.On note I ⊆ 1, . . . , n l’ensemble des indices des contraintessaturees.

I En particulier, si les contraintes sont toutes des contraintesd’egalite, l’interieur de F est vide et l’on est toujours dans ledernier cas (dit de Lagrange).

Caracterisation de l’optimum II / III

I En programmation lineaire, f (x) = c.x , ∇f = c n’est jamaisnul (ou bien le probleme est trivial), donc l’optimum est sur lafrontiere de F .

I Une direction d est admissible en un point x∗ ∈ F si il existeη > 0 tel que λ < η ⇒ x∗ + λd ∈ F .

I x∗ est un minimum si, pour toute direction admissible d ,

λ < η ⇒ f (x∗ + λd) > f (x∗).

I La condition d’admissibilite peut s’ecrire :

gi (x∗ + λd) = gi (x

∗) + λd .∇gi (x∗) 6 0, i ∈ I ,

soit encore d .∇gi (x∗) 6 0, i ∈ I .

Caracterisation de l’optimum III / III

I Les directions admissibles en x∗ appartiennent au cone

C = d | d .∇gi (x∗) 6 0, i ∈ I ,

avec I = i | gi (x∗) = 0.

I La reciproque est fausse, sauf dans quelques cas particuliers :I Les fonctions gi sont lineaires ou convexes ;I Les gradients sont lineairement independants.

I Si C est l’ensemble des directions admissibles, alors unecondition necessaire d’optimalite est :

d ∈ C ⇒ f (x∗ + λd)− f (x∗) > 0,

d ∈ C ⇒ d .∇f (x∗) > 0.

Conditions de Kuhn et Tucker

I D’apres le lemme de Farkas, il existe des λi > 0, i ∈ I telsque :

∀d : −d .∑i∈I

λi .∇gi (x) = d .∇f (x∗),

∇f (x∗)−∑i∈I

λi∇gi (x) = 0.

I Si on pose λi = 0 pour les contraintes non saturees, on peutetendre la sommation a toutes les valeurs de i . Une conditionnecessaire pour que x∗ soit un minimum est donc :

∃λi > 0 , i = 1, . . . , n

∇f (x∗) −n∑

i=1

λi∇gi (x∗) = 0,

λi .gi (x∗) = 0.

I Les λi sont les multiplicateurs de Kuhn-Tucker.

Conditions de Lagrange

I Un contrainte d’egalite gi = 0 peut se representer par deuxcontraintes d’inegalite gi > 0 et gi 6 0.

I Il lui correspond deux multiplicateurs de Kuhn-Tucker, λ+i et

λ−i positifs.

I On peut les regrouper en un seul dont le signe est quelconque.A une contrainte d’egalite correspond un multiplicateur noncontraint en signe.

I Si toutes les contraintes sont des egalites, les multiplicateurspeuvent etre de signe arbitraire. Ils prennent le nom demultiplicateurs de Lagrange.

I Dans ce cas particulier, toutes les contraintes doivent etresaturees.

Plan

Kuhn-Tucker

Une methode directe

Methodes duales

Fonction de Lagrange, point-col

Optimisation combinatoirecoque entiereAlgorithme de GomoryTechniques de codage

Methode des plans secants I / VII

I Soit a calculer :

min f (x),

gi (x) 6 0, i = 1, . . . , n

x ∈ Rn

ou on suppose que les fonctions f et gi sont convexes.

I On remarque que l’on peut supposer f lineaire. Sinon, on peutremplacer le probleme ci-dessus par le probleme equivalent :

min z ,

z − f (x) > 0,

gi (x) 6 0, i = 1, . . . , n

x ∈ Rn

Methode des plans secants II / VII

I On procede de facon iterative. A l’etape k, on suppose quel’on connaıt un polyedre convexe Q(k) tel que :

Q(k) ⊆ F = x | g(x) 6 0 .

I On resout le programme lineaire :

min f (x),

x ∈ Q(k).

Soit x (k) le point obtenu.

I Si x (k) ∈ F , c’est le minimum cherche. Sinon, il existe i telque gi (x

(k)) > 0. On forme :

Q(k+1) = Q(k)⋂

x∣∣∣ gi (x

(k)) +∇gi (x(k))T .(x − x (k)) 6 0

,

et on recommence.

Methode des plans secants III / VII

LemmeSi f est convexe, alors f (x) > f (a) +∇f (a)T .(x − a).

Demonstration.Pour simplifier on va supposer que x est un scalaire. Soit parexemple b > a. Par definition, f (x)− f (a) 6 (x − a) f (b)−f (a)

b−a . En

faisant tendre x vers a on en deduit f ′(a) 6 f (b)−f (a)b−a , ce qui n’est

autre que le resultat cherche. La demonstration est analogue pourb < a.

Methode des plans secants IV / VII

LemmeQ(k+1) ⊆ F .

Demonstration.Soit en effet x un point de F . Puisque gi est convexe, on agi (x) > gi (x

(k)) +∇gi (x(k))T .(x − x (k)). Or gi (x) 6 0, donc

x ∈ Q(k+1).

Lemmex (k) 6∈ Q(k′), k ′ > k

Demonstration.Il suffit d’observer que x (k) ne satisfait pas la contraintegi (x

(k)) +∇gi (x(k))T .(x − x (k)) 6 0.

Methode des plans secants V / VII

LemmeSi x (k) ∈ F , c’est le minimum cherche.

Demonstration.En effet, d’une part x (k) ∈ F , et d’autre part,

x ∈ F ⇒ x ∈ Q(k) ⇒ f (x) > f (x (k)).

Methode des plans secants VI / VII

TheoremeSi F est borne, tout point d’accumulation de la suite x (k) est unoptimum.

Demonstration.Soit y∗ un point d’accumulation, et soit y (k) une suite extraite dex∗ et convergeant vers y∗. Montrons d’abord que y∗ ∈ F . Onsupposera pour fixer les idees que a chaque pas, la contrainteutilisee pour construire une coupe est celle qui est la moinssatisfaite, c’est a dire celle pour laquelle gi (x

(k)) > 0 estmaximum. Supposons que y∗ ne soit pas dans F , et soit gi lacontrainte la moins satisfaite. Puisque y (k) converge vers y il existeun k∗ suffisamment grand pour que gi soit la contrainte la moinssatisfaite en y (k). On ajoute la contrainte :

gi (y(k)) +∇gi (y

(k))T .(x − y (k)) 6 0.

Methode des plans secants VII / VII

Demonstration.Il est facile de voir que la distance ||y [k′) − y (k)||, k ′ > k ne peut

etre inferieure a |gi (y[k)|

|∇gi (y [k)| , ce qui contredit le fait que y∗ est limite

des y (k).Supposons maintenant qu’il existe dans F un autre point y ′ tel quef (y ′) < f (y∗). Comme y ′ ∈ Q(k)∀k, il s’en suit que l’algorithme deprogrammation lineaire devrait toujours construire un point x (k) telque f (x (k)) 6 f (y ′). Par suite de la continuite de f , toute limite x∗

de la suite x (k) doit etre telle que f (x∗) 6 f (y ′) ce qui estcontradictoire.

Plan

Kuhn-Tucker

Une methode directe

Methodes duales

Fonction de Lagrange, point-col

Optimisation combinatoirecoque entiereAlgorithme de GomoryTechniques de codage

Methodes de penalites

I Principe : au lieu d’exclure les points qui violent les contraintes,ajouter a la fonction economique une penalite d’autant plus eleveeque la contrainte est moins respectee. Si la fonction de penalite estreguliere, on peut utiliser les methodes d’optimisation sanscontrainte.

I En general, la penalite depend d’un parametre qui permet de reglerson importance. Quand la penalite devient tres grande devant lafonction objectif, on tend vers l’optimum sous contrainte. Mais lafonction a optimiser devient de plus en plus mal conditionnee.

I Deux varietes :

I La fonction de penalite est nulle dans le domaine faisable.L’optimum penalise n’est pas faisable. C’est une methodeexterieure.

I La fonction de penalite devient infinie quand on sort dudomaine faisable. L’optimum est faisable, mais la methode abesoin d’un point faisable initial.

Methodes exterieures

I On considere la fonction h(x) egale a 0 si x 6 0 et a x2 sinon.Il est facile de voir qu’elle est continue et a derive continue.

I On remplace le probleme :

P : min f (x),

gi (x) 6 0, i = 1, . . . , n

x ∈ Rn

par la suite de problemes :

Pk : min f (x) + Sk

n∑i=1

h(gi (x)).

ou les Sk forment une suite croissante tendant vers l’infini.

I On note H(x) =∑n

i=1 h(gi (x)) et xk la solution de Pk .

Convergence I / III

TheoremeSi f est continue, si l’ensemble des points faisables est ferme et sisoit f (x) soit H(x) tend vers l’infini quand x tend vers l’infini, alorstout point d’accumulation de la suite xk est une solution de P.

On note ϕk = f (xk) + SkH(xk), et x∗ une solution de P.

LemmeLes ϕk forment une suite decroissante.

Demonstration.On a f (xk+1) + Sk+1H(xk+1) > f (xk+1) + SkH(xk+1) parce queSk+1 > Sk et f (xk+1) + SkH(xk+1) > f (xk) + SkH(xk) puisque xk

est la solution de Pk .De plus, ϕk 6 f (x∗) + SkH(x∗). Mais comme x∗ est faisable, lapenalite est nulle. On a donc l’encadrement

f (xk) 6 ϕk 6 f (x∗).

Convergence II / III

LemmeLes H(xk) forment une suite decroissante.

Demonstration.Comme chaque xk est la solution d’un probleme de minimum, ona :

f (xk) + SkH(xk) 6 f (xk+1) + SkH(xk+1),

f (xk+1) + Sk+1 6 f (xk) + Sk+1H(xk).

En additionnant et simplifiant :

(Sk − Sk+1)(H(xk+1)− H(xk)) > 0.

Comme le premier terme est negatif, l’autre l’est aussi.

Convergence III / III

I Les xk appartiennent a un ensemble borne, soit parce quef (xk) 6 f (x∗) et que f tend vers l’infini a l’infini, soit parceque H(xk) 6 H(1) et que H tend vers l’infini a l’infini. Onpeut donc extraire de xk une sous-suite x`, ` ∈ L qui convergevers x .

I Par continuite, f (x`) tend vers f (x), et comme f (xk) 6 f (x∗),f (x) 6 f (x).

I Comme ϕk 6 f (x∗), ϕk a une limite phi∗ 6 f (x∗).

I lim S`H(x`) = ϕ∗ − f (x). Donc H(x`) tend vers 0, et parcontinuite H(x) = 0.

I Donc x est un point faisable, donc f (x) > f (x∗), doncf (x) = f (x∗) et x est un optimum.

Methodes interieures

I On prend comme fonction de penalite une fonction qui tendvers l’infini au voisinage de 0, par exemple h(x) = −1/x .

I On minimise f (x) + R∑n

i=1 h(gi (x)).

I Dans les memes conditions que ci-dessus, on montre quel’optimum du probleme PR tend vers l’optimum de P quandR tend vers 0.

I Toutes les solutions intermediaires sont faisables, mais il fautdisposer d’un point faisable pour commencer les calculs.

Exemple

I Le probleme du cas le pire de Fourier-Motzkin:

max xy + z ,

x + y + z = n

I On elimine z a l’aide de la derniere contrainte et on appliquela methode des penalites :

max xy + n − x − y + S(n − x − y)2.

I On utilise un systeme de calcul algebrique pour achever lescalculs.

Plan

Kuhn-Tucker

Une methode directe

Methodes duales

Fonction de Lagrange, point-col

Optimisation combinatoirecoque entiereAlgorithme de GomoryTechniques de codage

Fonction de Lagrange, point-col

I Soit a resoudre :

min f (x),

gi (x) 6 0, i = 1, . . . , n

x ∈ S ⊆ Rn

I La fonction de Lagrange associee est :

L(x , λ) = f (x) + λ.g(x), λ > 0.

I g est le vecteur dont les composantes sont les gi .

Point-col

I (x∗, λ∗) est un point-col si et seulement si :

x∗ ∈ S , λ∗ > 0.

∀x ∈ S : L(x∗, λ∗) 6 L(x , λ∗),

∀λ > 0 : L(x∗, λ∗) > L(x∗, λ).

I Caracterisation d’un point-col :

L(x∗, λ∗) = minx∈S

L(x , λ∗),

g(x∗) 6 0,

λ∗.g(x∗) = 0.

Preuve

Soit (x∗, λ∗) un point-col. La premiere propriete est uneconsequence directe de la definition.La deuxieme propriete entraıne :

f (x∗) + λ∗.g(x∗) > f (x∗) + λ.g(x∗),

(λ− λ∗).g(x∗) 6 0.

S’il existait un gi (x∗) positif, il suffirait de prendre le λi

correspondant suffisamment grand pour violer cette inegalite. Donc∀i : gi (x

∗) 6 0.Pour λ = 0 on trouve :

−λ∗.g(x∗) 6 0.

Mais les deux termes du produit sont non negatifs, donc le produitest nul.

Preuve, reciproque

La premiere caracteristique entraıne directement la premierepropriete du point-col.On deduit de la troisieme caracteristique que L(x∗, λ∗) = f (x∗).Enfin :

L(x∗, λ) = f (x∗) + λ.g(x∗) 6 f (x∗) = L(x∗, λ∗),

puisque g(x∗) 6 0.

Interet

TheoremeSi (x∗, λ∗) est un point-col, alors x∗ est un minimum global.

Demonstration.D’apres la definition, x∗ ∈ S et g(x∗) 6 0, donc x∗ est faisable.D’autre part :

∀x ∈ S , g(x) > 0 : f (x∗) = L(x∗, λ∗) 6 L(x , λ∗) = f (x)+λ∗g(x) 6 f (x).

puisque λ∗ > 0 et g(x) 6 0.x∗ est donc bien minimum global.

Mais il existe des problemes qui n’ont pas de point-col.

Fonction de Lagrange et penalites

I La fonction de Lagrange est une fonction de penalite.

L(x , λ) = f (x) + λ.g(x), λ > 0.

I En effet, dans la region infaisable, g(x) > 0, donc le secondterme augmente la valeur de L, alors qu’on recherche unminimum.

I Toutefois, ce terme est negatif dans la region faisable, ce quidiminuerai artificiellement la valeur du minimum, si l’onn’avait pas la contrainte ∀i : λi .gi (x

∗) = 0.

I Comme les methodes de penalite, l’emploi de la fonction deLagrange permet de remplacer un probleme avec contraintespar un probleme sans contrainte.

Une mauvaise idee

I Maximiser L(x , λ) par rapport a λ > 0 pour x fixe. Soit g(x)le resultat. Minimiser ensuite g(x) sans contraintes.

I Il est facile de trouver le maximum.I Si gi (x) > 0, il suffit de faire tendre λi →∞ pour obtenir un

maximum infini.I Sinon, le maximum est egal a f (x).

I Ceci revient donc a etendre f en une fonction discontinue nonderivable, ce qui ne se prete pas a l’optimisation.

Une bonne idee

I Minimiser w(λ) = min L(x , λ) sans contrainte. Maximiserw(λ) sous la contrainte λ > 0.

Lemmew(λ) est une fonction concave.

Demonstration.Soit λ1, λ2 deux valeurs de λ, α et β deux nombres positifs telsque α + β = 1, et x un point arbitraire. Par definition des minima :

f (x) + λ1g(x) > w(λ1),

f (x) + λ2g(x) > w(λ2),

f (x) + (αλ1 + βλ2)g(x) > αw(λ1) + βw(λ2).

et cette propriete vraie partout s’etend au minimumw(αλ1 + βλ2).

Application a la programmation lineaire

I Il ne faut pas croire que l’optimisation de w est toujours sanscontrainte. Soit par exemple le programme lineaire :

min c.x ,

Ax − b > 0,

x > 0.

I La fonction de Lagrange associee est :

L(x , λ) = c.x − λ(Ax − b)− µx = (c − λA− µ).x + λb.

I Il est facile de voir que si c − λA− µ n’est pas nul, la valeur duminimum est −∞. Sinon, c’est λb. Comme c − λA− µ = 0 estequivalent a c − λA > 0, on voit que l’on est amene a resoudre :

max λ.b,

c − λA > 0,

λ > 0.

C’est le dual du probleme original!

Et s’il n’y a pas de point col ?

TheoremeSoit x∗ la solution du probleme avec contraintes. On a :maxλ>0 w(λ) 6 f (x∗).

Demonstration.Comme x∗ est faisable, g(x∗) 6 0. Donc

L(x∗, λ) = f (x∗) + λg(x∗) 6 f (x∗),

w(λ) = minx

L(x , λ) 6 L(x∗, λ) 6 f (x∗).

Cette propriete vraie pour tout λ s’etend au maximum.

I La solution du probleme dual fournit une borne inferieure de lasolution du primal.

I Il y a «saut de dualite» quand les deux solutions ne sont pasegales.

I w est derivable a l’optimum, si et seulement si le saut dedualite est nul.

Generation de colonnes I / III

I Si l’ensemble S = x1, . . . , xn est fini, le probleme s’ecrit :

maxλ>0

nmini=1

f (xi ) + λg(xi )

se ramene a un probleme de programmation lineaire :

P(n) : max z

z 6 f (xi ) + λg(xi ), i = 1, . . . , n

λ > 0.

I Soit xn, λn la solution de P(n).

Generation de colonnes II / III

I Si S est infini, on suppose que l’on a deja construit les pointsx1, . . . , xn.

I On resout le probleme lineaire ci-dessus.

I On determine le point xn+1 comme solution de :

minx∈S

L(x , λn) = f (x) + λng(x)

par une methode d’optimisation sans contraintes.

I Soit w(λn) le minimum obtenu.

I On recommence avec n + 1 points, jusqu’a convergence.

Generation de colonnes III / III

LemmeSoit x∗ la solution du probleme avec contrainte: w(λn) 6 f (x∗).

Demonstration.Puisque x∗ ∈ S , w(λn) 6 f (x∗) + λg(x∗) 6 f (x∗) puisque que x∗

est faisable.

Lemmef (x∗) 6 zn.

Demonstration.Il est evident que 〈f (x∗), λn〉 est un point faisable pour P(n).

Lemmezn+1 6 zn.

Demonstration.Tout point faisable pour P(n + 1) est faisable pour P(n).

Convergence

I On a l’encadrement w(λn) 6 f (x∗) 6 zn.

I Comme la suite zn est decroissante, elle converge.

I Mais la convergence de w(λn) vers f (x∗) impliquerait que lesaut de dualite est nul, ce qui n’est pas toujours le cas.

Plan

Kuhn-Tucker

Une methode directe

Methodes duales

Fonction de Lagrange, point-col

Optimisation combinatoirecoque entiereAlgorithme de GomoryTechniques de codage

Optimisation combinatoire

I Probleme d’optimisation sous contraintes ou l’ensemble despoints faisables est non pas continu mais discret.

I Forme du probleme :

min f (x)

x ∈ S

I Les inconnues sont les n composantes du vecteur x . S estl’ensemble discret des points faisables.

I En general, S est produit cartesien d’ensembles plus petits, etsa taille est le produit des tailles de ces petits ensembles (d’oule nom : optimisation combinatoire).

I Chaque composant de S correspond a un choix ; il fauttrouver la bonne suite de choix, sachant que ceux-ci ne sontpas independants en general.

Exemple I / II

I On considere un ordinateur sur lequel on doit executer talgorithmes enchaınes Ai , i = 1, . . . , t. Chaque algorithme apour donnees les resultats de l’algorithme precedent.

I Pour implementer chaque algorithme, on doit choisir unestructure pour ses donnees. On suppose qu’il y a s structurespossibles, Sk , k = 1, . . . , s et que le temps d’execution del’algorithme depend de la structure choisie. Par exemple, unematrice peut etre rangee par ligne ou par colonne, et, parsuite des effets de cache, le temps d’execution du produitmatriciel varie suivant la structure choisie. On supposeraqu’un algorithme ne modifie pas la structure des ses donnees.On note Tik le temps d’execution de l’algorithme i quand lesdonnees on la structure Sk .

Exemple II / II

I On suppose qu’il est possible de modifier les structure dedonnees (par exemple, de transposer une matrice). On noteθk` le temps necessaire pour passer de la structure Sk a lastructure S`. Remarquer que θkk = 0.

I La structure du programme est alors :

Sk0R0Sk1A1Sk1 . . .AtSktRtSkt+1

I On suppose que k0 et kt+1 sont fixes par le cahier des charges.

I Trouver la sequence de restructurations donnant le tempstotal minimum.

Quelques methodes de solution I / III

I Une heuristique gloutonne.

I On remarque que souvent θkl Tik . Pour l’exemple matriciel,le temps de transposition est O(n2) alors que le temps duproduit est O(n3).

I On choisit donc Skjde facon que Tikj

soit minimum, et onrajoute des redistributions si necessaire.

Quelques methodes de solution II / III

I Programmation dynamique. On remarque que le probleme aune structure analogue a celle d’un probleme de plus courtchemin.

I On note Pn(k) le probleme d’optimiser le programmeanalogue au programme initial, mais ou on s’arrete juste apresla redistribution Rn avec une structure de donnees Sk . Leprobleme initial est Pt(kt+1). Soit Ωn(k) le meilleur tempsd’execution de Pn(k). On a la relation de recurrence :

Ωn(k) = min`

Ωn−1(`) + Tn` + θ`k ,

Ω0(k) = θk0k .

I On peut calculer toutes les valeurs de Ωnk a l’aide de cetterecurrence, lire la valeur de Ωt(kt+1) et reconstituer le chemina suivre par retour arriere.

Quelques methodes de solution III / III

I Codage en variables 0-1. On pose Xik = 1 si la distributiondes donnees a l’etape i est la distribution Sk , et 0 sinon.

I A chaque etape, il y a une et une seule distribution :s∑

k=1

Xik = 1. (1)

I Le temps de calcul total est : Tc =∑t

i=1

∑sk=1 TikXik .

I Le temps de redistribution de l’etape i a i + 1 est donne parθk` tel que Xik = 1 et X(i+1)` = 1, ce qui peut s’ecrire :

Tr =t∑

i=0

s∑k=1

s∑`=1

XikX(i+1)`θk`.

I Il s’agit de minimiser la somme Tc + Tr sous les contraintes(1) et Xik ∈ 0, 1. C’est un probleme de programmationquadratique en nombres entiers.

Programmation lineaire en entiers

I Definition.

min x ,

Ax + b > 0,

x ∈ N.

I Noter que x ∈ N implique x > 0. Il s’agit donc de l’analogueexact du probleme resolu par l’algorithme dual, a ceci presqu’il y a une contrainte d’integrite en plus.

I On suppose en general que A et b ont des coefficients entiers.

Plan

Kuhn-Tucker

Une methode directe

Methodes duales

Fonction de Lagrange, point-col

Optimisation combinatoirecoque entiereAlgorithme de GomoryTechniques de codage

Coque entiere I / II

I Soit S un ensemble de Rn. La coque entiere de S , notee S estla coque convexe de l’ensemble des points entiers de S .

x ∈ Zn ∩ S ⇒ x ∈ S ,

x , y ∈ S , λ, µ > 0, λ + µ = 1 ⇒ λx + µy ∈ S .

Proprietes de la coque entiere

LemmeSi A est convexe, A ⊆ A.

LemmeA ⊆ B ⇒ A ⊆ B.

LemmeSi Zn ∩ P ⊆ S convexe, alors P ⊆ S.

Demonstration.Un point de P est combinaison convexe d’un certains nombres depoints de Zn ∩ P, qui appartiennent par hypothese a S . Or Scontient toutes les combinaisons convexes de ses points.

Caracterisation de la solution entiere

TheoremeLa coque entiere d’un polyedre defini par Ax + b > 0, avec Aentiere, est un polyedre.

Demonstration.Soit P = Q + C un polyedre, ou Q est borne et C un cone. Onpeut supposer que les vecteurs generateurs vi de C sont entiers, etil est facile de voir que C = C .Soit B =

∑i µivi | 0 6 µi 6 1. Il est clair que B est un

polyedre borne inclus dans C . Admettons que P = Q + B + C (cesera montre par les deux lemmes suivants). Or Q + B est borne, etpour un polyedre borne le theoreme est evident, puisque la conqueentiere est enveloppe convexe de ses points entiers qui sont ennombre fini.

Coque entiere II / II

LemmeP ⊆ Q + B + C.

Demonstration.D’apres un lemme ci-dessus, il suffit de considerer un point x entierde P. On peut l’ecrire x = q + c, q ∈ Q, c ∈ C . Il en resultec =

∑i µivi . On pose c ′ =

∑i bµic vi et b = c − c ′. Il est clair que

b ∈ B, donc que q + b ∈ Q + B, que c ′ ∈ C est entier, et queq + b = x − c ′ est entier, donc que q + b ∈ Q + B.

LemmeQ + B + C ⊆ P.

Demonstration.Puisque Q + B ⊆ P,Q + B + C ⊆ P + C = P + C = P + C = P.

Minimum entier

LemmeLe minimum entier d’un polyedre est le minimum rationnel de sacoque entiere.

Demonstration.Le minimum entier x∗ appartient a la coque entiere. Supposonsqu’il existe dans la coque entiere un point x ′ x∗. Ce point estnecessairement a coordonnees non entieres (puisque la coqueentiere est contenue dans le polyedre). x ′ est donc combinaisonconvexe de points entiers qui lui sont tous superieurs dans l’ordrelexicographique, ce qui est impossible.

I Le probleme sera resolu si on sait construire la coque entiere.I Mais la complexite de la coque entiere peut etre enorme.I Heureusement, on peut se contenter de construire quelques

coupes (et non toute la coque) : des contraintes affines quiexcluent une partie de P mais aucun point de P.

Plan

Kuhn-Tucker

Une methode directe

Methodes duales

Fonction de Lagrange, point-col

Optimisation combinatoirecoque entiereAlgorithme de GomoryTechniques de codage

Coupe de Gomory

I Construction d’une coupe : soit

a/D.x + b/D > 0

une des contraintes du probleme. D est le denominateurcommun des coefficients de x et du terme constant.

I Par construction de l’algorithme dual, la valeur de cettecontrainte est l’une des variables d’ecart du probleme initial,qui doit etre entiere. Comme les x sont entiers :

ax + b mod D = 0,

(a mod D)x ≡ (−b mod D)(modD),

(a mod D)x = (−b mod D) + kD,

I k est necessairement positif, d’ou :

(a mod D)x − (−b mod D) > 0.

Algorithme de Gomory

I On a mis le probleme sous la forme :min x

y = Sz + t > 0z > 0

ou la matrice S et le vecteur t sont entiers, ainsi que lesvariables y et z . z est un extrait de y , et les n premierescomposantes de y sont les variables originales.

I On procede comme dans l’algorithme du Simplexe jusqu’aobtenir t > 0. Si l’algorithme echoue, il n’y a pas de solutionentiere.

I Si les composantes 1 a n de t sont entieres, c’est la solution.I Sinon, on choisit le premier ti non entier, on construit une

coupe comme ci-dessus a l’aide de la contrainte Siz + ti > 0,et on l’ajoute au tableau.

I Le nouveau tableau n’est pas faisable : le terme constant de lacoupe est negatif. On reprend l’algorithme jusqu’a terminaison.

Preuve I / VI

TheoremeSi l’algorithme se termine, ou bien on a trouve la solution entiere,ou bien le probleme n’a pas de solution.

Demonstration.Soit Pn le polyedre obtenu apres la ne coupe. Par construction,tous les points entiers de P = P0 sont dans Pn. Si donc Pn estvide, P ne contient aucun point entier. Sinon, soit x∗ le minimumlexicographique de Pn, et supposons qu’il est entier. Si P contenaitun point entier plus petit, il serait dans Pn ce qui serait unecontradiction.

Preuve II / VI

LemmeOn peut toujours supposer qu’il existe une solution.

Demonstration.On considere le probleme etendu

min u, x

u + Ax + b > 0,

u > 0,

x > 0

Il est clair que ce probleme a toujours une solution : il suffit deprendre x nul et u tres grand. Si le probleme initial a un minimumx∗, alors 0, x∗ est le minimum du probleme etendu. Inversement, sile probleme initial n’a pas de solution, alors u ne peut etre nul dansla solution du probleme etendu. Les deux problemes sont doncequivalents.

Preuve III / VI

LemmeLes minima successifs xn forment une suite croissante dans l’ordrelexicographique.

Demonstration.Evident, puisque Pn+1 ⊆ Pn.

I A une certaine etape de l’algorithme, soit∑

jsjD xj + t

D > 0 laligne qui va fournir la coupe.

I A l’etape qui suit, l’algorithme du Simplexe execute un pivot.Soit xj la variable eliminee.

I Soit :∑

j

s′j

D xj + t′

D > 0 la ligne apres l’execution du pivot.

Preuve IV / VI

LemmeIl existe un nombre entier Q tel que t

D < Q 6 t′

D .

Demonstration.La coupe est :

∑j

sj mod DD xj − −t mod D

D > 0Les formules de changement de base donnent:

t ′

D=

t

D+

sjD

−t mod D

D

D

sj mod D6

t

D+−t mod D

D.

Soit q le quotient entier par defaut de t par D : t = qD + t mod D.

t ′

D> q +

t mod D + (−t mod D)

D.

Le deuxieme terme est egal a 1, il suffit donc de prendre Q = q +1.D’autre part t/D = (q + 1)− (D − t mod D)/D < q + 1.L’inegalite est stricte puisque t n’est pas entier.

Preuve V / VI

I A un instant donne du deroulement de l’algorithme, on ditqu’une ligne est active si lors d’une operation ulterieure, lavaleur de son second membre changera.

LemmeLa premiere ligne ne peut etre active qu’un nombre fini de fois.

Demonstration.Soit τ1 = dt1e. On a l’encadrement τ1 − 1 < t1 6 τ1. Consideronsl’evolution de τ1 apres une coupe.Si la source de la coupe est la ligne 1, apres le changement de basequi suit, τ1 augmente au moins d’une unite. Si la source est uneautre ligne, c’est que t1 est entier. Une autre ligne est source de lacoupe, et si la premiere ligne est active, c’est que S1j est non nul.La valeur de t1 augmente. Qu’elle prenne une valeur entiere oufractionnaire, la valeur de τ1 augmente au moins d’une unite.Or t1 donc τ1 sont bornes par la solution optimale x∗1 .

Preuve VI / VI

TheoremeL’algorithme des coupes de Gomory converge.

Demonstration.Nous avons vu que la premiere ligne ne peut etre active qu’unnombre fini de fois. Apres la derniere modification, tout se passecomme si le probleme a resoudre avait une contrainte et uneinconnue de moins (methode de deflation). On peut donc prouverque la deuxieme ligne n’est active qu’un nombre fini de fois. Deproche en proche, on voit que l’algorithme se termine.

Complexite

I Comme il faut pouvoir distinguer entre nombres entiers etnombres fractionnaires, les calculs doivent etre menes enarithmetique exacte.

I Les nombres a manipuler sont des determinants desous-matrices n × n de la matrice des contraintes. Leur taille(nombre de bits) est donc bornee par n fois le nombre de bitsdu plus grand coefficient.

I Le nombre maximum de coupes est borne par le nombre decoupes necessaires pour caracteriser la coque entiere del’ensemble des solutions. Resultat de Chvatal.

Plan

Kuhn-Tucker

Une methode directe

Methodes duales

Fonction de Lagrange, point-col

Optimisation combinatoirecoque entiereAlgorithme de GomoryTechniques de codage

Variables booleennes

I On peut coder un choix entre n possibilites a l’aide de nvariables 0-1, X1, . . . ,Xn.

I Chaque variable entiere ne peut prendre que les valeurs 0 ou1 : 0 6 x 6 1.

I Les choix sont exclusifs :∑n

i=1 Xi = 1.

I Si a chaque choix est associe une quantite ai , la quantiteassociee a un jeu de variables est

∑ni=1 Xi ti .

I On peut considerer les Xi comme des booleens et coder lesoperateurs :

Z ≡ X ∨ Y :: Z > X ,Z > Y ,Z 6 X + Y ,

Z ≡ X ∧ Y :: Z 6 X ,Z 6 Y ,Z > X + Y − 1,

Z ≡ ¬X :: Z = 1− X .

Problemes de graphe

I On peut representer un graphe de nombreuses facons :matrice d’incidence, matrice de connexion, Zij = 1 si etseulement si il existe un arc i → j .

I Chemin : Xij = 1 si et seulement si le chemin emprunte l’arci → j . Contrainte : Xij 6 Zij .

I Loi de Kirchoff :∑

i Xij =∑

k Xjk , pour tout j excepte ledebut et la fin du chemin.

I Chemin simple : ne passe qu’une fois par chaque sommet.∑i Xij 6 1.

I Pour le debut,∑

j Xij = 1, et pour la fin∑

i Xij = 1.

I Minimiser la somme∑

ij Xij assure que le chemin n’a pas deboucles isolees.

Techniques de grands nombres

I Soit P = x | Ax + b > 0 et Q = x | Cx + d > 0 deuxpolyedres dont on doit explorer les points entiers. Soit z unenouvelle variable 0-1.

I Si P et Q sont bornes, alors pour M suffisamment grand, lepolyedre :

P ⊕ Q = z , x | Ax + b + Mz > 0,Cx + d + M(1− z) > 0

est l’union disjointe de P et Q.

I On peut mener l’exploration sur P ⊕ Q en une seule fois.

I M doit etre choisi de telle facon que x ∈ P entraıneCx + d + M > 0 et reciproquement.