Recherche opérationnelle

Recherche Op´erationnelle Paul Feautrier 20 mai 2004

2

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

Table des mati` eres 1 Optimisation sans contraintes 1.1 Principaux concepts . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Optimisation continue sans contrainte . . . . . . . . . . . . . . . 1.3 Programmation lin´eaire . . . . . . . . . . . . . . . . . . . . . . .

5 5 10 15

2 Optimisation sous contraintes 2.1 Conditions de Kuhn et Tucker . 2.2 Une m´ethode directe . . . . . . 2.3 M´ethodes duales . . . . . . . . 2.4 Fonction de Lagrange, point-col 2.5 Optimisation combinatoire . . . 2.5.1 coque enti`ere . . . . . . 2.5.2 Algorithme de Gomory 2.5.3 Techniques de codage .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

27 27 29 30 32 36 38 39 41

3 M´ eta-heuristiques 3.1 S´eparation et ´evaluation ou Branch-and-Bound 3.1.1 Algorithme . . . . . . . . . . . . . . . . ´ 3.1.2 Evaluation . . . . . . . . . . . . . . . . 3.1.3 Strat´egie et Tactiques . . . . . . . . . . 3.2 Programmation Dynamique . . . . . . . . . . . 3.3 Exploration al´eatoire . . . . . . . . . . . . . . . 3.3.1 Am´elioration it´erative . . . . . . . . . . 3.3.2 Recuit simul´e . . . . . . . . . . . . . . . 3.3.3 La m´ethode Tabou . . . . . . . . . . . . 3.3.4 Algorithmes g´en´etiques . . . . . . . . . 3.4 Conclusion g´en´erale . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

43 43 43 45 46 48 53 53 54 57 58 59

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

4

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

Table des mati` eres

Chapitre 1

Optimisation sans contraintes Plan – Introduction et principaux concepts – Optimisation continue sans contrainte – Programmation lin´eaire – Optimisation continue sous contrainte – Optimisation combinatoire – Programmation lin´eaire en nombres entiers. – Exploration – M´etaheuristiques – Programmation dynamique ´ ements de Complexit´e – El´

1.1

Principaux concepts

Qu’est ce que la recherche op´ erationnelle ? – Vocabulaire : Recherche op´erationnelle = programmation math´ematique = optimisation (mais pas optimisation de programme). – Recherche op´erationnelle = mod´elisation math´ematique des processus de prise de d´ecision. – Inconnues : les variables de d´ecision. ´ – Evaluation de la d´ecision = fonction ´economique ou fonction «objectif». – Trouver les valeurs des variables de d´ecision qui minimisent (ou maximisent) la fonction objectif. Recherche op´ erationnelle

modélisation

optimisation

action

6

Optimisation sans contraintes – La mod´elisation est un art, l’optimisation est une science. – Applications : planification du d´ebarquement de Normandie, optimisation d’un programme de calcul intensif, investissement en bourse. – Investissement en bourse = optimisation avec information incompl`ete ou al´eatoire. – Planification d’une op´eration militaire = il y a un adversaire = th´eorie des jeux. – Optimisation d’un programme = en principe, on a une information compl`ete. – Le cours est essentiellement consacr´e `a l’optimisation avec information compl`ete.

Informatique ou math´ ematique ? Mathématique

Théorèmes d’existence Convergence

Informatique

Intelligence Artificielle

Recherche Opérationelle

Complexité

Vocabulaire

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

Algorithmes Preuves de terminaison

1.1 Principaux concepts

7

Forme canonique : trouver x ∈ D qui minimise f .

x

courbes de niveau de la fonction objectif optimum

min f (x) ∈ D

contraintes

Optimum local, global – Minimum local : a est un minimum local de f s’il existe un voisinage V de a tel que : x ∈ V ⇒ f (x) > f (a). – Minimum global : a est un minimum global de f dans D si et seulement si : x ∈ D ⇒ f (x) > f (a).

local global

Convexit´ e Un ensemble S est convexe si, pour toute paire de points a, b de S, S contient aussi le segment ab. a, b ∈ S ⇒ (0 6 λ 6 1 ⇒ λa + (1 − λ)b ∈ S.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

8

Optimisation sans contraintes

convexe

convexe

convexe

non convexe

Fonction convexe – f est convexe dans un ensemble convexe S si et seulement si : x, y ∈ S, 0 6 λ 6 1 ⇒ f (λx + (1 − λ)y) 6 λf (x) + (1 − λ)f (y)

f y x

S Int´ erˆ et de la convexit´ e Th´ eor` eme 1.1. Si f est convexe dans un ensemble convexe S, alors tout minimum local de f est un minimum global. D´emonstration. Soit a un minimum local, et V l’ouvert contenant a dans lequel : x ∈ V ⇒ f (x) > f (a). Si on suppose qu’il existe un point b ∈ S tel que f (b) < f (a) alors on a : f (λa + (1 − λ)b) 6 λf (a) + (1 − λ)f (b). Il est possible de trouver un λ suffisamment proche de 1 pour que x = λa + (1 − λ)b soit dans V . Contradiction en ce point : f (x) 6 λf (a) + (1 − λ)f (b) 6 f (a),  Classification – Selon la nature des variables de d´ecision : – Optimisation continue. – Optimisation discr`ete ou optimisation combinatoire. – Selon la nature des contraintes : – Pas de contraintes ou contraintes faciles `a satisfaire (un segment de la droite r´eelle) : optimisation sans contraintes. – Optimisation sous contraintes : il est difficile de trouver un point satisfaisant les contraintes. – Propri´et´es sp´eciales des ´el´ements du probl`eme : lin´earit´e, convexit´e.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

1.1 Principaux concepts

9

Optimisation multicrit` ere – Forme canonique : trouver x ∈ D qui minimise f1 , f2 , . . . min f1 (x) min f2 (x) ... x ∈ D – Le probl`eme est ´evidemment mal pos´e. Quel sens peut on lui donner ? – Exemple : on doit concevoir un ´equipement ´electronique qui doit ex´ecuter un algorithme donn´e le plus vite possible et pour le moindre prix. – f1 est le temps d’ex´ecution de l’algorithme. – f2 est le prix de l’´equipement. Domination – On se place dans le cas n = 2. – La solution x domine la solution y si et seulement si f1 (x) 6 f1 (y), f2 (x) 6 f2 (y). – La relation de domination est un ordre partiel. On ne peut donc pas prouver l’unicit´e d’un minimum s’il existe. – L’optimum de Pareto (ou le Pareto) du probl`eme est l’ensemble des solutions non domin´ees. Pareto prix

domination

latence

Que faire avec un Pareto ? Pond´ eration On attribue un poids ` a chaque objectif et on minimise l’objectif pond´er´e. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

10

Optimisation sans contraintes

prix

optimum pondéré

latence Transformation objectif/contrainte On fixe la valeur de l’une des fonctions objectif et on optimise l’autre. Par exemple, le marketing d´ecide du prix maximum de l’´equipement.

prix

borne du prix optimum

latence

1.2

Optimisation continue sans contrainte

Optimisation continue sans contrainte On consid`ere une seule variable min f (x) x ∈ R – Si on connaˆıt la d´eriv´ee f 0 de f , le probl`eme se ram`ene `a trouver les racines de f 0 , puis ` a les tester une par une pour savoir si elles sont un minimum, un maximum ou un point d’inflexion. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

1.2 Optimisation continue sans contrainte

11

– On peut utiliser pour cela des m´ethodes classiques : it´eration de Newton (si on peut calculer la d´eriv´ee seconde), dichotomie, m´ethode de la s´ecante. – Si on ne connaˆıt pas la d´eriv´ee, la premi`ere chose `a faire est de trouver un encadrement du minimum. Il n’y a pas de m´ethode g´en´erale, on utilise les renseignements que l’on peut avoir sur f . Fonctions unimodales – Une fonction f est unimodale dans l’intervalle [a, b] s’il existe un point a 6 c 6 b tel que si x 6 y 6 c alors f (x) > f (y) et si c 6 x 6 y alors f (x) 6 f (y). – Il est ´evident que si f est unimodale dans [a, b], alors c est un minimum global. Th´ eor` eme 1.2. Si f est continue convexe dans [a, b], alors f est unimodale. D´emonstration. Soit c le minimum de f , et x et y qui violent la condition d’unimodalit´e, par exemple c 6 x 6 y et f (c) < f (y) < f (x). Soit 0 6 λ 6 1 tel que x = λc + (1 − λ)y. Par convexit´e on doit avoir f (x) 6 λf (c) + (1 − λ)f (y) mais aussi λf (c) + (1 − λ)f (y) 6 f (y) < f (x) une contradiction.  M´ ethode par trichotomie

a

c

d

b

a

c

d

b

– On divise l’intervalle [a, b] en trois parties ´egales `a l’aide des points a < c < d < b. On calcule f (c) et f (d). – On d´etermine le minimum de f parmi les 4 points a, c, b, d. – Le minimum continu appartient `a l’intervalle encadrant le minimum discret. – L’intervalle est r´eduit au moins par un facteur 2/3. On poursuit jusqu’`a la pr´ecision voulue. Am´ eliorations n/2 – Vitesse de convergence : la taille de l’intervalle est multipli´ee par 23 apr`es n ´evaluations de la fonction. – La division en segment ´egaux n’est pas optimale. On a int´erˆet `a agrandir les segments extrˆemes. – On peut passer ` a un d´ecoupage en 4 parties ´egales. Il faut ´evaluer f trois fois ` a chaque ´etape, mais l’intervalle est au moins divis´e par 2. La convern/3 gence est en 12 donc plus rapide. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

12

Optimisation sans contraintes

M´ ethodes par exploration – Il est toujours indispensable de connaˆıtre une encadrement [a, b] du minimum. – On suppose toujours que f est unimodale. On choisit un pas d’exploration d. On calcule f aux points xk = a + k.d jusqu’`a trouver soit une configuration f (xk ) 6 f (xk+1 ), soit jusqu’`a atteindre le point b. – On fait a := xk−1 , b := xk+1 , d := ξd et on recommence. ξ < 1 est le facteur de convergence. – On s’arrˆete quand d est devenu suffisamment petit. – La m´ethode peut s’appliquer `a une fonction non unimodale. On obtient alors un optimum local sans garantie qu’il soit global. L’algorithme converge ete en – Le nombre de pas d’exploration est au plus b−a b . L’exploration s’arrˆ un temps fini. – Soit [an , bn ] le ne intervalle d’exploration et dn le ne pas d’exploration. On a dn = dξ n et bn − an 6 2dn . – Les [an , bn ] forment une suite d’intervalles emboˆıt´es dont la longueur tend vers 0. Ils convergent donc vers une limite c. Optimisation ` a plusieurs variables min f (x) – Forme du probl`eme : x ∈ Rn – Les inconnues sont les n composantes du vecteur x. – La notion de fonction unimodale ne se g´en´eralise pas. Recherche directionnelle – On se ram`ene au cas `a une seule variable. Pour cela on choisit un point de d´epart a et une direction d. – On minimise la fonction `a une variable f (a + t.d) `a l’aide de l’une des m´ethodes vues plus haut. – Si le d´eplacement t.d est suffisamment petit, on arrˆete. – Sinon, on change de direction et on recommence. – Le point important est le choix des directions. Recherche suivant les axes – On prend comme directions les vecteurs canoniques de la base. Ceci revient `a fixer n−1 variables de la fonction f , et `a optimiser suivant la ne . On passe ensuite `a la variable suivante. – La m´ethode est tr`es lente et peut mˆeme ne pas converger si les courbes de niveau sont `a peu pr`es parall`eles aux diagonales. – On peut l’acc´el´erer en effectuant N pas puis en utilisant la direction aN − a0 . Gradient – On suppose que la fonction f a une d´eriv´ee. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

1.2 Optimisation continue sans contrainte

13

∂f ∂f (a), . . . , ∂x (a))T . On le – Le gradient de f au point a est le vecteur ( ∂x 1 n note ∇f (a). – On a le d´eveloppement de Taylor :

f (a + h) = f (a) + h∇f (a) + . . . . Ceci montre que −∇f (a) est la direction dans laquelle f d´ecroˆıt le plus rapidement (steepest descent). – D’o` u l’algorithme : 1. Calculer le gradient ∇f (a). 2. Minimiser la fonction ` a une variable f (a − x∇f (a)). 3. Si le crit`ere de convergence n’est pas v´erifi´e, recommencer en 1. Propri´ et´ e Th´ eor` eme 1.3. Dans l’algorithme ci-dessus, les directions de recherche successives sont orthogonales. D´emonstration. Soit a le point de d´epart d’une recherche unidimensionnelle suivant la direction ∇f (a) et b son point d’arriv´ee. La d´eriv´ee de la fonction `a minimiser est : df (a − x∇f (a)) = −∇f (a).∇f (x). dx

a

b

En b cette d´eriv´ee est nulle, d’o` u la propri´et´e.



Directions conjugu´ ees – Une matrice A de dimension n × n est d´efinie positive si et seulement si : ∀x : xT Ax > 0. Une matrice d´efinie positive d´efinit un produit scalaire. – Deux vecteurs u, v sont conjugu´es par rapport `a A si et seulement si : uT Av = 0. C’est une g´en´eralisation de la notion d’orthogonalit´e. – Soit n vecteurs d1 , . . . , dn mutuellement conjugu´es : i 6= j ⇒ dTi .A.dj = 0. – Soit la fonction f (x) = 1/2xT Ax + bT x + c. Si on la minimise successivement suivant les directions d1 , . . . , dn , on atteint le minimum exact en n ´etapes. Notations – Soit x(k) , k = 0, . . . les minima successifs. – x(k+1) = x(k) + λk dk . – Le gradient de f en x est Ax + b. – D’apr`es la propri´et´e ci-dessus et la conjugaison des dk , on a : λk = −

dTk (Ax(0) + b) . dTk Adk

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

14

Optimisation sans contraintes – Les coordonn´ees de x(k) sont donn´ees par la formule : x(k) = x(0) +

k X

λi di .

i=1

Preuve Lemme 1.4. En tout point x(k) le gradient de f est orthogonal au sous-espace engendr´e par d1 , . . . , dk . Pk−1 D´emonstration. Le gradient en x(k) est Ax(k) + b = Ax(0) + i=1 λi ADi + b. Si on multiplie par di et qu’on remplace λi par sa valeur il vient : di Ax(0) −

dTi (Ax(0) + b) T .(di Adi ) + b = 0. dTi Adi 

Th´ eor` eme 1.5. Le point x(n) est le minimum de f . D´emonstration. En effet, le gradient en x(n) doit ˆetre conjugu´e de n vecteurs lin´eairement ind´ependants, et donc doit ˆetre nul.  Gradient conjugu´ e – C’est la transposition de la m´ethode ci-dessus au cas o` u la fonction f est quelconque, mais o` u on sait calculer son gradient. – On part d’un point a0 et on pose d0 = −∇f (a0 ). – Supposons que l’on soit parvenu en un point ak avec la direction dk . On minimise f (ak + λ.dk ). Soit λk la solution obtenue. – On pose : ak+1 βk dk+1

= ak + λk .dk , ||∇f (ak+1 )||2 = , ||∇f (ak )||2 = −∇f (ak+1 ) + βk dk .

– On montre que si f est quadratique d´efinie positive, la m´ethode est identique ` a celle des directions conjugu´es et converge en n ´etapes. Recherche al´ eatoire – Au lieu de calculer la direction de recherche optimale pour une approximation quadratique de f , on peut la choisir al´eatoirement en tirant n nombres au hasard dans l’intervalle [0, 1]. – La m´ethode ne n´ecessite pas le calcul du gradient. Elle fonctionne mˆeme si f n’est pas d´erivable. – Mais en g´en´eral, sa convergence est beaucoup plus lente.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

1.3 Programmation lin´ eaire

15

Test d’arrˆ et – Le choix d’un test d’arrˆet est difficile. – Si f est d´erivable, son gradient doit ˆetre nul `a l’optimum. On peut donc utiliser ||∇f (ak )|| < ε comme test d’arrˆet. – Sinon, on peut arrˆeter les it´erations quand la solution ne change plus : ||ak+1 − ak || < ε. – ε doit refl´eter la pr´ecision requise. Il ne doit pas ˆetre plus petit que la pr´ecision des calculs sous peine de blocage. – Il est prudent d’attendre que le test ait ´et´e satisfait plusieurs fois avant d’arrˆeter. – En g´en´eral, la valeur du minimum est mieux d´efinie que sa position.

1.3

Programmation lin´ eaire

Programmation lin´ eaire

min Ax + b – – – –

c.x > 0

x est le vecteur des inconnues, de dimension n. A est la matrice des contraintes, de dimension m × n. b est le terme constant, de dimension m. c de dimension n est le gradient de la fonction objectif.

Autres formes d’un programme lin´ eaire – Un programme lin´eaire peut se mettre sous de multiples formes, toutes ´equivalentes. – On peut changer le sens de l’in´egalit´e, ou passer le terme constant de gauche ` a droite. – On peut remplacer les in´egalit´es par des ´egalit´es en introduisant des variables d’´ecart toutes positives : Ax + b > 0 ≡ Ax + b − y = 0, y > 0 – On peut imposer que toutes les variables soient positives, en posant x := x+ − x− , x+ , x− > 0 – On peut enfin transposer le programme : Ax + b > 0 ≡ xT At + bt > 0 Poly` edre Convexe – L’ensemble P = {x | Ax + b > 0 } est convexe. On l’appelle un poly`edre convexe ou simplement un poly`edre. – La fonction c.x est trivialement convexe. – Donc, si un programme lin´eaire a un minimum local, c’est un minimum global. Test de faisabilit´ e – Pour trouver un minimum, il faut que le poly`edre : P = {x | ax = b > 0 } Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

16

Optimisation sans contraintes

– – – –

soit non vide, ou encore qu’il existe au moins un point x0 qui satisfasse toute les in´egalit´es Ax + b > 0. On peut v´erifier cette condition `a l’aide du test de Fourier-Motzkin. On ´elimine successivement toutes les inconnues de x jusqu’`a trouver un syst`eme sans inconnues, dont la faisabilit´e se teste par inspection. Notations : x(n) le vecteur x amput´e de ses n premi`eres composantes. x(0) = x. A(n) x(n) + b(n) > 0 le syst`eme obtenu apr`es l’´elimination de n variables.

Test de Fourier-Motzkin – Soit a ` ´eliminer x1 . On r´eparti les contraintes en trois classes : – k ∈ I0 ssi ak1 = 0. – k ∈ I+ ssi ak1 > 0. – k ∈ I− ssi ak1 < 0. – Dans une contrainte de I0 , l’inconnue x1 est d´ej`a ´elimin´ee. – Une contrainte k ∈ I+ donne une borne inf´erieure de x1 : x1 > −

bk + ak,2 x2 + . . . ; ak1

– Une contrainte k ∈ I− donne une borne sup´erieure de x1 : x1 6

bk + ak,2 x2 + . . . ; −ak1

– Pour ´eliminer x1 , il suffit d’´ecrire que chaque borne inf´erieure est inf´erieure a chaque borne sup´erieure. ` – On poursuit jusqu’`a ´elimination de toutes les variables. Au bout de n ´etapes, le syst`eme est de la forme : b(n) > 0, qu’il suffit d’inspecter. Correction On dit que le test r´eussit si b(n) > 0, et qu’il ´echoue dans le cas contraire. Th´ eor` eme 1.6. Si le test ´echoue, alors le syst`eme initial est infaisable. D´emonstration. Supposons a contrario que le syst`eme initial a une solution u. Les transformations effectu´ees sur les contraintes sont de simples manipulations alg´ebriques valides ; on en conclu que les intervalles obtenus en comparant une borne inf´erieure et une borne sup´erieure sont non vides, et donc que le syst`eme A(1) x(1) + b(1) > 0 est faisable. En poursuivant l’´elimination, on en arrive au syst`eme d’ordre n − 1, qui n’a plus qu’une seule inconnue xn et qui est ´egalement faisable. Mais le fait que l’un des b(n) < 0 indique que l’un des intervalles de variation de xn est vide, une contradiction.  Compl´ etude Th´ eor` eme 1.7. Si le test r´eussit, le syst`eme initial est faisable. D´emonstration. On exhibe une solution du syst`eme initial en la construisant de proche en proche ` a partir de sa derni`ere composante. On part du syst`eme A(n−1) x(n−1) + b(n−1) > 0. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

1.3 Programmation lin´ eaire

17

Le fait que les b(n) > 0 garantit que l’intervalle des valeurs possibles de xn est non vide. On en choisit une arbitrairement et on la reporte dans le syst`eme d’ordre n − 2. Ce syst`eme n’a plus qu’une inconnue, xn−1 , dont l’intervalle des valeurs possibles est non vide. On poursuit ainsi jusqu’`a avoir donn´e une valeur `a toutes les composantes de x.  Remarques – Si on s’astreint ` a choisir ` a chaque pas la solution la plus petite, i.e. la borne inf´erieure de l’intervalle de variation, on obtient le minimum lexicographique de P, les inconnues ´etant prises dans l’ordre xn , . . . , x1 . – Il n’est pas obligatoire de poursuive l’´elimination jusqu’`a la fin. Si on s’arrˆete ` a l’´etape p, les variables de x(p) deviennent des param`etres. Les conditions b(p) > 0 d´elimitent les valeurs des param`etres pour lesquelles le syst`eme est faisable. Enfin, le proc´ed´e de s´election ci-dessus donne la valeur param´etrique de la solution. – L’algorithme peut s’ex´ecuter sans division. La combinaison de la contrainte j ∈ I+ et de la contrainte k ∈ I− se fait en multipliant la premi`ere par −ak1 > 0 et l’autre par aj1 > 0 et en additionnant. Complexit´ e – On ´evalue d’abord une borne du nombre de contraintes `a l’´etape p, mp , soit mp = x0 + x+ × x+ . – Comme x0 + x+ + x− = mp−1 , mp prend sa valeur maximum pour x0 = 0 et x+ = x− = mp−1 , ` a condition que mp−1 > 4. m 2 – Pour le cas le pire, on a donc la r´ecurrence mp = ( p−1 2 ) dont la solution n m 2 est mn = ( 2 ) . C’est aussi une borne du travail `a effectuer. – La complexit´e est donc ´enorme sauf pour les petits syst`emes. Mais la redondance est ´egalement ´enorme, surtout si le syst`eme est creux (a beaucoup de coefficients nuls). – Enfin, il est possible que l’algorithme se termine pr´ematur´ement. – L’algorithme de Fourier-Motzkin est tr`es simple `a programmer, mais il doit ˆetre r´eserv´e ` a de petits probl`emes. Un exemple – Soit le code : for(j=i+1; j
18

Optimisation sans contraintes + j−i−1 − n−j−1 0 k−i−1 0 n−k−1 − i−j 0 i−k + j + k − 2i Bingo !

> > > > > > >

0, 0, 0, 0, 0, 0, 0.

+ k−i−1 − n−k−1 − i−k 0 n−i−2 0 −1

> > > > >

0, 0, 0, 0, 0.

Algorithme de Fourier-Motzkin ´ etendu – On peut au cours de l’ex´ecution du test, garder la trace des combinaisons effectu´ees. On voit alors que chaque contrainte du syst`eme d’ordre p est une combinaison lin´eaire `a coefficients positifs d’au plus deux contraintes du syst`eme d’ordre p − 1. – En g´en´eralisant, toute contrainte figurant dans l’algorithme est combinaison lin´eaire positive de lignes de Ax + b. Soit y > 0 le vecteur des coefficients. – Comme dans le syst`eme d’ordre n toutes les variables ont ´et´e ´elimin´ees, on en d´eduit yA = 0. Lemme de Farkas Th´ eor` eme 1.8. (∃x : Ax + b > 0) ⇔ (∀y : y > 0, yA = 0 ⇒ yb > 0). D´emonstration. De gauche `a droite soit u tel que Au + b > 0 . Soit un y quelconque tel que y > 0 et yA = 0. On a y(Ax + b) > 0. Mais y(Ax + b) = yAx + yb = yb. De droite ` a gauche, on ex´ecute l’algorithme de Fourier-Motzkin ´etendu. On en tire un y > 0 tel que yA = 0. On en d´eduit que yb > 0, ce qui veut dire que le test a r´eussi et qu’il est possible de construire un u tel que Au + b > 0.  Programmation lin´ eaire – On adjoint au syst`eme Ax + b > 0 la contrainte z > c.x, o` u z est une nouvelle variable. – On ex´ecute l’algorithme de Fourier-Motzkin en prenant soin d’´eliminer z en dernier. – Si l’algorithme ´echoue, le probl`eme n’est pas faisable. – Sinon, la valeur de z dans la solution donne la valeur minimum de c.x. – Le reste de la solution caract´erise un point ou ce minimum est atteint. Lemme de Farkas affine Th´ eor` eme 1.9. Si le syst`eme Ax + b > 0 est faisable, alors : (∀x : Ax + b > 0 ⇒ cx + d > 0) ⇔ (∃λ0 , λ > 0 : (∀x : cx + d = λ0 + λ(Ax + b))).

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

1.3 Programmation lin´ eaire

19

D´emonstration. L’implication de droite `a gauche est ´evidente. De gauche `a droite, l’hypoth`ese revient ` a dire que le syst`eme Ax + b > 0, cx + d < 0 n’a pas de solution. D’apr`es le lemme de Farkas, ceci implique l’existence de y0 , λ > 0 tel que λA − y0 c = 0 et λb − y0 d < 0. De plus, y0 ne peut ˆetre nul car cela impliquerait que Ax + b > 0 n’a pas de solution. On peut donc prendre y0 = 1. On pose λb − d = −λ0 , λ0 > 0 et il vient : λ(Ax + b) − cx − d = λb − d = −λ0 , d’o` u la conclusion du th´eor`eme.



Cˆ ones – Un cˆ one C est un poly`edre convexe dont les contraintes sont de la forme Ax > 0. – Propri´et´e fondamentale : u, v ∈ C, λ, µ > 0 ⇒ λu + µv ∈ C. P Th´ eor` eme 1.10. L’objet { i λi ui | λi > 0 } est un cˆ one. D´emonstration. Il suffit de consid´erer le syst`eme : X x− λi ui = 0, i

λi

> 0.

et d’utiliser la m´ethode de Fourier-Motzkin pour ´eliminer les λi . Ce qui reste est un syst`eme de contraintes lin´eaires en x, qui d´efinissent bien un poly`edre.  R´ eciproque Th´ eor` eme 1.11. Tout cˆ one C = {x | Ax > 0 } est engendr´e par un syst`eme fini de rayons u1 , . . . , up . D´emonstration. On consid`ere l’objet C ∗ = {yA | y > 0 }. C ∗ est un cˆone dont on peut d´eterminer les contraintes comme ci-dessus : C ∗ = {c | cB > 0 } . Quelque soit y > 0, yA appartient `a C ∗ , donc yAB > 0. Comme on peut prendre pour y les m vecteurs unitaires, on en d´eduit AB > 0 ce qui signifie que les vecteurs colonnes de B appartiennent `a C. Soit maintenant x un vecteur quelconque de C. Pour tout y > 0 on a yA.x = y.Ax > 0. En d’autre termes, pour tout c tel que cB > 0, on a cx > 0. On peut donc appliquer le lemme de Farkas affine : il existe λ > 0 tel que x = λB. C est donc engendr´e par les vecteurs colonnes de B.  Th´ eor` eme de Minkovsky Th´ eor` eme 1.12. Tout poly`edre P peut ˆetre mis sous la forme : P = Q ⊕ C ⊕ H, o` u Q est un polytope (poly`edre born´e), C est un cˆ one et H un sous espace lin´eaire. D´emonstration. Soit P = {x | Ax + b > 0 }. On consid`ere le cˆone D = {x, z | Ax + zb > 0 } o` u z est une nouvelle variable. Il est clair que P est l’ intersection de D avec l’hyperplan {z = 1}. On construit les rayons de D. Ceux dont la coordonn´ees z n’est pas nulle engendrent Q. Les rayons dont l’oppos´e est ´egalement un rayon engendrent H. Enfin, ceux qui restent engendrent C.  Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

20

Optimisation sans contraintes On peut ´ecrire : X nX o X X P= λ.u + µ.v + ν.w λ = 1, λ > 0, µ > 0

Les u sont les sommets, les v les rayons et les w les lignes. Programmation lin´ eaire, bis – Le minimum de c.x sous la contrainte x ∈ P = Q + C + H est atteint en l’un des sommets de Q `a condition que H soit vide et que c ∈ C. – En effet on peut ´ecrire : X X X c.x = λc.u + µc.v + νc.w. Puisque ν n’est pas contraint, on peut faire d´ecroˆıtre c.x a volont´e s’il existe un w. Il en est de mˆeme s’il existe un v tel que c.v < 0, puisque µ > 0. Si H est vide, le dernier terme n’existe pas, et si c ∈ C, on minimise c.x en prenant µ = 0. Soit u0 un sommet o` u c.x est minimum, et u1 un sommet o` u c.u1 > c.u0 . Supposons que dans l’expression de x, u1 ait un coefficient λ1 non nul. Le point x − λ1 (u1 − u0 ) est dans P et sa fonction objectif a diminu´e. On en d´eduit que la solution d’un programme lin´eaire est l’un quelconque des sommets de Q o` u c.x atteint son minimum. Critique – La m´ethode ci-dessus est inefficace car il faut utiliser Fourier-Motzkin pour trouver la d´ecomposition de P, et aussi parce que le nombre de sommets n , le coefficient du binˆome). peut ˆetre tr`es grand (de l’ordre de Cm – Il existe un algorithme plus efficaces que Fourier-Motzkin pour d´ecomposer un poly`edre, l’algorithme de Chernikova, mais le nombre de sommets ne change pas. Dualit´ e Th´ eor` eme 1.13. Si les deux ensembles {x | Ax 6 b } et {y | y > 0, yA = c } sont non vides, on a : ` = max {cx | Ax 6 b } = min {yb | y > 0, yA = c } = r. Soit par exemple x∗ (resp. y ∗ ) un point de l’ensemble de gauche (resp. de droite). On a : c.x∗ = y ∗ Ax∗ 6 y ∗ .b. Il en r´esulte que ` et r existent et que ` 6 r. On peut supposer que x∗ (resp. y ∗ ) est le point o` u le maximum (resp. le minimum) est atteint. En tout point x tel que b−Ax > 0 on sait que c.x∗ −c.x > 0, on peut donc appliquer le lemme de Farkas affine : ∃λ0 , λ > 0 : ∀x : c.x∗ − c.x = λ0 + λ(b − Ax). On en d´eduit c.x∗ = λ0 + λb et c = λA. Il en r´esulte que λ fait partie de l’ensemble de droite : r 6 λb = c.x∗ − λ0 6 `. On en d´eduit ` = r. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

1.3 Programmation lin´ eaire

21

Analyse de sensibilit´ e – Variation de ω(b) = max {cx | Ax 6 b } avec b ? – Par dualit´e, ω(b) = min {yb | y > 0, yA = c }. Or ce poly`edre ne d´epend pas de b. Interpr´etation g´eom´etrique : aussi longtemps que b reste dans le cˆ one des directions admissibles, l’optimum y ∗ ne change pas. Donc : ω(b) = y ∗ .b.

optimum

cone des directions admissibles

– Pour en savoir plus, il faut faire de la programmation lin´eaire param´etrique.

Compl´ ementarit´ e Th´ eor` eme 1.14. ∀j : yj .(bj − A•j .x) = 0. D´emonstration. y ∗ .(b − A.x∗ ) = y ∗ .b − y ∗ .A.x∗ = = c.x∗ − y ∗ .A.x∗ = (c − y ∗ A).x∗ = 0. Mais chaque terme du produit scalaire y ∗ .(b−A.x∗ ) est positif, donc si la somme est nulle chaque terme est nul.  Dualit´ e g´ en´ eralis´ ee Il existe une tr`es grande vari´et´e de th´eor`emes de dualit´e, suivant la nature des contraintes et le signe des variables. En premi`ere approximation, on peut utiliser le tableau suivant : Primal objectif (Min) second membre A Contrainte i : > Contrainte i : = Variable xj > 0 Variable xj non contrainte en signe

Dual second membre objectif (Max) AT variable ui > 0 variable non contrainte en signe contrainte j : 6 contrainte j : =

On trouvera dans Schrijver une formulation plus pr´ecise. Algorithme du Simplexe

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

22

Optimisation sans contraintes – «Trouver le point le plus bas d’un vase». Fourier, 1828. – Formalisation par Danzig, 1950.

c

M´ ethodes externes, m´ ethodes internes

c c

optimum

– M´ethodes internes : il faut connaˆıtre un point faisable. On peut arrˆeter la recherche avant l’optimum. – M´ethodes externes : il n’y a pas besoin de connaˆıtre un point faisable.

Ordre lexicographique – D´efinition : x  y = ∃k : x1,··· ,k−1 = y1,··· ,k−1 , xk < yk .  est un ordre total. L’ordre par composantes n’est pas total. c.x < c.y n’est pas un ordre. D’o` u l’int´erˆet de remplacer min c.x par min . On peut toujours ajouter une nouvelle variable u et la contrainte u > c.x a condition que u soit la premi`ere inconnue. ` – Cette technique ´evite les probl`emes bien connus de d´eg´en´erescence. – – – – –

Algorithme du simplexe externe ou dual Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

1.3 Programmation lin´ eaire

23

R´esoudre :

G´en´eralisation : min 

x

min

x

y = Sz + t z

> 0 > 0



x > 0 Ax + b > 0 Tailles : x : n, A : m × n, b : m. Au commencement,  z = x, S =

I A



 , t=

0 b

 .

Invariants – Les vecteurs colonnes de S sont lexicopositifs au d´emarrage et le restent tout au long de l’algorithme. – z est un sous-ensemble de x, y. La condition z > 0 est donc toujours v´erifi´ee. – D’une ´etape ` a l’autre, t croˆıt dans l’ordre lexicographique. – Ces invariants sont v´erifi´es au d´ebut de l’algorithme. Cas de base – Si t > 0, on a trouv´e la solution. Il suffit de faire z = 0, ce qui satisfait les contraintes. On a x = t1,··· ,n . – De plus, c’est le minimum lexicographique : toute autre valeur positive de z ajoute ` a x un vecteur lexicopositif. – Soit ti < 0. Si ∀j : Sij 6 0, le probl`eme n’a pas de solution. Changement de variable – Soit ti < 0 et Sij > 0 (le pivot). On ´elimine zj en faveur de yi : X zj = yi /Sij − Si` /Sij z` − ti /Si` . `6=j

yk =

X

(Sk` − Skj Si` /Sij )z` + Skj /Sij zj + tk − Skj ti /Sij .

`6=j

– Remarquer que −ti /Sij est positif, et que Skj est lexicopositif. Donc, t croˆıt selon l’ordre lexicographique. – Comme Sij > 0, le vecteur colonne j reste lexicopositif. – Il reste ` a garantir que le vecteur colonne ` reste lexicopositif. Choix du pivot – Si Si` est n´egatif, il n’y a pas de probl`eme. – Sinon le nouveau vecteur colonne est ´egal, `a un coefficient positif pr`es, `a : S•` /Si` − S•j /Sij . – Il faut donc choisir j pour que Sij > 0 et que le «vecteur r´eduit» S•j /Sij soit le plus petit possible. – Un tel choix est toujours possible sauf si on est dans le cas d’un syst`eme infaisable. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

24

Optimisation sans contraintes

Convergence – Observer que l’´etat de l’algorithme est enti`erement d´etermin´e quand on sait quelles sont les composantes de y qui sont dans z (les variables en base). n – Or y est de taille m+n et z de taille n, il n’y a donc que Cm+n combinaisons possibles. – L’algorithme ne peut pas boucler, car t croˆıt dans l’ordre lexicographique. n – Comme Cm+n n’est pas un polynˆome en n et m, l’algorithme n’est pas polynomial. – On peut construire des cas pathologiques qui demandent un temps exponentiel. – Mais en pratique (et en probabilit´e) le nombre d’op´erations est en O(n2 (n+ m)). Questions num´ eriques – Du point de vue num´erique, l’algorithme du Simplexe est analogue `a la m´ethode de Gauss, avec une r`egle particuli`ere pour le choix du pivot. – Si l’on connaˆıt la matrice des inconnues de base, l’algorithme ne fait qu’inverser celle-ci, tout en appliquant les mˆemes transformations aux inconnues hors base. – Les r´esultats sont donc donn´es par des formules de Cramer. – On peut faire les calculs en virgule flottante. Il y a alors accumulation d’erreurs d’arrondi, qui peuvent faire que la solution finale n’est pas faisable (en particulier pour les contraintes satur´ees). – Il faut alors d´evelopper des m´ethodes de correction. En g´en´eral la solution est faisable, mais l’optimalit´e n’est pas garantie. – On peut rendre la matrice des contraintes enti`eres, et essayer de mener les calculs exactement (algorithmes «tout entiers»). – Les nombres ` a manipuler sont des d´eterminants de Cramer. On peut donc les borner ` a l’aide de l’in´egalit´e de Hadamard : |det(A)| 6 |A1 | . . . |An |, o` u les Ai sont les vecteurs colonnes (ou les vecteurs lignes) de A. – Il en r´esulte que la taille des nombres `a manipuler est born´ee par n fois la taille du plus grand ´el´ement de A. Cette borne est rarement atteinte. – Il faut utiliser des arithm´etiques en pr´ecision arbitraire, telle la librairie GMP. Algorithme primal – On prend le probl`eme sous la forme ´equivalente suivante : min f (x) = c.x Ax = b x > 0 – On peut supposer que les lignes de la matrice des contraintes A sont lin´eairement ind´ependantes : on peut ´eliminer les lignes redondantes. – A est de dimension m × n avec n´ecessairement m < n. Dans le cas contraire, le syst`eme Ax = b aurait au plus une solution et le probl`eme serait trivial.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

1.3 Programmation lin´ eaire

25

Base – Une «base» est une matrice carr´ee n × n extraite de A inversible. On partitionne A en deux blocs B, la base, et N le reste de la matrice. On partitionne de mˆeme x en xB , xN et c en cB , cN . – La solution associ´ee ` a une base B est le vecteur (B −1 b, 0)T . Il satisfait ´evidemment ` a la contrainte Ax = b. – La base B est r´ealisable si et seulement si la solution correspondante satisfait ´egalement ` a la contrainte x > 0, c’est-`a-dire si x = B −1 b > 0. – A une base r´ealisable correspond une valeur de l’objectif, cB .B −1 b. – Est-il possible d’am´eliorer cet objectif en faisant varier xN ? Recherche de l’optimum – Si xN n’est plus nul, on a : xB = B −1 (b − N xn ) f (x) = cB .B −1 b + (cN − cB .B −1 N )xn

–

– – –

– – – – – –

Le vecteur c = cN − cB .B −1 N est le vecteur des coˆ uts r´eduits. Si xi fait partie de xn , comme il est nul on ne peut que l’augmenter pour que la solution reste faisable. Ceci fait d´ecroˆıtre f (x) `a condition que ci < 0. Si tous les coˆ uts r´eduits sont positifs, on a trouv´e l’optimum. Sinon, on choisit un xi dont le coˆ ut r´eduit est n´egatif (par exemple celui dont le coˆ ut r´eduit est minimum). Puisque on fait croˆıtre xi et que les autres composantes de xN restent nulles, la seule contrainte sur la valeur de xi est B −1 (b − N xn ) > 0. Il y a deux cas possibles : Toutes les composantes de la colonne i de B = B −1 N sont n´egatives. Alors xi n’est pas born´e, et le minimum est −∞. Sinon, ` a chaque composante B ik > 0 correspond la borne xi 6 xk /B ik . Soit j l’indice de la plus petite de ces bornes. Le point correspondant ` a xk = 0 sauf pour k = j : xj = xj /B ij est faisable et la valeur de f (x) est inf´erieure `a celle du point de d´epart. La base qui correspond au nouveau point courant s’obtient en rempla¸cant dans b le colonne i par la colonne j. On poursuit l’algorithme en inversant la nouvelle base et en calculant la nouvelle solution et les nouveaux coˆ uts r´eduits. L’algorithme se termine si ` a chaque pas la valeur de l’objectif d´ecroˆıt strictement. En effet il n’y a que Cnm bases possibles et la condition de d´ecroissance stricte empˆeche tout bouclage.

– Cependant l’algorithme peut boucler en cas de d´eg´en´erescence (il semble que ce soit tr`es rare). – Comme pour l’algorithme dual, on peut mener les calculs de fa¸con incr´ementale (il suffit d’un seul pivot de Gauss pour inverser la nouvelle base). Recherche du point faisable initial – Il s’agit de trouver un point dans le poly`edre P = {x | x > 0, Ax > b }. Soit 1 le vecteur dont tous les ´el´ements sont ´egaux `a 1, et soit y un nouveau Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

26

Optimisation sans contraintes vecteur de mˆeme taille que x. On consid`ere le probl`eme : min x > y > Ax + y >

1.y 0 0 b

– Il est facile de voir que le point x = 0, y = max(b, 0) est faisable. On peut donc appliquer l’algorithme pr´ec´edent. – Si y ∗ = 0, il est facile de voir que le point x∗ ∈ P . – R´eciproquement, si x∗ ∈ P , alors (0, x∗ ) est faisable pour le probl`eme augment´e, donc le minimum est nul. Si inversement le minimum n’est pas nul, P est vide.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

Chapitre 2

Optimisation sous contraintes Optimisation sous contraintes – R´esoudre : courbes de niveau de la fonction objectif optimum

contraintes

gi (x) x

min f (x), 6 0, i = 1, . . . , n ∈ Rn

– L’ensemble des points faisables est {x ∈ Rn | gi (x) 6 0, i = 1, . . . n }. Les fonctions g sont les contraintes. – La programmation lin´eaire est le cas particulier o` u f et les gi sont lin´eaires. On obtient des probl`emes plus ou moins difficiles suivant que l’un ou l’autre ou les deux de ces ´el´ements sont non lin´eaires (resp. non convexes).

G´ en´ eralisation – Certaines contraintes peuvent ˆetre difficiles `a mettre sous la forme gi (x) 6 0. – Exemple : on veut que x soit entier (i.e. `a coordonn´ees enti`eres). – On remplace la derni`ere contrainte par : x ∈ S ⊆ Rn .

2.1

Conditions de Kuhn et Tucker

Caract´ erisation de l’optimum – On suppose les fonctions f et gi continues et `a d´eriv´ees continues. – L’optimum x∗ peut ˆetre ` a l’int´erieur de F . Dans ce cas ∇f (x∗ ) = 0 . – L’optimum peut ˆetre sur les fronti`eres de F . Dans ce cas gi (x∗ ) = 0 pour un certain nombres de contraintes (les contraintes satur´ees) et ∇f (x∗ ) n’est pas n´ecessairement nul. On note I ⊆ {1, . . . , n} l’ensemble des indices des contraintes satur´ees.

28

Optimisation sous contraintes – En particulier, si les contraintes sont toutes des contraintes d’´egalit´e, l’int´erieur de F est vide et l’on est toujours dans le dernier cas (dit de Lagrange). – En programmation lin´eaire, f (x) = c.x, ∇f = c n’est jamais nul (ou bien le probl`eme est trivial), donc l’optimum est sur la fronti`ere de F . – Une direction d est admissible en un point x∗ ∈ F si il existe η > 0 tel que λ < η ⇒ x∗ + λd ∈ F . – x∗ est un minimum si, pour toute direction admissible d, λ < η ⇒ f (x∗ + λd) > f (x∗ ). – La condition d’admissibilit´e peut s’´ecrire : gi (x∗ + λd) = gi (x∗ ) + λd.∇gi (x∗ ) 6 0, i ∈ I, soit encore d.∇gi (x∗ ) 6 0, i ∈ I. – Les directions admissibles en x∗ appartiennent au cˆone C = {d | d.∇gi (x∗ ) 6 0, i ∈ I } , avec I = {i | gi (x∗ ) = 0 }. – La r´eciproque est fausse, sauf dans quelques cas particuliers : – Les fonctions gi sont lin´eaires ou convexes ; – Les gradients sont lin´eairement ind´ependants. – Si C est l’ensemble des directions admissibles, alors une condition n´ecessaire d’optimalit´e est : d ∈ C ⇒ f (x∗ + λd) − f (x∗ ) > 0, d ∈ C ⇒ d.∇f (x∗ ) > 0.

Conditions de Kuhn et Tucker – D’apr`es le lemme de Farkas, il existe des λi > 0, i ∈ I tels que : X ∀d : −d. λi .∇gi (x) = d.∇f (x∗ ), i∈I ∗

∇f (x ) −

X

λi ∇gi (x)

= 0.

i∈I

– Si on pose λi = 0 pour les contraintes non satur´ees, on peut ´etendre la sommation ` a toutes les valeurs de i. Une condition n´ecessaire pour que x∗ soit un minimum est donc : ∃λi > 0

,

i = 1, . . . , n n X ∇f (x∗ ) − ∇gi (x∗ ) = 0, i=1

λi .gi (x∗ )

= 0.

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

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

2.2 Une m´ ethode directe

29

Conditions de Lagrange – Un contrainte d’´egalit´e gi = 0 peut se repr´esenter par deux contraintes d’in´egalit´e gi > 0 et gi 6 0. − – Il lui correspond deux multiplicateurs de Kuhn-Tucker, λ+ i et λi positifs. ` une – On peut les regrouper en un seul dont le signe est quelconque. A contrainte d’´egalit´e correspond un multiplicateur non contraint en signe. – Si toutes les contraintes sont des ´egalit´es, les multiplicateurs peuvent ˆetre de signe arbitraire. Ils prennent le nom de multiplicateurs de Lagrange. – Dans ce cas particulier, toutes les contraintes doivent ˆetre satur´ees.

2.2

Une m´ ethode directe

M´ ethode des plans s´ ecants – Soit ` a calculer : min f (x), gi (x) 6 0, i = 1, . . . , n x ∈ Rn o` u on suppose que les fonctions f et gi sont convexes. – On remarque que l’on peut supposer f lin´eaire. Sinon, on peut remplacer le probl`eme ci-dessus par le probl`eme ´equivalent : min z − f (x) > gi (x) 6 x ∈

z, 0, 0, i = 1, . . . , n Rn

– On proc`ede de fa¸con it´erative. A l’´etape k, on suppose que l’on connaˆıt un poly`edre convexe Q(k) tel que : Q(k) ⊆ F = {x | g(x) 6 0 } . – On r´esout le programme lin´eaire : min f (x), x ∈ Q(k) . Soit x(k) le point obtenu. – Si x(k) ∈ F , c’est le minimum cherch´e. Sinon, il existe i tel que gi (x(k) ) < 0. On forme : o \ n Q(k+1) = Q(k) x gi (x(k) ) + ∇gi (x(k) )T .(x − x(k) ) 6 0 , et on recommence. Lemme 2.1. Si f est convexe, alors f (x) > f (a) + ∇f (a)T .(x − a). D´emonstration. Pour simplifier on va supposer que x est un scalaire. Soit par (a) exemple b > a. Par d´efinition, f (x)−f (a) 6 (x−a) f (b)−f . En faisant tendre x b−a (a) vers a on en d´eduit f 0 (a) 6 f (b)−f , ce qui n’est autre que le r´esultat cherch´e. b−a La d´emonstration est analogue pour b < a. 

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

30

Optimisation sous contraintes

Lemme 2.2. Q(k+1) ⊆ F . D´emonstration. Soit en effet x un point de F . Puisque gi est convexe, on a gi (x) > gi (x(k) ) + ∇gi (x(k) )T .(x − x(k) ). Or gi (x) 6 0, donc x ∈ Q(k+1) .  0

Lemme 2.3. x(k) 6∈ Q(k ) , k 0 > k D´emonstration. Il suffit d’observer que x(k) ne satisfait pas la contrainte gi (x(k) )+ ∇gi (x(k) )T .(x − x(k) ) 6 0.  Lemme 2.4. Si x(k) ∈ F , c’est le minimum cherch´e. D´emonstration. En effet, d’une part x(k) ∈ F , et d’autre part, x ∈ F ⇒ x ∈ Q(k) ⇒ f (x) > f (x(k) ).  Th´ eor` eme 2.5. Si F est born´e, tout point d’accumulation de la suite x(k) est un optimum. D´emonstration. Soit y ∗ un point d’accumulation, et soit y (k) une suite extraite de x∗ et convergeant vers y ∗ . Montrons d’abord que y ∗ ∈ F . On supposera pour fixer les id´ees que ` a chaque pas, la contrainte utilis´ee pour construire une coupe est celle qui est la moins satisfaite, c’est `a dire celle pour laquelle gi (x( k)) > 0 est maximum. Supposons que y ∗ ne soit pas dans F , et soit gi la contrainte la moins satisfaite. Puisque y (k) converge vers y il existe un k ∗ suffisamment grand pour que gi soit la contrainte la moins satisfaite en y (k) . On ajoute la contrainte : gi (y (k) ) + ∇gi (y (k) )T .(x − y (k) ) 6 0.  0

D´emonstration. Il est facile de voir que la distance ||y [k ) − y (k) ||, k 0 > k ne peut [k)

|gi (y | ∗ ˆetre inf´erieure ` a |∇g est limite des y (k) . [k) | , ce qui contredit le fait que y i (y Supposons maintenant qu’il existe dans F un autre point y 0 tel que f (y 0 ) < f (y ∗ ). Comme y 0 ∈ Q(k) ∀k, il s’en suit que l’algorithme de programmation lin´eaire devrait toujours construire un point x(k) tel que f (x(k) ) 6 f (y 0 ). Par suite de la continuit´e de f , toute limite x∗ de la suite x(k) doit ˆetre telle que f (x∗ ) 6 f (y 0 ) ce qui est contradictoire. 

2.3

M´ ethodes duales

M´ ethodes de p´ enalit´ es – Principe : au lieu d’exclure les points qui violent les contraintes, ajouter `a la fonction ´economique une p´enalit´e d’autant plus ´elev´ee que la contrainte est moins respect´ee. Si la fonction de p´enalit´e est r´eguli`ere, on peut utiliser les m´ethodes d’optimisation sans contrainte. – En g´en´eral, la p´enalit´e d´epend d’un param`etre qui permet de r´egler son importance. Quand la p´enalit´e devient tr`es grande devant la fonction objectif, on tend vers l’optimum sous contrainte. Mais la fonction `a optimiser devient de plus en plus mal conditionn´ee. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

2.3 M´ ethodes duales

31

– Deux vari´et´es : – La fonction de p´enalit´e est nulle dans le domaine faisable. L’optimum p´enalis´e n’est pas faisable. C’est une m´ethode ext´erieure. – La fonction de p´enalit´e devient infinie quand on sort du domaine faisable. L’optimum est faisable, mais la m´ethode a besoin d’un point faisable initial. M´ ethodes ext´ erieures – On consid`ere 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 d´eriv´e continue. – On remplace le probl`eme : P : min f (x), gi (x) 6 0, i = 1, . . . , n x ∈ Rn par la suite de probl`emes : Pk : min f (x) + Sk

n X

h(gi (x)).

i=1

o` u les Sk formentP une suite croissante tendant vers l’infini. n – On note H(x) = i=1 h(gi (x)) et xk la solution de Pk . Convergence Th´ eor` eme 2.6. Si f est continue, si l’ensemble des points faisables est ferm´e et si soit f (x) soit H(x) tend vers l’infini quand x tend vers l’infini, alors tout point d’accumulation de la suite xk est une solution de P . On note ϕk = f (xk ) + Sk H(xk ), et x∗ une solution de P . Lemme 2.7. Les ϕk forment une suite d´ecroissante. D´emonstration. On a f (xk+1 ) + Sk+1 H(xk+1 ) > f (xk+1 ) + Sk H(xk+1 ) parce que Sk+1 > Sk et f (xk+1 ) + Sk H(xk+1 ) > f (xk ) + Sk H(xk ) puisque xk est la solution de Pk . De plus, ϕk 6 f (x∗ ) + Sk H(x∗ ). Mais comme x∗ est faisable, la p´enalit´e est nulle. On a donc l’encadrement f (xk ) 6 ϕk 6 f (x∗ ).  Lemme 2.8. Les H(xk ) forment une suite d´ecroissante. D´emonstration. Comme chaque xk est la solution d’un probl`eme de minimum, on a : f (xk ) + Sk H(xk ) 6 f (xk+1 ) + Sk H(xk+1 ), f (xk+1 ) + Sk+1 6 f (xk ) + Sk+1 H(xk ). En additionnant et simplifiant : (Sk − Sk+1 )(H(xk+1 ) − H(xk )) > 0. Comme le premier terme est n´egatif, l’autre l’est aussi. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml



32

Optimisation sous contraintes – Les xk appartiennent `a un ensemble born´e, soit parce que f (xk ) 6 f (x∗ ) et que f tend vers l’infini `a l’infini, soit parce que H(xk ) 6 H(1) et que H tend vers l’infini `a l’infini. On peut donc extraire de xk une sous-suite x` , ` ∈ L qui converge vers x ˆ. – Par continuit´e, f (x` ) tend vers f (ˆ x), et comme f (xk ) 6 f (x∗ ), f (ˆ x) 6 f (x). – Comme ϕk 6 f (x∗ ), ϕk a une limite phi∗ 6 f (x∗ ). – lim S` H(x` ) = ϕ∗ −f (ˆ x). Donc H(x` ) tend vers 0, et par continuit´e H(ˆ x) = 0. – Donc x ˆ est un point faisable, donc f (ˆ x) > f (x∗ ), donc f (ˆ x) = f (x∗ ) et x ˆ est un optimum.

M´ ethodes int´ erieures – On prend comme fonction de p´enalit´e une fonction qui tend vers l’infini au voisinage de 0, par exemple h(x) = −1/x. Pn – On minimise f (x) + R i=1 h(gi (x)). – Dans les mˆemes conditions que ci-dessus, on montre que l’optimum du probl`eme PR tend vers l’optimum de P quand R tend vers 0. – Toutes les solutions interm´ediaires sont faisables, mais il faut disposer d’un point faisable pour commencer les calculs. Exemple – Le probl`eme du cas le pire de Fourier-Motzkin :

x+y+z

max xy + z, = n

– On ´elimine z ` a l’aide de la derni`ere contrainte et on applique la m´ethode des p´enalit´es : max xy + n − x − y + S(n − x − y)2 . – On utilise un syst`eme de calcul alg´ebrique pour achever les calculs.

2.4

Fonction de Lagrange, point-col

Fonction de Lagrange, point-col – Soit ` a r´esoudre : min f (x), gi (x) 6 0, i = 1, . . . , n x ∈ S ⊆ Rn – La fonction de Lagrange associ´ee est : L(x, λ) = f (x) + λ.g(x), λ > 0. – g est le vecteur dont les composantes sont les gi .

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

2.4 Fonction de Lagrange, point-col

33

Point-col – (x∗ , λ∗ ) est un point-col si et seulement si : x∗ ∈ S, λ∗ > 0. ∀x ∈ S : L(x∗ , λ∗ ) 6 L(x, λ∗ ), ∀λ > 0 : L(x∗ , λ∗ ) 6 L(x∗ , λ). – Caract´erisation d’un point-col : L(x∗ , λ∗ )

=

min L(x, λ∗ ), x∈S

g(x∗ ) > 0, λ∗ .g(x) = 0. Preuve Soit (x∗ , λ∗ ) un point-col. La premi`ere propri´et´e est une cons´equence directe de la d´efinition. La deuxi`eme propri´et´e 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 in´egalit´e. Donc ∀i : gi (x∗ ) 6 0. Pour λ = 0 on trouve : −λ∗ .g(x∗ ) 6 0. Mais les deux termes du produit sont non n´egatifs, donc le produit est nul. Preuve, r´ eciproque La premi`ere caract´eristique entraˆıne directement la premi`ere propri´et´e du point-col. On d´eduit de la troisi`eme caract´eristique que L(x∗ , λ∗ ) = f (x∗ ). Enfin : L(x∗ , λ) = f (x∗ ) + λ.g(x∗ ) 6 f (x∗ ) = L(x∗ , λ∗ ), puisque g(x∗ ) 6 0. Int´ erˆ et Th´ eor` eme 2.9. Si (x∗ , λ∗ ) est un point-col, alors x∗ est un minimum global. D´emonstration. D’apr`es la d´efinition, 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 probl`emes qui n’ont pas de point-col. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml



34

Optimisation sous contraintes

Fonction de Lagrange et p´ enalit´ es – La fonction de Lagrange est une fonction de p´enalit´e. L(x, λ) = f (x) + λ.g(x), λ > 0. – En effet, dans la r´egion infaisable, g(x) > 0, donc le second terme augmente la valeur de L, alors qu’on recherche un minimum. – Toutefois, ce terme est n´egatif dans la r´egion faisable, ce qui diminuerai artificiellement la valeur du minimum, si l’on n’avait pas la contrainte ∀i : λi .gi (x∗ ) = 0. – Comme les m´ethodes de p´enalit´e, l’emploi de la fonction de Lagrange permet de remplacer un probl`eme avec contraintes par un probl`eme sans contrainte. Une mauvaise id´ ee – Maximiser L(x, λ) par rapport `a λ > 0 pour x fix´e. Soit g(x) le r´esultat. Minimiser ensuite g(x) sans contraintes. – Il est facile de trouver le maximum. – Si gi (x) > 0, il suffit de faire tendre λi → ∞ pour obtenir un maximum infini. – Sinon, le maximum est ´egal `a f (x). – Ceci revient donc ` a ´etendre f en une fonction discontinue non d´erivable, ce qui ne se prˆete pas `a l’optimisation. Une bonne id´ ee – Minimiser w(λ) = min L(x, λ) sans contrainte. Maximiser w(λ) sous la contrainte λ > 0. Lemme 2.10. w(λ) est une fonction concave. D´emonstration. Soit λ1 , λ2 deux valeurs de λ, α et β deux nombres positifs tels que α + β = 1, et x un point arbitraire. Par d´efinition des minima : f (x) + λ1 g(x) > w(λ1 ), f (x) + λ2 g(x) > w(λ2 ), f (x) + (αλ1 + βλ2 )g(x) > αw(λ1 ) + βw(λ2 ). et cette propri´et´e vraie partout s’´etend au minimum w(αλ1 + βλ2 ).



Application ` a la programmation lin´ eaire – Il ne faut cependant pas croire que l’optimisation de w est toujours sans contrainte. Soit par exemple le programme lin´eaire : min c.x, Ax − b > 0, x > 0. – La fonction de Lagrange associ´ee est : L(x, λ) = c.x − λ(Ax − b) − µx =

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

(c − λA − µ).x + λb.

2.4 Fonction de Lagrange, point-col

35

– Il est facile de voir que si c−λA−µ n’est pas nul, la valeur du minimum est −∞. Sinon, c’est λb. Comme c − λA − µ = 0 est ´equivalent `a c − λA > 0, on voit que l’on est amen´e ` a r´esoudre :

c − λA λ

max λ.b, > 0, > 0.

C’est le dual du probl`eme original! Et s’il n’y a pas de point col ? Th´ eor` eme 2.11. Soit x∗ la solution du probl`eme avec contraintes. On a : maxλ>0 w(λ) 6 f (x∗ ). D´emonstration. Comme x∗ est faisable, g(x∗ ) 6 0. Donc L(x∗ , λ) = f (x∗ ) + λg(x∗ ) 6 f (x∗ ), w(λ) = min L(x, λ) 6 L(x∗ , λ) 6 f (x∗ ). x

Cette propri´et´e vraie pour tout λ s’´etend au maximum.



– La solution du probl`eme dual fournit une borne inf´erieure de la solution du primal. – Il y a «saut de dualit´e» quand les deux solutions ne sont pas ´egales. – w est d´erivable ` a l’optimum, si et seulement si le saut de dualit´e est nul. G´ en´ eration de colonnes – Si l’ensemble S = {x1 , . . . , xn } est fini, le probl`eme s’´ecrit : n

max min f (xi ) + λg(xi ) λ>0 i=1

se ram`ene ` a un probl`eme de programmation lin´eaire : P (n) : max z z 6 f (xi ) + λg(xi ), i = 1, . . . , n λ > 0. – – – –

Soit xn , λn la solution de P (n). Si S est infini, on suppose que l’on a d´ej`a construit les points {x1 , . . . , xn }. On r´esout le probl`eme lin´eaire ci-dessus. On d´etermine le point xn+1 comme solution de : min L(x, λn ) = f (x) + λn g(x) x∈S

par une m´ethode d’optimisation sans contraintes. – Soit w(λn ) le minimum obtenu. – On recommence avec n + 1 points, jusqu’`a convergence. Lemme 2.12. Soit x∗ la solution du probl`eme avec contrainte : w(λn ) 6 f (x∗ ).

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

36

Optimisation sous contraintes

D´emonstration. Puisque x∗ ∈ S, w(λn ) 6 f (x∗ ) + λg(x∗ ) 6 f (x∗ ) puisque que x∗ est faisable.  Lemme 2.13. f (x∗ ) 6 z n . D´emonstration. Il est ´evident que hf (x∗ ), λn i est un point faisable pour P (n).  Lemme 2.14. z n+1 6 z n . D´emonstration. Tout point faisable pour P (n + 1) est faisable pour P (n).



Convergence – On a l’encadrement w(λn ) 6 f (x∗ ) 6 z n . – Comme la suite z n est d´ecroissante, elle converge. – Mais la convergence de w(λn ) vers f (x∗ ) impliquerait que le saut de dualit´e est nul, ce qui n’est pas toujours le cas.

2.5

Optimisation combinatoire

Optimisation combinatoire – Probl`eme d’optimisation sous contraintes o` u l’ensemble des points faisables est non pas continu mais discret. – Forme du probl`eme : min f (x) x ∈ S – Les inconnues sont les n composantes du vecteur x. S est l’ensemble discret des points faisables. – En g´en´eral, S est produit cart´esien d’ensembles plus petits, et sa taille est le produit des tailles de ces petits ensembles (d’o` u le nom : optimisation combinatoire). – Chaque composant de S correspond `a un choix ; il faut trouver la bonne suite de choix, sachant que ceux-ci ne sont pas ind´ependants en g´en´eral. Exemple – On consid`ere un ordinateur sur lequel on doit ex´ecuter t algorithmes enchaˆın´es Ai , i = 1, . . . , t. Chaque algorithme a pour donn´ees les r´esultats de l’algorithme pr´ec´edent. – Pour impl´ementer chaque algorithme, on doit choisir une structure pour ses donn´ees. On suppose qu’il y a s structures possibles, Sk , k = 1, . . . , s et que le temps d’ex´ecution de l’algorithme d´epend de la structure choisie. Par exemple, une matrice peut ˆetre rang´ee par ligne ou par colonne, et, par suite des effets de cache, le temps d’ex´ecution du produit matriciel varie suivant la structure choisie. On supposera qu’un algorithme ne modifie pas la structure des ses donn´ees. On note Tik le temps d’ex´ecution de l’algorithme i quand les donn´ees on la structure Sk . – On suppose qu’il est possible de modifier les structure de donn´ees (par exemple, de transposer une matrice). On note θk` le temps n´ecessaire pour passer de la structure Sk `a la structure S` . Remarquer que θkk = 0. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

2.5 Optimisation combinatoire

37

– La structure du programme est alors : Sk0 R0 Sk1 A1 Sk1 . . . At Skt Rt Skt+1 – On suppose que k0 et kt+1 sont fix´es par le cahier des charges. – Trouver la s´equence de restructurations donnant le temps total minimum. Quelques m´ ethodes de solution – Une heuristique gloutonne. – On remarque que souvent θkl  Tik . Pour l’exemple matriciel, le temps de transposition est O(n2 ) alors que le temps du produit est O(n3 ). – On choisit donc Skj de fa¸con que Tikj soit minimum, et on rajoute des redistributions si n´ecessaire. – Programmation dynamique. On remarque que le probl`eme a une structure analogue ` a celle d’un probl`eme de plus court chemin. – On note Pn (k) le probl`eme d’optimiser le programme analogue au programme initial, mais ou on s’arrˆete juste apr`es la redistribution Rn avec une structure de donn´ees Sk . Le probl`eme initial est Pt (kt+1 ). Soit Ωn (k) le meilleur temps d’ex´ecution de Pn (k). On a la relation de r´ecurrence : Ωn (k)

=

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

Ω0 (k)

= θ k0 k .

`

– On peut calculer toutes les valeurs de Ωnk `a l’aide de cette r´ecurrence, lire la valeur de Ωt (kt+1 ) et reconstituer le chemin `a suivre par retour arri`ere. – Codage en variables 0-1. On pose Xik = 1 si la distribution des donn´ees `a l’´etape i est la distribution Sk , et 0 sinon. – A chaque ´etape, il y a une et une seule distribution : s X

Xik = 1.

(2.1)

k=1

Pt Ps – Le temps de calcul total est : Tc = i=1 k=1 Tik Xik . – Le temps de redistribution de l’´etape i `a i + 1 est donn´e par θk` tel que Xik = 1 et X(i+1)` = 1, ce qui peut s’´ecrire : Tr

=

t X s X s X

Xik X(i+1)` θk` .

i=0 k=1 `=1

– Il s’agit de minimiser la somme Tc + Tr sous les contraintes (2.1) et Xik ∈ {0, 1}. C’est un probl`eme de programmation quadratique en nombres entiers. Programmation lin´ eaire en entiers – D´efinition. min x, Ax + b > 0, x ∈ N.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

38

Optimisation sous contraintes – Noter que x ∈ N implique x > 0. Il s’agit donc de l’analogue exact du probl`eme r´esolu par l’algorithme dual, `a ceci pr`es qu’il y a une contrainte d’int´egrit´e en plus. – On suppose en g´en´eral que A et b ont des coefficients entiers.

2.5.1

coque enti` ere

Coque enti` ere – Soit S un ensemble de Rn . La coque enti`ere de S, not´ee Sˆ est la coque convexe de l’ensemble des points entiers de S. ˆ x ∈ Zn ∩ S ⇒ x ∈ S, ˆ ˆ x, y ∈ S, λ, µ > 0, λ + µ = 1 ⇒ λx + µy ∈ S. Propri´ et´ es de la coque enti` ere Lemme 2.15. Si A est convexe, Aˆ ⊆ A. ˆ Lemme 2.16. A ⊆ B ⇒ Aˆ ⊆ B. Lemme 2.17. Si Zn ∩ P ⊆ S convexe, alors Pˆ ⊆ S. D´emonstration. Un point de Pˆ est combinaison convexe d’un certains nombres de points de Zn ∩ P , qui appartiennent par hypoth`ese `a S. Or S contient toutes les combinaisons convexes de ses points.  Caract´ erisation de la solution enti` ere Th´ eor` eme 2.18. La coque enti`ere d’un poly`edre d´efini par Ax + b > 0, avec A enti`ere, est un poly`edre. D´emonstration. Soit P = Q + C un poly`edre, o` u Q est born´e et C un cˆone. On peut supposer que les vecteurs g´en´erateurs vi de C sont entiers, et il est facile de voir que Cˆ = PC. Soit B = { i µi vi | 0 6 µi 6 1 }. Il est clair que B est un poly`edre born´e \ inclus dans C. Admettons que Pˆ = Q + B + C (ce sera montr´e par les deux lemmes suivants). Or Q + B est born´e, et pour un poly`edre born´e le th´eor`eme est ´evident, puisque la conque enti`ere est enveloppe convexe de ses points entiers qui sont en nombre finis.  \ Lemme 2.19. Pˆ ⊆ Q + B + C. D´emonstration. D’apr`es un lemme ci-dessus, il suffit de consid´ererP un point x entier de PP . On peut l’´ecrire x = q+c, q ∈ Q, c ∈ C. Il en r´esulte c = i µi vi . On pose c0 = i bµi c vi et b = c − c0 . Il est clair que b ∈ B, donc que q + b ∈ Q + B, \ que c0 ∈ C est entier, et que q +b = x−c0 est entier, donc que q +b ∈ Q + B.  \ + B + C ⊆ Pˆ . Lemme 2.20. Q \ D´emonstration. Puisque Q + B ⊆ P , Q + B + C ⊆ Pˆ + C = Pˆ + Cˆ = P\ +C = ˆ P.  Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

2.5 Optimisation combinatoire

39

Minimum entier Lemme 2.21. Le minimum entier d’un poly`edre est le minimum rationnel de sa coque enti`ere. D´emonstration. Le minimum entier x∗ appartient `a la coque enti`ere. Supposons qu’il existe dans la coque enti`ere un point x0  x∗ . Ce point est n´ecessairement `a coordonn´ees non enti`eres (puisque la coque enti`ere est contenue dans le poly`edre). x0 est donc combinaison convexe de points entiers qui lui sont tous sup´erieurs dans l’ordre lexicographique, ce qui est impossible.  – Le probl`eme sera r´esolu si on sait construire la coque enti`ere. – Mais la complexit´e de la coque enti`ere peut ˆetre ´enorme (Chvatal). – Heureusement, on peut se contenter de construire quelques coupes (et non toute la coque) : des contraintes affines qui excluent une partie de P mais aucun point de Pˆ .

2.5.2

Algorithme de Gomory

Coupe de Gomory – Construction d’une coupe : soit a/D.x + b/D > 0 une des contraintes du probl`eme. D est le d´enominateur commun des coefficients de x et du terme constant. – Par construction de l’algorithme dual, la valeur de cette contrainte est l’une des variables d’´ecart du probl`eme initial, qui doit ˆetre enti`ere. 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, – k est n´ecessairement positif, d’o` u: (a mod D)x − (−b mod D) > 0. Algorithme de Gomory – On a mis le probl`eme sous la forme : min x y = Sz + t > 0 z > 0 o` u la matrice S et le vecteur t sont entiers, ainsi que les variables y et z. z est un extrait de y, et les n premi`eres composantes de y sont les variables originales. – On proc`ede comme dans l’algorithme du Simplexe jusqu’`a obtenir t > 0. Si l’algorithme ´echoue, il n’y a pas de solution enti`ere. – Si les composantes 1 ` a n de t sont enti`eres, c’est la solution. – Sinon, on choisit le premier ti non entier, on construit une coupe comme ci-dessus ` a l’aide de la contrainte Si z + ti > 0, et on l’ajoute au tableau. – Le nouveau tableau n’est pas faisable : le terme constant de la coupe est n´egatif. On reprend l’algorithme jusqu’`a terminaison.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

40

Optimisation sous contraintes

Preuve Th´ eor` eme 2.22. Si l’algorithme se termine, ou bien on a trouv´e la solution enti`ere, ou bien le probl`eme n’a pas de solution. D´emonstration. Soit Pn le poly`edre obtenu apr`es la ne coupe. Par construction, tous les points entiers de P = P0 sont dans Pn . Si donc Pn est vide, P ne contient aucun point entier. Sinon, soit x∗ le minimum lexicographique de Pn , et supposons qu’il est entier. Si P contenait un point entier plus petit, il serait dans Pn ce qui serait une contradiction.  Lemme 2.23. On peut toujours supposer qu’il existe une solution. D´emonstration. On consid`ere le probl`eme ´etendu min u + Ax + b > u > x >

u, x 0, 0, 0

Il est clair que ce probl`eme a toujours une solution : il suffit de prendre x nul et u tr`es grand. Si le probl`eme initial a un minimum x∗ , alors 0, x∗ est le minimum du probl`eme ´etendu. Inversement, si le probl`eme initial n’a pas de solution, alors u ne peut ˆetre nul dans la solution du probl`eme ´etendu. Les deux probl`emes sont donc ´equivalents.  Lemme 2.24. Les minima successifs xn forment une suite croissante dans l’ordre lexicographique. ´ puisque Pn+1 ⊆ Pn . D´emonstration. Evident,

 sj j D xj

+ Dt > 0 la ligne qui – A une certaine ´etape de l’algorithme, soit va fournir la coupe. – A l’´etape qui suit, l’algorithme du Simplexe ex´ecute un pivot. Soit xj la variable ee. P´elimin´ s0 t0 – Soit : j Dj xj + D > 0 la ligne apr`es l’ex´ecution du pivot. P

Lemme 2.25. Il existe un nombre entier Q tel que Dt < Q 6 P s mod D D D´emonstration. La coupe est : j j D xj − −t mod >0 D Les formules de changement de base donnent :

t0 D.

t0 t sj −t mod D D t −t mod D = + 6 + . D D D D sj mod D D D Soit q le quotient entier par d´efaut de t par D : t = qD + t mod D. t0 t mod D + (−t mod D) >q+ . D D Le deuxi`eme 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’in´egalit´e est stricte puisque t n’est pas entier.  Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

2.5 Optimisation combinatoire

41

– A un instant donn´e du d´eroulement de l’algorithme, on dit qu’une ligne est active si lors d’une op´eration ult´erieure, la valeur de son second membre changera. Lemme 2.26. La premi`ere ligne ne peut ˆetre active qu’un nombre fini de fois. D´emonstration. Soit τ1 = dt1 e. On a l’encadrement τ1 −1 < t1 6 τ1 . Consid´erons l’´evolution de τ1 apr`es une coupe. Si la source de la coupe est la ligne 1, apr`es le changement de base qui suit, τ1 augmente au moins d’une unit´e. Si la source est une autre ligne, c’est que t1 est entier. Une autre ligne est source de la coupe, et si la premi`ere ligne est active, c’est que S1j est non nul. La valeur de t1 augmente. Qu’elle prenne une valeur enti`ere ou fractionnaire, la valeur de τ1 augmente au moins d’une unit´e. Or t1 donc τ1 sont born´es par la solution optimale x∗1 .  Th´ eor` eme 2.27. L’algorithme des coupes de Gomory converge. D´emonstration. Nous avons vu que la premi`ere ligne ne peut ˆetre active qu’un nombre fini de fois. Apr`es la derni`ere modification, tout se passe comme si le probl`eme ` a r´esoudre avait une contrainte et une inconnue de moins (m´ethode de d´eflation). On peut donc prouver que la deuxi`eme ligne n’est active qu’un nombre fini de fois. De proche en proche, on voit que l’algorithme se termine.  Complexit´ e – Comme il faut pouvoir distinguer entre nombres entiers et nombres fractionnaires, les calculs doivent ˆetre men´es en arithm´etique exacte. – Les nombres ` a manipuler sont des d´eterminants de sous-matrices n × n de la matrice des contraintes. Leur taille (nombre de bits) est donc born´ee par n fois le nombre de bits du plus grand coefficient. – Le nombre maximum de coupes est born´e par le nombre de coupes n´ecessaires pour caract´eriser la coque enti`ere de l’ensemble des solutions. R´esultat de Chvatal.

2.5.3

Techniques de codage

Variables bool´ eennes – On peut coder un choix entre n possibilit´es `a l’aide de n variables 0-1, X1 , . . . , Xn . – Chaque variable enti`ere nePpeut prendre que les valeurs 0 ou 1 : 0 6 x 6 1. n – Les choix sont exclusifs : i=1 Xi = 1. – Si ` a chaque choixPest associ´e une quantit´e ai , la quantit´e associ´ee `a un jeu n de variables est i=1 Xi ti . – On peut consid´erer les Xi comme des bool´eens et coder les op´erateurs : Z Z Z

≡ X ∨ Y :: Z > X, Z > Y, Z 6 X + Y, ≡ X ∧ Y :: Z 6 X, Z 6 Y, Z > X + Y − 1, ≡ ¬X :: Z = 1 − X.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

42

Optimisation sous contraintes

Probl` emes de graphe – On peut repr´esenter un graphe de nombreuses fa¸cons : matrice d’incidence, matrice de connexion, Zij = 1 si et seulement si il existe un arc i → j. – Chemin : Xij = 1 si et seulement si le chemin emprunte l’arc i → j. Contrainte : Xij 6 PZij . P – Loi de Kirchoff : i Xij = k Xjk , pour tout j except´e le d´ebut et la fin du chemin. P – Chemin simple P : ne passe qu’une fois par chaque sommet. i Xij 6 1. P – Pour le d´ebut, j XijP = 1, et pour la fin i Xij = 1. – Minimiser la somme ij Xij assure que le chemin n’a pas de boucles isol´ees. Techniques de grands nombres – Soit P = {x | Ax + b > 0 } et Q = {x | Cx + d > 0 } deux poly`edres dont on doit explorer les points entiers. Soit z une nouvelle variable 0-1. – Si P et Q sont born´es, alors pour M suffisamment grand, le poly`edre : P ⊕ Q = {z, x | Ax + b + M z > 0, Cx + d + M (1 − z) > 0 } est l’«union disjointe» de P et Q. – On peut mener l’exploration sur P ⊕ Q en une seule fois. – M doit ˆetre choisi de telle fa¸con que x ∈ P entraˆıne Cx + d + M > 0 et r´eciproquement.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

Chapitre 3

M´ eta-heuristiques 3.1 3.1.1

S´ eparation et ´ evaluation ou Branch-and-Bound Algorithme

S´ eparation et ´ evaluation – Plus commun´ement appel´ee branch and bound. Soit un probl`eme de la forme : min f (x) gi (x) 6 0, i = 1, . . . , n – Principe. On construit une arbre de probl`emes. Le probl`eme initial est la racine. – On s’arrange pour diviser le probl`eme en deux (ou plus) sous-probl`emes, par exemple en introduisant une contrainte suppl´ementaire, qui peut ˆetre satisfaite ou non. – Le minimum peut appartenir ` a l’un quelconque des sous-probl`emes. – Si l’on peut prouver que l’un des sous probl`emes est infaisable, on l’´elimine. – Si l’un des sous-probl`emes est tellement contraint que sa solution est ´evidente, on note la valeur de sa solution. – On cherche ` a obtenir une borne inf´erieure de la solution d’un sous-probl`eme. Si elle est sup´erieure ` a la meilleure solution d´ej`a obtenue, on ´elimine le sous-probl`eme. – Dans le cas restant, on subdivise de nouveau le sous-probl`eme. Variables bivalentes – La m´ethode est particuli`erement bien adapt´ee `a la r´esolution de probl`emes lin´eaires en variables bivalentes : les inconnues ne peuvent prendre que les valeurs 0 ou 1. – Pour s´eparer un probl`eme en deux, on choisit l’une des inconnues, par exemple x1 , et on impose les contraintes x1 = 0 ou x1 = 1. – Pour obtenir une borne sup´erieure, on r´esout le probl`eme en continu. – Un sous-probl`emes est r´esolu si toutes les variables sont fix´ees ou si la solution continue est enti`ere.

44

M´ eta-heuristiques

Exemple : le sac ` a dos

max x1 + 2x2 + 3x3 + 4x4 4x1 + 3x2 + 3x3 + x4 x1 , x2 , x3 , x4

6 5 ∈ {0, 1}

– On veut emporter dans un sac `a dos de contenance 5 une s´election de 4 objets de volumes respectifs 4, 3, 3, 1. – Les utilit´es de ces objets sont respectivement de 1, 2, 3 et 4. – Trouver la combinaison d’utilit´e maximum. R´ esolution On value les inconnues dans l’ordre x1 , . . . , x4 .

x4=1

x4=0

13/3 x1=1

x3=1

x1=0

x3=0

x2=1 23/3

x3=1

7

x3=0

x3=1

x2=1

25/4

x2=0

x2=1

x2=0

x2=0

7

x3=0

x1=1

6 x4=1

5

x1=0

x4=0

1

7

Si on value les inconnues dans l’ordre x4 , . . . , x1 , la r´esolution est plus rapide.

M´ eta-algorithme On doit d’abord d´efinir une repr´esentation des probl`emes `a r´esoudre. Par exemple, dans le cas du sac-`a-dos, on notera le tableau du probl`eme et celles des inconnues qui sont d´ej`a valu´ees, dans une variable de type pb. Fonctions de sp´ecialisation : – is_trivial : pb → bool permet de savoir si le probl`eme peut ˆetre r´esolu facilement (i.e. si toutes les inconnues, ou toutes les inconnues sauf une sont valu´ees). – trivial_solve : pb → int r´esout un probl`eme trivial. Doit rendre +∞ si le probl`eme trivial n’est pas faisable. – bound : pb → int donne une borne inf´erieure de la solution. – branch : pb → (pb, pb) d´ecoupe un probl`eme en deux sous-probl`emes. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

3.1 S´ eparation et ´ evaluation ou Branch-and-Bound

45

best pb:= . . . best:= MAXINT Algorithme : BandB(pb0 ) if is_trivial (pb0 ) then local best := trivial_solve(pb0 ) if local best < best then best = local best best pb = pb0 else local best := bound(pb0 ) if local best < best then (pb1, pb2 ) := best pb(pb0) BandB(pb1 ) BandB(pb2 )

– On utilise deux variables globales, best et best pb. – Dans cette version, l’arbre des probl`emes n’est pas repr´esent´e explicitement. Il est cod´e dans la suite des appels r´ecursifs. – La recherche se fait en profondeur d’abord. L’objectif est de trouver une solution le plus vite possible, pour pouvoir ensuite ´elaguer l’arbre. – Dans le cas du sac-` a-dos, on donne la priorit´e `a la valeur x = 1 pour ´eviter la solution triviale xi = 0. – La m´emoire utilis´ee par l’algorithme est proportionnelle `a la hauteur de l’arbre, i.e. au nombres de variables, n. D’autres versions utiliseraient une m´emoire de taille O(2n ).

Construction de l’arbre des probl` emes – Que faire si les variables ne sont pas bivalentes ? – Borner chaque variable, a 6 x 6 b, puis ´ecrire en binaire la valeur de x−a, avec log2 (b − a) bits. Engendre log2 (b − a) variables ´equivalentes. – De fa¸con ´equivalente, partitionner `a l’aide de contraintes x < (b + a)/2 et x > (b + a)/2. M´ethode plus g´en´erale, car on peut ´ecrire des contraintes portant sur plusieurs variables. – Il est possible de partitionner en plus de deux sous-probl`emes. S’applique en particulier au cas o` u les variables ne sont pas num´eris´ees.

3.1.2

´ Evaluation

– La qualit´e de la fonction d’´evaluation conditionne directement l’efficacit´e de la m´ethode. – Exemple du sac ` a dos. On prend comme borne sup´erieure y1 + 2y2 + 3y3 + 4y4 o` u yi = xi si xi est valu´ee et yi = 1 sinon. Il est clair que cette fonction donne bien une borne sup´erieure de l’utilit´e.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

46

M´ eta-heuristiques

x4=1

x4=0

9 x3=1

x3=0

x2=1

x3=1

x2=1

x1=1

x2=0

7 x1=1

x1=0

3

6

7

x2=0

x3=0

6 x2=0 6

7

Relaxation continue – Si le probl`eme est lin´eaire et en nombres entiers, on obtient une borne (inf´erieure ou sup´erieure) `a partir de la solution continue. La m´ethode fournit une alternative ` a la m´ethode des coupes, `a condition que le probl`eme soit born´e. – Relaxation Lagrangienne. On a vu plus haut que si on sait calculer : w(λ) f

∗

= min L(x, λ), x

= max w(λ) λ>0

alors f ∗ est une borne inf´erieure du minimum cherch´e. – Exploitation des propri´et´es de la fonction objectif, quand il est possible de calculer facilement son minimum en ne tenant compte que d’une partie des contraintes. Lin´ earisation de la fonction objectif – Si les contraintes sont lin´eaires, on peut remplacer f par une minorante lin´eaire. – Soit ` a minimiser une fonction contenant le produit de deux inconnues x et y dans un poly`edre (affectation quadratique). – Si on sait d’apr`es les contraintes que x > 0 et y > b, on en d´eduit xy > bx. La solution du probl`eme dont la fonction objectif est bx est un minorant de la solution du probl`eme initial. Lin´ earisation des contraintes – On suppose la fonction objectif lin´eaire. On d´etermine un poly`edre qui contient l’ensemble des points entiers faisables. Si le domaine des points faisables est convexe, cette repr´esentation peut ˆetre aussi pr´ecise qu’on le veut. – La solution dans le poly`edre est un minorant de la solution du probl`eme original. – Exemple : Minimiser une fonction lin´eaire dans un disque.

3.1.3

Strat´ egie et Tactiques

– L’efficacit´e de la recherche d´epend fortement : Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

3.1 S´ eparation et ´ evaluation ou Branch-and-Bound

–

– –

–

47

– De la qualit´e de la fonction d’´evaluation. – De la disponibilit´e d’une premi`ere bonne solution. Noter qu’aucun ´elagage ne se produit tant qu’une solution n’est disponible. – De l’ordre de traitement des nœuds. Dans le m´eta-algorithme ci-dessus : – La fonction d’´evaluation est implant´ee dans la fonction bound. – L’ordre de valuation des variables est implant´e dans la fonction branch. – L’ordre de traitement des nœuds est implant´e dans l’algorithme. C’est l’ordre en profondeur d’abord et de gauche `a droite. Est-ce la meilleure strat´egie ? La strat´egie en profondeur d’abord fournit tr`es vite (en n ´etapes) une solution, et utilise peu de m´emoire. Mais elle peut s’´egarer dans une r´egion peu int´eressante de l’arbre. Dans la strat´egie en largeur d’abord, on construit l’arbre niveau par niveau. 23/3 x1=1

x1=0

5

23/3 x2=0

x2=1

7

x3=1

7

x3=0

6

M´ eta-algorithme (largeur d’abord) – Dans la strat´egie «meilleur d’abord», on se base sur l’id´ee que la valeur de la borne inf´erieure est une estimation de l’optimum dans le sous-arbre. – On a donc int´erˆet ` a d´evelopper d’abord le nœud qui a la meilleure borne. – Dans l’exemple du sac-` a-dos, les deux strat´egies co¨ıncident. – Au niveau de l’impl´ementation, il suffit que les probl`emes soient ordonn´es par valeur (borne) croissante. On modifie les proc´edures insert et pop. – On peut utiliser une structure de donn´ees plus adapt´ee, un tas par exemple. Impl´ ementation parall` ele – L’algorithme par s´eparation et ´evaluation se prˆete bien `a une impl´ementation parall`ele, parce que le d´eveloppement de chaque probl`eme est ind´ependant des autres probl`emes. – La seule d´ependance est celle sur la meilleure solution, best. Mais on peut accepter que cette valeur soit ajust´ee avec retard, la seule incidence ´etant un ´elagage moins efficace. – Paradoxe : l’´elagage peut ˆetre plus efficace si le parall´elisme permet d’atteindre plus vite la r´egion de l’arbre o` u se trouve le minimum.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

48

M´ eta-heuristiques

best pb := . . . ; best := MAXINT queue := ∅; insert(queue, pb0 ) while queue 6= ∅ do pbcurrent := pop(queue) if is_trivial(pbcurrent ) then local best := trivial_solve(pbcurrent ) if local best < best then best := local best best pb := pbcurrent else local best := bound(pbcurrent ) if local best < best then (pblef t , pbright ) := branch(pbcurrent ) insert(queue, pblef t ) ; insert(queue, pbright )

3.2

Programmation Dynamique

Programmation dynamique – M´ethode invent´ee par R. Bellman en 1956. – Con¸cue sur le mod`ele de l’algorithme du plus court chemin dans un graphe. – On remplace la r´esolution d’un probl`eme de taille n par celle d’un certain nombre de probl`emes de taille n − 1, dont on combine les r´esultats. – Exemple : calcul du plus court chemin entre deux points d’un DAG, i et j. – Si i = j, alors la longueur du plus court chemin est 0. Sinon, ce chemin passe n´ecessairement par l’un des successeurs de i. – Soit lij la longueur du plus court chemin, et dij la distance de deux sommets adjacents. On a la r´ecurrence : lij =

min k∈Succ(i)

dik + lkj =

min k∈P red(j)

lik + dkj .

Exemple du sac-` a-dos Soit ` a r´esoudre :

min

n X

ci xi ,

i=1 n X

wi xi

6

W,

xi

∈

{0, 1}

i=1

– On suppose les wi entiers. – On consid`ere la famille de probl`emes obtenue en faisant varier W et en ne prenant en compte que les variables xi , i = k, . . . , n. Soit Vk (W ) la valeur d’un tel probl`eme.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

3.2 Programmation Dynamique

49

´ Equations de r´ ecurrence – Soit ` a calculer V1 (W ). Il y a deux choix possibles : x1 = 0, x1 = 1. – Un fois la valeur de x1 fix´ee, on doit r´esoudre un autre probl`eme de sac`a-dos. – Si x1 = 0, la capacit´e disponible est toujours W , on doit calculer V2 (W ). – Si x1 = 1, il ne reste plus que W − w1 unit´es de capacit´e, mais on a d´ej`a obtenu c1 unit´es de valeur. – Dans le cas g´en´eral, on a la r´ecurrence : Vk (W ) = max{Vk+1 (W ), Vk+1 (W − wk ) + ck }. Conditions aux limites – Que vaut Vn (W ) ? – On ne peut fixer que la valeur de xn , et on doit avoir wn 6 W si on veut pouvoir faire xn = 1. On a donc : ( cn si W > wn Vn (W ) = 0 sinon – De plus, Vk (W ) = 0 si W 6 0. Pn – M´ethode de r´esolutions. On remarque que 0 6 W 6 B = i=1 wi . – Il suffit donc de calculer Vk (W ) pour les B valeurs [1, . . . B] et pour k = n, . . . 1. Algorithme #define N ... #define B ... int w[N+1]; int c[N+1]; void main(void){ int V[N+1][B+1]; int W, k, c1, c2; for(W=1; W <= B; W++) if(w[N] <= W) V[N][W] = c[N]; else V[N][W] = 0; for(k=N-1; k >= 1; k--) for(W = 1; W <= B; W++){ c1 = V[k+1][W]; if(W - w[k] > 0) c2 = V[k+1][W - w[k]] + c[k]; else c2 = 0; V[k][W] = c1 > c2 ? c1 : c2;}}

Remarques – On lit directement la valeur du probl`eme original dans V1W . – Noter que l’on a r´esolu non seulement le probl`eme original, mais le probl`eme pour toutes les valeurs possibles de W . En effet, Vk (W ) = Vk (B) si W > B. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

50

M´ eta-heuristiques – Dans ce cas particulier, comme Vk (W ) ne d´epend que de Vk+1 (W 0 ) pour W 0 6 W , on peut ne calculer les valeurs que pour les valeurs de W au plus ´egale ` a la contrainte du probl`eme original.

Exemple HH k 1 W HH 11 10 10 9 9 9 8 9 7 9 6 7 5 7 4 7 3 4 2 4 1 4 0 0

H

max x1 + 2x2 + 3x3 + 4x4 4x1 + 3x2 + 3x3 + x4 6 5 x1 , x2 , x3 , x4 ∈ {0, 1}

2

3

4

9 9 9 9 9 7 7 7 4 4 4 0

7 7 7 7 7 7 7 7 4 4 4 0

4 4 4 4 4 4 4 4 4 4 4 0

Complexit´ e – Il est facile de voir que la complexit´e est O(n.B). – On dit que le probl`eme est pseudo-polynomial. En effet, n.B est bien un polynˆ ome, mais B est exponentiel en la taille des wk (nombre de bits). – L’ensemble [0, B] est «l’ensemble des ´etats» de l’algorithme. Il peut ˆetre a plusieurs dimensions. Dans ce cas, la complexit´e devient prohibitive. ` Reconstituer la solution – Il suffit d’introduire un nouveau tableau x[N][B+1]. – On modifie l’algorithme comme suit : if(W - w[k] > 0){ c2 = V[k+1][W - w[k]] + c[k]; else c2 = 0; if(c1 > c2){ V[k][W] = c1; X[k][W] = 1; } else { V[k][W] = c2; X[k][W] = 0; } – On reconstitue la valeur des xi par la r`egle : W = W_0; for(k=1; k<=N; k++){ x[k] = X[k][W]; W = W - x[k]*w[k]; } ´ Economiser la m´ emoire – Si l’on n’est int´eress´e que par la valeur de l’optimum, il est facile de voir que l’on n’a besoin que de deux lignes du tableau V, V[k] et V[k+1]. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

3.2 Programmation Dynamique

51

– Il suffit donc de 2B cellules de m´emoire. Les deux lignes sont permut´ees `a chaque it´eration. – Ce cas se pr´esente quand la programmation dynamique est composante d’un autre algorithme, par exemple un branch-and-bound. – Si on souhaite reconstituer la solution, il faut soit stocker le tableau x, de taille N.B, soit effectuer des calculs redondants. G´ en´ eralisation – Soit ` a r´esoudre :

gn (x)

minx∈Ωn 6

fn (x), 0.

– Il est ´evident que la m´ethode ne marche que parce que la fonction objectif et les contraintes ont des propri´et´es sp´eciales. – La fonction objectif doit ˆetre s´eparable. Soit x un vecteur. On note xhd (head) la premi`ere composante de x et xtl (tail) le vecteur des autres composantes. – Une fonction fn ` a n variables est s´eparable s’il existe une fonction hn et une fonction fn−1 telles que : fn (x) = hn (xhd , fn−1 (xtl )), ∂hn (x, y) > 0 ∂y Th´ eor` eme 3.1. min fn (x)

=

gn (x)60

min hn (xhd ,

xhd ∈Ω

min gn (xhd ,xtl )60

fn−1 (xtl ))

D´emonstration. Soit x∗ la solution du probl`eme de droite, et soit y ∗ (xhd ) le point o` u fn−1 (y) atteint son minimum sous la contrainte gn (xhd , xtl ) 6 0. Par construction, hx∗ , y ∗ (x∗ )i satisfait la contrainte, donc fn (x∗ , y ∗ ) > minx∈Ωn fn (x). R´eciproquement, soit x la solution du probl`eme de gauche. On a ming(xhd ,xtl )60 fn−1 (xtl ) 6 fn−1 (xtl ), donc, par la monotonie de hn hn (xhd ,

min g(xhd ,xtl )60

fn−1 (xtl )) > hn (xhd , fn−1 (xtl )),

et cette propri´et´e s’´etend au minimum.



– Cette propri´et´e ne suffit pas. Si la d´ecomposition de fn peut ˆetre poursuivie, elle fournit une r´ecurrence permettant de calculer le minimum, mais sa complexit´e est du mˆeme ordre que celle d’une recherche exhaustive. – Pour aller plus loin, il faut plonger le probl`eme initial dans une famille de probl`emes o` u les contraintes d´ependent d’une variable d’´etat S ∈ S. Pn (S) : min fn (x), gn (x, S) 6 0, o` u gn a les deux propri´et´es : – ∃Tn gn (x, S) = gn−1 (xtl , tn (xhd , S)) – ∀x ∈ Ω, S ∈ S : tn (x, S) ∈ S.

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

52

M´ eta-heuristiques

Algorithme – On suppose que l’ensemble des valeurs possibles de x, Ω et celui des valeurs possible de S, S sont finis. for S ∈ S do Vn (S) = mingn (x,S)60 fn (x) for k = n − 1 downto 1 do for S ∈ S do Vk (S) = min hk (x, Vk+1 (tk (x, S)) x∈Ω

– L’efficacit´e de la m´ethode est enti`erement conditionn´ee par la taille de S qui doit ˆetre ´enum´er´e. – Les probl`emes d’optimisation `a une dimension sur Ω peuvent ˆetre r´esolus par ´enum´eration (si |Ω| est petit) ou par toute autre m´ethode. Application au sac-` a-dos – La fonction objectif se met bien sous la forme : n X

ci xi = c1 x1 +

n X

ci xi .

i=2

i=1

– La fonction h est l’addition, qui est bien monotone croissante en son deuxi`eme argument. – La contrainte se met sous la forme : n X

wi xi − W 6 0,

i=1

Pn et on peut ´ecrire : i=2 wi xi − (W − w1 x1 ) 6 0. – La fonction de transition est tk (x, W ) = W − k x. Pw n – L’espace des ´etats est S = [0, B] avec B = i=1 wi , l’espace des valeurs est Ω = [0, 1]. Autres exemples – On peut envisager d’autres formes de la fonction objectif, comme : n Y

xci i .

i=1

– Ici la fonction de combinaison est la multiplication, qui est bien non d´ecroissante en son deuxi`eme argument `a condition que le premier argument soit non n´egatif. Le voyageur de commerce – On se donne n villes et une matrice des «distances» {dij | 1 6 i 6 n, 1 6 j 6 n }. Certaines distances peuvent ˆetre infinies. – On demande de trouver une tourn´ee de longueur minimale. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

3.3 Exploration al´ eatoire

53

– Une tourn´ee est un circuit hamiltonien, i.e. qui passe une fois et une seule par chaque ville. – Le probl`eme est tr`es difficile, parce que le nombre de circuits (hamiltoniens) est tr`es ´elev´e. ´ Equation de r´ ecurrence – On peut choisir une ville arbitraire, par exemple la ville 1, comme point de d´epart de la tourn´ee. – Soit S un sous ensemble de [1, n] contenant 1. On consid`ere les chemins hamiltoniens de S, c’est-` a-dire les chemins partant de 1 et passant une fois et une seule par chaque ville de S. – On note P red(k) l’ensemble des pr´ed´ecesseurs de k, c’est-`a-dire l’ensemble : {i ∈ [1, n] | dik < ∞ } . – On note F (S, k) la longueur du plus court chemin de 1 `a k qui passe une et une seule fois par toutes les villes de S. – Consid´erons la ville k 0 qui pr´ec`ede k dans le plus court chemin cherch´e. Cette ville fait ´evidemment partie de P red(k) ∩ S. – D’autre part, le chemin de 1 ` a k 0 passe par toute les villes de S − {k}. Si sa longueur est sup´erieure ` a F (S − {k}, k 0 ), il est possible de l’am´eliorer. On a donc la r´ecurrence : F (S, k) =

min

k0 ∈P red(k)∩S

F (S − {k}, k 0 ) + dk0 k .

– On a d’autre part la condition initiale F ({1}, 1) = 0. – On peut donc r´esoudre le probl`eme en tabulant la fonction F pour tous les ensembles ne contenant qu’une ville, puis pour tous les sous-ensembles de villes ` a 2, 3, ... ´el´ements. – On lit le r´esultat en F ([1, n], 1). – Mais la m´ethode n’est pas tr`es efficace car il y a en tout 2n−1 sousensembles. Relaxation – On peut simplifier le probl`eme en demandant que le chemin passe par |S| villes sans exiger qu’il soit hamiltonien. – On peut alors traiter en une seule fois tous les sous-ensembles de mˆeme cardinal. – On obtient une borne inf´erieure de la longueur de la tourn´ee, qui peut ˆetre utilis´ee, par exemple, dans un algorithme branch and bound.

3.3 3.3.1

Exploration al´ eatoire Am´ elioration it´ erative

Position du probl` eme Soit ` a r´esoudre : max f (x). x∈S

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

54

M´ eta-heuristiques – L’ensemble S est l’ensemble des configurations, ou ensemble des ´etats. On suppose qu’il est trop grand pour ˆetre ´enum´er´e, mais qu’il existe un proc´ed´e efficace pour tirer une configuration au hasard dans S. – f est la fonction objectif. ´ – On suppose que tout point x de S a un ensemble fini de voisins, V (x). Etant donn´e x, il existe un proc´ed´e efficace pour ´enum´erer V (x). Enfin, l’espace des configurations est connexe, i.e. on peut aller de x `a y quelconque par des d´eplacements de voisin `a voisin. – Un maximum global de f est un point x∗ de S tel que ∀x ∈ S : f (x) 6 f (x∗ ). – Un maximum local est un point x tel que ∀x ∈ V (x) : f (x) 6 f (x).

Am´ elioration it´ erative Algorithme : Hill-Climbing x best := random(S) best := f (x best) for i = 1 to n do x := random(S) repeat z := x foreach y ∈ V (x) do if f (y) > f (x) then x := y break until z = x if f (x) > best then best := f (x) x best := x

Bassin d’attraction – Autour de chaque maximum local a il existe un bassin d’attraction A d´efini par : a ∈ A, (∀y ∈ V (x) : f (y) > f (x) ⇒ y ∈ A) ⇒ x ∈ A. – Si le point initial est dans le bassin d’attraction du maximum global, l’algorithme Hill-Climbing trouve le maximum global. – La probabilit´e d’atteindre le minimum global tend donc vers 1 quand n → ∞. – Mais il est impossible d’avoir une certitude.

3.3.2

Recuit simul´ e

– Algorithme de M´etropolis, 1953. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

3.3 Exploration al´ eatoire

55

– Voir aussi P. J. M. van Larrhoven ans E.H. Aarts, Simulated Annealing, Theory and Applications, Kluwer, 1987. – Analogie avec la physique statistique. Lorsqu’un objet physique pouvant exister dans plusieurs ´etats atteint l’´equilibre thermodynamique, la population d’un ´etat d’´energie E est donn´ee par la loi de Boltzmann : p(E) =

–

– – – –

1 −E e kT , Z

o` u k est la constante de Boltzmann, T la temp´erature, et Z un facteur de normalisation, la fonction de partition. Cet ´equilibre est dynamique. Il r´esulte de multiples transitions qui se compensent. Une transition faisant varier l’´energie de ∆E a une probabilit´e ∆E proportionnelle ` a e− kT . On mod´elise un probl`eme d’optimisation par un syst`eme thermodynamique dont on simule l’´evolution. Les ´el´ements de S sont les divers ´etats possibles du syst`eme. L’«´energie» de l’´etat x est f (x). Si le syst`eme est dans l’´etat x, il peut passer al´eatoirement dans l’un des ´etats de V (x). La probabilit´e pour le syst`eme de passer dans l’´etat y ∈ V (x) est : – Z1 si f (y) > f (x) ; f (y)−f (x)

– – – – – –

si f (y) < f (x). – Z1 e T Z est le facteur de normalisation. T est une pseudo-temp´erature. Si le probl`eme a des contraintes qui ne sont pas int´egr´ees dans la d´efinition de S, il suffit de faire f (x) = −∞ quand x n’est pas faisable. Au bout d’un certain temps, le syst`eme se stabilise. On r´eduit la valeur de la «temp´erature» et on continue. La motivation est de permettre au syst`eme simul´e de s’´echapper du bassin d’attraction d’un minimum local pour atteindre le minimum global.

Algorithme : Simulated-Annealing T := . . . x := xbest := random(S) best = f (x) for i := 1 to n do for j := 1 to m do y := random(V (x)) if f(y) > f(x) then x := y if f(x) > best then best := f(x) xbest := x else v = random([0, 1]) f (y)−f (x) then x := y if v < e T T := 0.99T

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

56

M´ eta-heuristiques

Analyse du recuit simul´ e – Quand doit-on baisser la temp´erature (i.e., quel est la valeur de m) ? – Combien de fois doit on baisser la temp´erature (i.e. quelle est la valeur de n) ? – A quelle vitesse faire baisser la temp´erature (la valeur 0.99 est elle la bonne) ? Chaˆıne de Markov – Une chaˆıne de Markov uniforme, discr`ete et `a temps discret est un syst`eme qui peut exister dans plusieurs ´etats formant un ensemble S. Soit xn l’´etat du syst`eme ` a l’´etat n. La chaˆıne ne change d’´etat qu’aux instants de valeur enti`ere. – La probabilit´e de transition de l’´etat x `a l’´etat y ne d´epend que de x et de y. Elle ne d´epend ni du temps, ni des ´etats ant´erieurs occup´es par le syst`eme. Soit PP e de transition de l’´etat x `a l’´etat y. xy la probabilit´ – On doit avoir y∈S Pxy = 1. La matrice pxy est une «matrice stochastique». – Il est clair qu’un algorithme de recuit simul´e fonctionne comme une chaˆıne de Markov. Calcul des probabilit´ es de transition – Chaque tirage peut avoir trois r´esultats : – On tire un point y tel que f (y) > f (x). – On tire un point y tel que f (y) < f (x) et un nombre v tel que v < f (y)−f (x) e T . – Dans le cas restant, on recommence le tirage. P P f (y)−f (x) . – Fonction de partition : Z = f (y)>f (x 1 + f (y) f (x) ; –

(x) 1 f (y)−f T Ze

sinon.

Graphe d’une chaˆıne de Markov – Le graphe d’une chaˆıne de Markov a pour sommets les ´etats de la chaˆıne. Il y a un arc de x vers y si et seulement si la transition x → y est de probabilit´e non nulle. – On peut construire les composantes fortement connexes (cfc) de ce graphe et le graphe r´eduit. – En vertu du principe que tout ´ev`enement de probabilit´e non nulle finit par se produire au bout d’un temps suffisamment long, l’´etat de la chaˆıne finit toujours par parvenir dans l’une des cfcs terminale. – On dit que la chaˆıne est simple s’il n’y a qu’une seule cfc terminale. – Une chaˆıne simple finit par atteindre sa cfc terminale. A partir du moment o` u elle entre dans la cfc terminale, elle passe une infinit´e de fois par chaque sommet de celle-ci. Distribution limite Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

3.3 Exploration al´ eatoire

57

– Si p0x est la distribution de probabilit´e initiale sur la cfc terminale, la distribution apr`es n ´etapes est ´egale `a : pn = pn−1 .P – Le comportement de pn d´epend donc des valeurs propres de P T . On montre : – Que 1 est valeur propre de P T . – Que les composantes de pn sont positives, que leur somme est ´egale `a 1, et par cons´equent, qu’elles sont comprises entre 0 et 1. – En cons´equence, P T ne peut avoir de valeur propre de module > 1. – On est dans le cas r´egulier quand 1 est valeur propre simple de P T . Une condition suffisante est que tous les coefficients de P soient non nuls. – Dans ce cas, la distribution de probabilit´e converge vers le vecteur propre de P T associ´e ` a 1. Application au recuit simul´ e – Dans le cas du recuit simul´e, aucune probabilit´e de transition n’est nulle. On est donc toujours dans le cas r´egulier. – Quand la temp´erature d´ecroˆıt, certaines probabilit´es de transition tendent vers 0. A la limite, chaque cfc est un ensemble contigu de minimum locaux. La ou les cfcs terminales sont associ´ees `a l’extremum global. – Pour arrˆeter la recherche, on peut attendre que la distribution de probabilit´e soit stable (par exemple en estimant l’esp´erance math´ematique de x, si cela ` a un sens, ou celle de f (x).) Exemple, Sac-` a-dos – L’ensemble des ´etats est celui des suites binaires de taille n qui v´erifient la contrainte. – Voisinage : deux suites qui diff`erent par un seul bit. – Sur un petit exemple, le r´esultat n’est pas tr`es satisfaisant. Exemple, Voyageur de Commerce – On suppose que la matrice des distances est sym´etrique. – Ensemble des ´etats : ensemble des circuits hamiltoniens du graphe. – Voisinage. – On choisit deux villes a et b visit´ees dans l’ordre a → b. Soit a0 la ville qui pr´ec`ede a et b0 celle qui suit b. – On construit le circuit a0 → b → a → b0 → a0 . – Les r´esultats exp´erimentaux sont excellents.

3.3.3

La m´ ethode Tabou

– On conserve les notions d’espace de configuration et de voisinage. – Pour ´eviter de rester bloqu´e autour d’un optimum local, on conserve la liste des derniers points visit´es, la liste tabou. – Quand on explore un voisinage, on choisit le meilleur voisin `a l’exclusion des points de la liste tabou. – La liste tabou est g´er´ee comme une FIFO. Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

58

M´ eta-heuristiques – Sa longueur est un param`etre crucial. Folklore : la valeur L = 7 est presque toujours suffisante ! Algorithme : Tabou essais := ∅ for i := 1 to n do tabou := ∅ ; x := . . . continue:= true while continue do add_FIFO(tabou, x) if V (x) r tabou 6= ∅ then x := argmin {f (y) | y ∈ V (x) r tabou } else continue:= f alse essais ∪= x return best(essais)

´ Evaluation – Contrairement au recuit simul´e, il n’y a pas de th´eorie de la m´ethode Tabou. – Elle est cependant r´eput´ee plus efficace et fiable que le recuit simul´e. – Le choix de la longueur de la liste Tabou (NB- qui est cach´ee dans la fonction add_FIFO) est le plus important. – L’autre param`etre est le nombre d’essais (n ci-dessus) qui ne peut gu`ere ˆetre choisi que de fa¸con exp´erimentale.

3.3.4

Algorithmes g´ en´ etiques

– Principe : on cherche `a imiter ce que l’ont sait du fonctionnement de l’´evolution biologique. – Chaque configuration doit pouvoir ˆetre cod´ee par une chaˆıne de caract`eres. – Pour le sac-` a-dos, on prend la chaˆıne 0-1 des valeurs des variables. – Pour le voyageur de commerce, on prend la liste des villes dans l’ordre de la tourn´ee. – On travaille non pas sur une configuration, mais sur une population de configurations, que l’on tire au hasard au d´ebut. – On ´evalue f pour tous les individus de la population (parall´elisme) on classe et on retient les meilleurs 20% (par exemple). – On compl`ete la population `a l’aide de 2 m´ecanismes : – Mutation : on choisit un individu au hasard et on modifie (avec une probabilit´e tr`es faible) l’une de ses lettres. – Croisement : On choisit deux individus x et y, on s´electionne un point de croisement x = a.b, y = c.d, et on forme les individus a.d et c.b (la longueur de a et celle de c doivent ˆetre ´egales). – On it`ere jusqu’` a stabilisation de la population. Evaluation Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml

3.4 Conclusion g´ en´ erale

59

Algorithme : Genetic(P, N, L, Q) for i := 1 to P do x[i] := random(S) for k := 1 to N do sort(x, P, f ) l := m := p/5 for q = 1 to Q do i := random(J1, mK) x[l + 1] := mutate(x[i]); l += 1 while l < P do i = random(J1, mK) j = random(J1, mK) if i 6= j then cut := random(J2, L − 1K]) (u, v) := crossover(x[i], x[j], cut) x[l] := u; x[l + 1] := v; l := l + 2

– L’originalit´e essentielle est de travailler sur une population et non sur un individu unique. Similaire ` a l’id´ee du red´emarrage al´eatoire, mais permet une ´evaluation parall`ele si c’est possible. – L’id´ee des mutations est similaire `a l’exploration al´eatoire d’un voisinage. – L’id´ee de recombinaison peut avoir du sens ou non. – Elle repose sur l’id´ee que les g`enes ont un effet cumulatif et non positionnel. – C’est faux pour le sac-` a-dos, pour le voyageur de commerce, et peut-ˆetre aussi dans la nature. – La m´ethode ne s’applique donc efficacement que dans des cas particuliers.

3.4

Conclusion g´ en´ erale

– Tout un ensemble de m´ethodes, des plus particuli`eres (la programmation lin´eaire et les m´ethodes de gradient) aux plus g´en´erales (les m´etaheuristiques). – Les m´ethodes particuli`eres sont plus difficiles `a programmer, mais plus efficaces. – Les m´ethodes g´en´erales sont faciles `a programmer et d’un champ d’application plus vaste. – Donc choisir toujours la m´ethode la plus sp´ecialis´ee compatible avec la d´efinition du probl`eme (il existe beaucoup de logiciels tout faits, libres et commerciaux). – La m´ethode Branch and Bound demande une ´etude pr´eliminaire du probl`eme. Elle est tr`es g´en´erale et pas trop difficile `a programmer. Elle justifie `a elle seule le principe de Minoux : «En optimisation combinatoire, la lin´earit´e n’est pas importante».

Distribu´ e sous license Open-Content: http://opencontent.org/opl.shtml