Recherche Op´erationnelle Premi`ere Partieperso.ens-lyon.fr/paul.feautrier/slides-ch1.pdf ·...

Recherche OperationnellePremiere Partie

Paul Feautrier

ENS Lyon

1er novembre 2005

Plan

I Introduction et principaux concepts

I Optimisation continue sans contrainte

I Programmation lineaire

I Optimisation continue sous contrainteI Optimisation combinatoire

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

I Elements de Complexite

Plan

Principaux concepts

Un exempleModelisationResolutionConclusion

Optimisation continue sans contrainte

Programmation lineaire

Qu’est ce que la recherche operationnelle ?

I Vocabulaire: Recherche operationnelle = programmationmathematique = optimisation (mais pas optimisation deprogramme).

I Recherche operationnelle = modelisation mathematique desprocessus de prise de decision.

I Inconnues : les variables de decision.I Evaluation de la decision = fonction economique ou fonction

«objectif».I Trouver les valeurs des variables de decision qui minimisent (ou

maximisent) la fonction objectif.

Recherche operationnelle

modélisationoptimisation action

I La modelisation est un art, l’optimisation est une science.I Applications : planification du debarquement de Normandie,

optimisation d’un programme de calcul intensif,investissement en bourse.

I Investissement en bourse = optimisation avec informationincomplete ou aleatoire.

I Planification d’une operation militaire = il y a un adversaire =theorie des jeux.

I Optimisation d’un programme = en principe, on a uneinformation complete.

I Le cours est essentiellement consacre a l’optimisation avecinformation complete.

Informatique ou mathematique ?

Mathématique Informatique

Recherche Opérationelle

Complexité

Théorèmes d’existenceConvergence

AlgorithmesPreuves de terminaisonArtificielle

Intelligence

Vocabulaire

courbes de niveau dela fonction objectif

optimum

contraintes

Formecanonique :trouver x ∈ Dqui minimise f .

min f (x)x ∈ D

Optimum local, global

I Minimum local : a est un minimum local de f s’il existe unvoisinage V de a tel que :

x ∈ V ⇒ f (x) > f (a).

I Minimum global : a est un minimum global de f dans D si etseulement si :

x ∈ D ⇒ f (x) > f (a).

local

global

Convexite

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 .

convexe convexe convexe non convexe

Fonction convexe

I 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)

S

f

x

y

Interet de la convexite

TheoremeSi f est convexe dans un ensemble convexe S, alors tout minimumlocal de f est un minimum global.

Demonstration.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) alorson a :

f (λa + (1− λ)b) 6 λf (a) + (1− λ)f (b).

Il est possible de trouver un λ suffisamment proche de 1 pour quex = λa + (1− λ)b soit dans V . Contradiction en ce point :

f (x) 6 λf (a) + (1− λ)f (b) 6 f (a),

Classification

I Selon la nature des variables de decision :I Optimisation continue.I Optimisation discrete ou optimisation combinatoire.

I Selon la nature des contraintes :I Pas de contraintes ou contraintes faciles a satisfaire (un

segment de la droite reelle) : optimisation sans contraintes.I Optimisation sous contraintes : il est difficile de trouver un

point satisfaisant les contraintes.

I Proprietes speciales des elements du probleme : linearite,convexite.

Plan

Principaux concepts

Un exempleModelisationResolutionConclusion

Optimisation continue sans contrainte

Programmation lineaire

Un exemple: l’allocation de registre

I Les processeurs modernes utilisent des registres pour eviter lesacces a la memoire.

I Il est interessant de conserver une donnee en registre le pluslongtemps possible ...

I Mais les registres sont en nombre fini.

I Le compilateur commence par ecrire le code comme s’il yavait un nombre illimite de registres virtuels, puis alloue lesregistres virtuels aux registres physiques.

I Il ne faut pas utiliser plus de registres physiques qu’il n’y en asur le processeur.

Plan

Principaux concepts

Un exempleModelisationResolutionConclusion

Optimisation continue sans contrainte

Programmation lineaire

Intervalle de vivacite

I Bloc de base : suited’instructions sanstest et sans gotoentrant ni sortant. Enpremiereapproximation, onalloue les registresindependemmentpour chaque bloc debase.

I Un registre virtuel estvivant depuis sapremiere ecriturejusqu’a sa dernierelecture.

1 v1 = stack ; [1,11]2 v2 = *v1 ; [2,7]3 v3 = 2 ; [3,7]4 v4 = *(v1+8) ; [4,8]5 v5 = *(v1+16) ; [5,9]6 v6 = *(v1+24) ; [6,10]7 v7 = v2*v3 ; [7,8]8 v8 = v7*v4 ; [8,9]9 v9 = v8*v5 ; [9,10]10 v10 = v9*v6 ; [10,11]11 *v1 = v10 ;

Graphe d’interference

I Deux registres virtuels interferents’ils peuvent etre simultanementvivants, i.e. si leurs intevalles devivacite ont une intersection nulle.

I Deux registres virtuels quiinterferent ne peuvent pas etrealloues au meme registre physique.

I On peut construire le graphed’interference d’un bloc de base.

V2 V3 V4

V1

V9

Colorier le graphe d’interference

I Contrainte : Il faut affecter un registre physique a chaqueregistre virtuel de facon a ce que deux registres virtuelsadjacents ne soient pas affectes au meme registre physique.

I Objectif minimiser le nombre de registres physiques.

I C’est un probleme classique de coloriage de graphe.I On peut le prendre de deux facons:

I Existe-t-il un coloriage avec k couleurs ?I Quel est le nombre minimum de couleurs necessaires (nombre

chromatique = register pressure).

I On va se concentrer sur la deuxieme question.

Plan

Principaux concepts

Un exempleModelisationResolutionConclusion

Optimisation continue sans contrainte

Programmation lineaire

NP-completude

I On doit toujours commencer par une estimation de ladifficulte du probleme.

I Probleme NP: probleme dont on peut verifier la solution entemps polynomial.

I Il existe une liste (provisoire) de problemes NP pour lesquelson ne sait pas (aujourd’hui) trouver la solution en tempspolynomial, et qui peuvent etre reduits l’un a l’autre en tempspolynomial : les problemes NP-complets. Exemples canoniques: SAT (une formule booleenne est-elle satisfiable) et PLNE (unsysteme d’inequations en nombres entiers est-il satisfiable).

I Le probleme du coloriage est NP-complet: on peut le reduire aun probleme SAT, et on peut reduire un probleme SAT a unprobleme de coloriage.

I Il ne faut donc pas esperer une solution facile.

Programmation lineaire en nombres entiers

I On numerote les couleurs par des entiers ; soit ci la couleur dusommet Vi . Les contraintes sont:

ci > 0

ci 6= cj ,Vi adjacentVj .

I Objectif: minimiser max ci :

min z ,

z > ci .

I Pour rendre le probleme convexe, on pose: xij = 1 ssi ci > cj .On obtient un probleme en variables entieres dont lescontraintes sont:

ci − cj + (1− xij)M > 0, cj − ci + xijM > 0.

ou M est un“grand nombre”. On s’est ramene a un PLNE.

Branch-and-Bound, I/III

I Methode : on construit un arbre de sous-problemes endivisant l’espace des solutions recursivement en deux.

I La recherche s’arrete quand la solution est“evidente”.

I On utilise une borne inferieure pour ignorer les sous-problemesqui ne sont pas“prometteurs”.

Branch-and-Bound, II/III

I On engendre les sous-problemes en remplacant ci 6= cj parci > cj ou par cj > ci . Chaque sous-probleme est un problemede plus court chemin, qui se resoud en temps polynomial.

I S’il n’y a pas de solution (cycle de poids positif) il est inutilede poursuivre l’exploration.

I Sinon, on compare la valeur du probleme a la meilleuresolution connue. On arrete l’exploration si elle est superieure.

I On obtient une solution (candidate) quand on a exploitetoutes les contraintes.

Branch-and-Bound, III/III

����

����

����

����

��

������������������������������

� � � � � � � � � ���������������������

������������������������������������������������������

���������������������������������������������

���������������������������������������������= +

i

j

iji

j

I Selectionner deux sommets i et j non connectes.I Il y a deux possibilites:

I Ils ont la meme couleur: on peut les fusionner.I Ils ont des couleurs differentes: on peut ajouter l’arc i − j .

I La division s’arrete quand on a forme un graphe complet, dontle coloriage est trivial.

I On peut avoir une borne inferieure en cherchant une cliquedans le graphe.

Recherche aleatoire

I Initialisation : on part d’un coloriage legal arbitraire: parexemple, on donne a chaque sommet une couleur differente.

I Exploration : on choisit au hasard un sommet et on changesa couleur au hasard.

I Progression : on conserve le nouveau coloriage s’il est legal ets’il ameliore la solution (moins de couleurs).

I Il existe de nombreuses variantes sur le meme theme (recuitsimule, tabou, algorithmes genetiques): voir la suite du cours.

Plan

Principaux concepts

Un exempleModelisationResolutionConclusion

Optimisation continue sans contrainte

Programmation lineaire

Conclusion

I De nombreux problemes de la vie pratique (emploi du temps),de programmation (utilisation optimale d’un reseau), decompilation (allocation de registres, parallelisation) peuvent semettre sous la forme“optimisation sous contraintes”.

I Les inconnues peuvent etre continues ou discretes (couleurs).

I Avantage: Il existe toute une panoplie de methodes deresolution efficace.

I Toute l’intelligence se concentre dans la phase demodelisation, pour laquelle il n’existe que des“recettes decuisine”.

I Le modele peut etre plus ou moins detaille (exemple:allocation de registres en tenant compte des identitesremarquables de l’algebre).

Plan

Principaux concepts

Un exempleModelisationResolutionConclusion

Optimisation continue sans contrainte

Programmation lineaire

Optimisation continue sans contrainte

On considere une seule variable

min f (x)

x ∈ R

I Si on connaıt la derivee f ′ de f , le probleme se ramene atrouver les racines de f ′, puis a les tester une par une poursavoir si elles sont un minimum, un maximum ou un pointd’inflexion.

I On peut utiliser pour cela des methodes classiques : iterationde Newton (si on peut calculer la derivee seconde),dichotomie, methode de la secante.

I Si on ne connaıt pas la derivee, la premiere chose a faire estde trouver un encadrement du minimum. Il n’y a pas demethode generale, on utilise les renseignements que l’on peutavoir sur f .

Fonctions unimodales

I Une fonction f est unimodale dans l’intervalle [a, b] s’il existeun point a 6 c 6 b tel que si x 6 y 6 c alors f (x) > f (y) etsi c 6 x 6 y alors f (x) 6 f (y).

I Il est evident que si f est unimodale dans [a, b], alors c est unminimum global.

TheoremeSi f est continue convexe dans [a, b], alors f est unimodale.

Demonstration.Soit c le minimum de f , et x et y qui violent la conditiond’unimodalite, par exemple c 6 x 6 y et f (c) < f (y) < f (x). Soit0 6 λ 6 1 tel que x = λc + (1− λ)y . Par convexite on doit avoirf (x) 6 λf (c) + (1− λ)f (y) mais aussiλf (c) + (1− λ)f (y) 6 f (y) < f (x) une contradiction.

Methode par trichotomie

a c d b a c d b

I On divise l’intervalle [a, b] en trois parties egales a l’aide despoints a < c < d < b. On calcule f (c) et f (d).

I On determine le minimum de f parmi les 4 points a, c, b, d .I Le minimum continu appartient a l’intervalle encadrant le

minimum discret.I L’intervalle est reduit au moins par un facteur 2/3. On

poursuit jusqu’a la precision voulue.

Ameliorations

I Vitesse de convergence : la taille de l’intervalle est multipliee

par 23

n/2apres n evaluations de la fonction.

I La division en segment egaux n’est pas optimale. On a intereta agrandir les segments extremes.

I On peut passer a un decoupage en 4 parties egales. Il fautevaluer f trois fois a chaque etape, mais l’intervalle est au

moins divise par 2. La convergence est en 12

n/3donc plus

rapide.

Methodes par exploration

I Il est toujours indispensable de connaıtre une encadrement[a, b] du minimum.

I On suppose toujours que f est unimodale. On choisit un pasd’exploration d . On calcule f aux points xk = a + k.d jusqu’atrouver soit une configuration f (xk) 6 f (xk+1), soit jusqu’aatteindre le point b.

I On fait a := xk−1, b := xk+1, d := ξd et on recommence.ξ < 1 est le facteur de convergence.

I On s’arrete quand d est devenu suffisamment petit.

I La methode peut s’appliquer a une fonction non unimodale.On obtient alors un optimum local sans garantie qu’il soitglobal.

L’algorithme converge

I Le nombre de pas d’exploration est au plus b−ab . L’exploration

s’arrete en un temps fini.

I Soit [an, bn] le ne intervalle d’exploration et dn le ne pasd’exploration. On a dn = dξn et bn − an 6 2dn.

I Les [an, bn] forment une suite d’intervalles emboıtes dont lalongueur tend vers 0. Ils convergent donc vers une limite c.

Optimisation a plusieurs variables

I Forme du probleme :min f (x)

x ∈ Rn

I Les inconnues sont les n composantes du vecteur x .

I La notion de fonction unimodale ne se generalise pas.

Recherche directionnelle

I On se ramene au cas a une seule variable. Pour cela on choisitun point de depart a et une direction d .

I On minimise la fonction a une variable f (a + t.d) a l’aide del’une des methodes vues plus haut.

I Si le deplacement t.d est suffisamment petit, on arrete.

I Sinon, on change de direction et on recommence.

I Le point important est le choix des directions.

Recherche suivant les axes

I On prend comme directions lesvecteurs canoniques de la base.Ceci revient a fixer n − 1 variablesde la fonction f , et a optimisersuivant la ne. On passe ensuite a lavariable suivante.

I La methode est tres lente et peutmeme ne pas converger si lescourbes de niveau sont a peu presparalleles aux diagonales.

I On peut l’accelerer en effectuant Npas puis en utilisant la directionaN − a0.

Gradient

I On suppose que la fonction f a une derivee.

I Le gradient de f au point a est le vecteur( ∂f

∂x1(a), . . . , ∂f

∂xn(a))T . On le note ∇f (a).

I On a le developpement de Taylor :

f (a + h) = f (a) + h∇f (a) + . . . .

Ceci montre que −∇f (a) est la direction dans laquelle fdecroıt le plus rapidement (steepest descent).

I D’ou l’algorithme :

1. Calculer le gradient ∇f (a).2. Minimiser la fonction a une variable f (a− x∇f (a)).3. Si le critere de convergence n’est pas verifie,

recommencer en 1.

Propriete

TheoremeDans l’algorithme ci-dessus, les directions de recherche successivessont orthogonales.

a b

Demonstration.Soit a le point de departd’une recherche unidimensionnelle suivantla direction ∇f (a) et b son point d’arrivee.La derivee de la fonction a minimiser est :

df (a− x∇f (a))

dx= −∇f (a).∇f (x).

En b cette derivee est nulle, d’ou la propriete.

Directions conjuguees

I Une matrice A de dimension n × n est definie positive si etseulement si :

∀x : xTAx > 0.

Une matrice definie positive definit un produit scalaire.

I Deux vecteurs u, v sont conjugues par rapport a A si etseulement si : uTAv = 0. C’est une generalisation de la notiond’orthogonalite.

I Soit n vecteurs d1, . . . , dn mutuellement conjugues :

i 6= j ⇒ dTi .A.dj = 0.

I Soit la fonction f (x) = 1/2xTAx + bT x + c. Si on laminimise successivement suivant les directions d1, . . . , dn, onatteint le minimum exact en n etapes.

Notations

I Soit x (k), k = 0, . . . les minima successifs.

I x (k+1) = x (k) + λkdk .

I Le gradient de f en x est Ax + b.

I D’apres la propriete ci-dessus et la conjugaison des dk , on a :

λk = −dTk (Ax (0) + b)

dTk Adk

.

I Les coordonnees de x (k+1) sont donnees par la formule :

x (k+1) = x (0) +k∑

i=1

λidi .

Preuve

LemmeEn tout point x (k) le gradient de f est orthogonal au sous-espaceengendre par d1, . . . , dk .

Demonstration.Le gradient en x (k) est Ax (k) + b = Ax (0) +

∑k−1i=1 λjAdj + b. Si on

multiplie par dTi et qu’on remplace λj par sa valeur il vient :

dTi Ax (0) −

dTi (Ax (0) + b)

dTj Adj

.(dTi Adj) + dT

i .b = 0.

TheoremeLe point x (n) est le minimum de f .

Demonstration.En effet, le gradient en x (n) doit etre conjugue de n vecteurslineairement independants, et donc doit etre nul.

Gradient conjugue

I C’est la transposition de la methode ci-dessus au cas ou lafonction f est quelconque, mais ou on sait calculer songradient.

I On part d’un point a0 et on pose d0 = −∇f (a0).I Supposons que l’on soit parvenu en un point ak avec la

direction dk . On minimise f (ak + λ.dk). Soit λk la solutionobtenue.

I On pose :

ak+1 = ak + λk .dk ,

βk =||∇f (ak+1)||2

||∇f (ak)||2,

dk+1 = −∇f (ak+1) + βkdk .

I On montre que si f est quadratique definie positive, lamethode est identique a celle des directions conjugues etconverge en n etapes.

Recherche aleatoire

I Au lieu de calculer la direction de recherche optimale pour uneapproximation quadratique de f , on peut la choisiraleatoirement en tirant n nombres au hasard dans l’intervalle[0, 1].

I La methode ne necessite pas le calcul du gradient. Ellefonctionne meme si f n’est pas derivable.

I Mais en general, sa convergence est beaucoup plus lente.

Test d’arret

I Le choix d’un test d’arret est difficile.

I Si f est derivable, son gradient doit etre nul a l’optimum. Onpeut donc utiliser ||∇f (ak)|| < ε comme test d’arret.

I Sinon, on peut arreter les iterations quand la solution nechange plus : ||ak+1 − ak || < ε.

I ε doit refleter la precision requise. Il ne doit pas etre plus petitque la precision des calculs sous peine de blocage.

I Il est prudent d’attendre que le test ait ete satisfait plusieursfois avant d’arreter.

I En general, la valeur du minimum est mieux definie que saposition.

Plan

Principaux concepts

Un exempleModelisationResolutionConclusion

Optimisation continue sans contrainte

Programmation lineaire

Programmation lineaire

min c.x

Ax + b > 0

I x est le vecteur des inconnues, de dimension n.

I A est la matrice des contraintes, de dimension m × n.

I b est le terme constant, de dimension m.

I c de dimension n est le gradient de la fonction objectif.

Autres formes d’un programme lineaire

I Un programme lineaire peut se mettre sous de multiplesformes, toutes equivalentes.

I On peut changer le sens de l’inegalite, ou passer le termeconstant de gauche a droite.

I On peut remplacer les inegalites par des egalites enintroduisant des variables d’ecart toutes positives:

Ax + b > 0 ≡ Ax + b − y = 0, y > 0

I On peut imposer que toutes les variables soient positives, enposant x := x+ − x−, x+, x− > 0

I On peut enfin transposer le programme :Ax + b > 0 ≡ xTAt + bt > 0

Polyedre Convexe

I L’ensemble P = {x | Ax + b > 0} est convexe. On l’appelleun polyedre convexe ou simplement un polyedre.

I La fonction c.x est trivialement convexe.

I Donc, si un programme lineaire a un minimum local, c’est unminimum global.

Test de faisabilite

I Pour trouver un minimum, il faut que le polyedre :

P = {x | ax = b > 0}

soit non vide, ou encore qu’il existe au moins un point x0 quisatisfasse toute les inegalites Ax + b > 0.

I On peut verifier cette condition a l’aide de l’algorithmed’elimination de Fourier-Motzkin.

I Notations : x (n) le vecteur x ampute de ses n premierescomposantes. x (0) = x .

I A(n)x (n) + b(n) > 0 le systeme obtenu apres l’elimination de nvariables.

Test de Fourier-Motzkin I / II

I Soit a eliminer x1. On reparti les contraintes en trois classes :I k ∈ I0 ssi ak1 = 0.I k ∈ I+ ssi ak1 > 0.I k ∈ I− ssi ak1 < 0.

I Dans une contrainte de I0, l’inconnue x1 est deja eliminee.

Test de Fourier-Motzkin II / II

I Une contrainte k ∈ I+ donne une borne inferieure de x1 :

x1 > −bk + ak,2x2 + . . .

ak1;

I Une contrainte k ∈ I− donne une borne superieure de x1 :

x1 6bk + ak,2x2 + . . .

−ak1;

I Pour eliminer x1, il suffit d’ecrire que chaque borne inferieureest inferieure a chaque borne superieure.

I On poursuit jusqu’a elimination de toutes les variables. Aubout de n etapes, le systeme est de la forme : b(n) > 0, qu’ilsuffit d’inspecter.

Correction

On dit que le test reussit si b(n) > 0, et qu’il echoue dans le cascontraire.

TheoremeSi le test echoue, alors le systeme initial est infaisable.

Demonstration.Supposons a contrario que le systeme initial a une solution u. Lestransformations effectuees sur les contraintes sont de simplesmanipulations algebriques valides ; on en conclu que les intervallesobtenus en comparant une borne inferieure et une borne superieure sontnon vides, et donc que le systeme A(1)x(1) + b(1) > 0 est faisable.En poursuivant l’elimination, on en arrive au systeme d’ordre n − 1, quin’a plus qu’une seule inconnue xn et qui est egalement faisable. Mais lefait que l’un des b(n) < 0 indique que l’un des intervalles de variation dexn est vide, une contradiction.

Completude

TheoremeSi le test reussit, le systeme initial est faisable.

Demonstration.On exhibe une solution du systeme initial en la construisant deproche en proche a partir de sa derniere composante. On part dusysteme

A(n−1)x (n−1) + b(n−1) > 0.

Le fait que les b(n) > 0 garantit que l’intervalle des valeurspossibles de xn est non vide. On en choisit une arbitrairement et onla reporte dans le systeme d’ordre n − 2. Ce systeme n’a plusqu’une inconnue, xn−1, dont l’intervalle des valeurs possibles estnon vide. On poursuit ainsi jusqu’a avoir donne une valeur a toutesles composantes de x .

Remarques

I Si on s’astreint a choisir a chaque pas la solution la pluspetite, i.e. la borne inferieure de l’intervalle de variation, onobtient le minimum lexicographique de P, les inconnues etantprises dans l’ordre xn, . . . , x1.

I Il n’est pas obligatoire de poursuive l’elimination jusqu’a la fin.Si on s’arrete a l’etape p, les variables de x (p) deviennent desparametres. Les conditions b(p) > 0 delimitent les valeurs desparametres pour lesquelles le systeme est faisable. Enfin, leprocede de selection ci-dessus donne la valeur parametrique dela solution.

I L’algorithme peut s’executer sans division. La combinaison dela contrainte j ∈ I+ et de la contrainte k ∈ I− se fait enmultipliant la premiere par −ak1 > 0 et l’autre par aj1 > 0 eten additionnant.

Complexite

I On evalue d’abord une borne du nombre de contraintes al’etape p,mp, soit mp = x0 + x+ × x+.

I Comme x0 + x+ + x− = mp−1, mp prend sa valeur maximumpour x0 = 0 et x+ = x− = mp−1/2, a condition quemp−1 > 4.

I Pour le cas le pire, on a donc la recurrence mp = (mp−1

2 )2

dont la solution est mn = (m2 )2

n. C’est aussi une borne du

travail a effectuer.I La complexite est donc enorme sauf pour les petits systemes.

Mais la redondance est egalement enorme, surtout si lesysteme est creux (a beaucoup de coefficients nuls).

I Enfin, il est possible que l’algorithme se termineprematurement.

I L’algorithme de Fourier-Motzkin est tres simple aprogrammer, mais il doit etre reserve a de petits problemes.

Un exemple I / II

I Soit le code :

for(j=i+1; j<n; j++)for(k=i+1; k<n; k++)

a[j][k] -= a[j][i]*a[i][k]/a[i][i];

I L’execution de ces deux boucles modifie-t-elle le termea[i][i] (le pivot) ?

I Reponse : le systeme :

i + 1 6 j < n,

i + 1 6 k < n,

i = j ,

i = k,

est il faisable ?

Un exemple II / II

+ j − i − 1 > 0,− n − j − 1 > 0,0 k − i − 1 > 0,0 n − k − 1 > 0,− i − j > 0,0 i − k > 0,+ j + k − 2i > 0.

+ k − i − 1 > 0,− n − k − 1 > 0,− i − k > 0,0 n − i − 2 > 0,0 −1 > 0.

Bingo !

Un exemple II / II

+ j − i − 1 > 0,− n − j − 1 > 0,0 k − i − 1 > 0,0 n − k − 1 > 0,− i − j > 0,0 i − k > 0,+ j + k − 2i > 0.

+ k − i − 1 > 0,− n − k − 1 > 0,− i − k > 0,0 n − i − 2 > 0,0 −1 > 0.

Bingo !

Algorithme de Fourier-Motzkin etendu

I On peut au cours de l’execution du test, garder la trace descombinaisons effectuees. On voit alors que chaque contraintedu systeme d’ordre p est une combinaison lineaire acoefficients positifs d’au plus deux contraintes du systemed’ordre p − 1.

I En generalisant, toute contrainte figurant dans l’algorithmeest combinaison lineaire positive de lignes de Ax + b. Soity > 0 le vecteur des coefficients.

I Comme dans le systeme d’ordre n toutes les variables ont eteeliminees, on en deduit yA = 0.

Lemme de Farkas

Theoreme

(∃x : Ax + b > 0) ⇔ (∀y : y > 0, yA = 0 ⇒ yb > 0).

Demonstration.De gauche a droite soit u tel que Au + b > 0 . Soit un yquelconque 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 execute l’algorithme de Fourier-Motzkinetendu. On en tire un y > 0 tel que yA = 0. On en deduit queyb > 0, ce qui veut dire que le test a reussi et qu’il est possible deconstruire un u tel que Au + b > 0.

Programmation lineaire

I On adjoint au systeme Ax + b > 0 la contrainte z > c.x , ou zest une nouvelle variable.

I On execute l’algorithme de Fourier-Motzkin en prenant soind’eliminer z en dernier.

I Si l’algorithme echoue, le probleme n’est pas faisable.

I Sinon, la valeur de z dans la solution donne la valeurminimum de c.x .

I Le reste de la solution caracterise un point ou ce minimum estatteint.

Lemme de Farkas affine

TheoremeSi le systeme Ax + b > 0 est faisable, alors :∀x : Ax + b > 0 ⇒ cx + d > 0 est equivalent a:

∃λ0, λ > 0 : ∀x : cx + d = λ0 + λ(Ax + b).

Demonstration.L’implication de droite a gauche est evidente. De gauche a droite,l’hypothese revient a dire que le systeme Ax + b > 0, cx + d < 0 n’a pasde solution. D’apres le lemme de Farkas, ceci implique l’existence dey0, λ > 0 tel que λA− y0c = 0 et λb − y0d < 0. De plus, y0 ne peut etrenul car cela impliquerait que Ax + b > 0 n’a pas de solution. On peutdonc prendre y0 = 1. On pose λb − d = −λ0, λ0 > 0 et il vient:

λ(Ax + b)− cx − d = λb − d = −λ0,

d’ou la conclusion du theoreme.

Cones

I Un cone C est un polyedre convexe dont les contraintes sontde la forme Ax > 0.

I Propriete fondamentale : u, v ∈ C, λ, µ > 0 ⇒ λu + µv ∈ C.

TheoremeL’objet {

∑i λiui | λi > 0} est un cone.

Demonstration.Il suffit de considerer le systeme :

x −∑

i

λiui = 0,

λi > 0.

et d’utiliser la methode de Fourier-Motzkin pour eliminer les λi . Ce quireste est un systeme de contraintes lineaires en x , qui definissent bien unpolyedre.

Reciproque

TheoremeTout cone C = {x | Ax > 0} est engendre par un systeme fini derayons u1, . . . , up.

Demonstration.On considere l’objet C∗ = {yA | y > 0}. C∗ est un cone dont on peutdeterminer les contraintes comme ci-dessus :

C∗ = {c | cB > 0} .

Quelque soit y > 0, yA appartient a C∗, donc yAB > 0. Comme on peutprendre pour y les m vecteurs unitaires, on en deduit AB > 0 ce quisignifie que les vecteurs colonnes de B appartiennent a C.Soit maintenant x un vecteur quelconque de C. Pour tout y > 0 on ayA.x = y .Ax > 0. En d’autre termes, pour tout c tel que cB > 0, on acx > 0. On peut donc appliquer le lemme de Farkas affine : il existe λ > 0tel que x = λB. C est donc engendre par les vecteurs colonnes de B.

Theoreme de Minkovsky

TheoremeTout polyedre P peut etre mis sous la forme : P = Q⊕ C ⊕H, ouQ est un polytope (polyedre borne), C est un cone et H un sousespace lineaire.

Demonstration.Soit P = {x | Ax + b > 0}. On considere le coneD = {x , z | Ax + zb > 0} ou z est une nouvelle variable. Il est clair queP est l’ intersection de D avec l’hyperplan {z = 1}. On construit lesrayons de D. Ceux dont la coordonnees z n’est pas nulle engendrent Q.Les rayons dont l’oppose est egalement un rayon engendrent H. Enfin,ceux qui restent engendrent C.

On peut ecrire:

P ={∑

λ.u +∑

µ.v +∑

ν.w∣∣∣ ∑

λ = 1, λ > 0, µ > 0}

Les u sont les sommets, les v les rayons et les w les lignes.

Programmation lineaire, bis

I Le minimum de c.x sous la contrainte x ∈ P = Q+ C +H estatteint en l’un des sommets de Q a condition que H soit videet que c ∈ C.

I En effet on peut ecrire :

c.x =∑

λc.u +∑

µc.v +∑

νc.w .

Puisque ν n’est pas contraint, on peut faire decroıtre c.x avolonte s’il existe un w . Il en est de meme s’il existe un v telque c.v < 0, puisque µ > 0. Si H est vide, le dernier termen’existe pas, et si c ∈ C, on minimise c.x en prenant µ = 0.Soit u0 un sommet ou c.x est minimum, et u1 un sommet ouc.u1 > c.u0. Supposons que dans l’expression de x , u1 ait uncoefficient λ1 non nul. Le point x − λ1(u1 − u0) est dans P etsa fonction objectif a diminue. On en deduit que la solutiond’un programme lineaire est l’un quelconque des sommets deQ ou c.x atteint son minimum.

Critique

I La methode ci-dessus est inefficace car il faut utiliserFourier-Motzkin pour trouver la decomposition de P, et aussiparce que le nombre de sommets peut etre tres grand (del’ordre de Cn

m, le coefficient du binome).

I Il existe un algorithme plus efficaces que Fourier-Motzkin pourdecomposer un polyedre, l’algorithme de Chernikova, mais lenombre de sommets ne change pas.

Dualite I / II

TheoremeSi les deux ensembles {x | Ax 6 b} et {y | y > 0, yA = c } sontnon 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 resulte que ` et r existent et que ` 6 r .

Dualite II / II

On peut supposer que x∗ (resp. y∗) est le point ou le maximum(resp. le minimum) est atteint. En tout point x tel que b − Ax > 0on sait que c.x∗ − c.x > 0, on peut donc appliquer le lemme deFarkas affine :

∃λ0, λ > 0 : ∀x : c.x∗ − c.x = λ0 + λ(b − Ax).

On en deduit c.x∗ = λ0 + λb et c = λA. Il en resulte que λ faitpartie de l’ensemble de droite:

r 6 λb = c.x∗ − λ0 6 `.

On en deduit ` = r .

Analyse de sensibilite

optimumcone desdirectionsadmissibles

I Variation deω(b) = max {cx | Ax 6 b} avec b ?

I Par dualite,ω(b) = min {yb | y > 0, yA = c }. Orce polyedre ne depend pas de b.Interpretation geometrique : aussilongtemps que b reste dans le conedes directions admissibles, l’optimumy∗ ne change pas. Donc:

ω(b) = y∗.b.

I Pour en savoir plus, il faut faire de laprogrammation lineaire parametrique.

Complementarite

Theoreme

∀j : y∗j .(bj − A•j .x∗) = 0.

Demonstration.

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.

Dualite generalisee

Il existe une tres grande variete de theoremes de dualite, suivant lanature des contraintes et le signe des variables. En premiereapproximation, on peut utiliser le tableau suivant :

Primal Dual

objectif (Min) second membre

second membre objectif (Max)

A AT

Contrainte i : > variable ui > 0

Contrainte i : =variable

non contrainte en signe

Variable xj > 0 contrainte j : 6Variable xj

non contrainte en signecontrainte j : =

On trouvera dans Schrijver une formulation plus precise.

Algorithme du Simplexe

c

I «Trouver le point le plus bas d’un vase».Fourier, 1828.

I Formalisation par Danzig, 1950.

Methodes externes, methodes internes

c

c

optimum

I Methodes internes : il faut connaıtre un point faisable. Onpeut arreter la recherche avant l’optimum.

I Methodes externes : il n’y a pas besoin de connaıtre un pointfaisable.

Ordre lexicographique

I Definition :

x � y = ∃k : x1,··· ,k−1 = y1,··· ,k−1, xk < yk .

I � est un ordre total.

I L’ordre par composantes n’est pas total.

I c.x < c.y n’est pas un ordre.

I D’ou l’interet de remplacer min c.x par min�.

I On peut toujours ajouter une nouvelle variable u et lacontrainte u > c.x a condition que u soit la premiereinconnue.

I Cette technique evite les problemes bien connus dedegenerescence.

Algorithme du simplexe externe ou dual

Resoudre :

min�

x

x > 0

Ax + b > 0

Tailles : x : n, A : m×n, b : m.

Generalisation :

min�

x

y = Sz + t > 0

z > 0

Au commencement,

z = x , S =

[IA

], t =

(0b

).

Invariants

I Les vecteurs colonnes de S sont lexicopositifs au demarrage etle restent tout au long de l’algorithme.

I z est un sous-ensemble de x , y . La condition z > 0 est donctoujours verifiee.

I D’une etape a l’autre, t croıt dans l’ordre lexicographique.

I Ces invariants sont verifies au debut de l’algorithme.

Cas de base

I Si t > 0, on a trouve la solution. Il suffit de faire z = 0, ce quisatisfait les contraintes. On a x = t1,··· ,n.

I De plus, c’est le minimum lexicographique : toute autre valeurpositive de z ajoute a x un vecteur lexicopositif.

I Soit ti < 0. Si ∀j : Sij 6 0, le probleme n’a pas de solution.

Changement de variable

I Soit ti < 0 et Sij > 0 (le pivot). On elimine zj en faveur de yi :

zj = yi/Sij −∑` 6=j

Si`/Sijz` − ti/Si`.

yk =∑` 6=j

(Sk` − SkjSi`/Sij)z` + Skj/Sijzj + tk − Skj ti/Sij .

I Remarquer que −ti/Sij est positif, et que Skj est lexicopositif.Donc, t croıt selon l’ordre lexicographique.

I Comme Sij > 0, le vecteur colonne j reste lexicopositif.

I Il reste a garantir que le vecteur colonne ` reste lexicopositif.

Choix du pivot

I Si Si` est negatif, il n’y a pas de probleme.

I Sinon le nouveau vecteur colonne est egal, a un coefficientpositif pres, a :

S•`/Si` − S•j/Sij .

I Il faut donc choisir j pour que Sij > 0 et que le «vecteurreduit» S•j/Sij soit le plus petit possible.

I Un tel choix est toujours possible sauf si on est dans le casd’un systeme infaisable.

Convergence

I Observer que l’etat de l’algorithme est entierement determinequand on sait quelles sont les composantes de y qui sont dansz (les variables en base).

I Or y est de taille m + n et z de taille n, il n’y a donc queCn

m+n combinaisons possibles.

I L’algorithme ne peut pas boucler, car t croıt dans l’ordrelexicographique.

I Comme Cnm+n n’est pas un polynome en n et m, l’algorithme

n’est pas polynomial.

I On peut construire des cas pathologiques qui demandent untemps exponentiel.

I Mais en pratique (et en probabilite) le nombre d’operationsest en O(n2(n + m)).

Questions numeriques I / II

I Du point de vue numerique, l’algorithme du Simplexe estanalogue a la methode de Gauss, avec une regle particulierepour le choix du pivot.

I Si l’on connaıt la matrice des inconnues de base, l’algorithmene fait qu’inverser celle-ci, tout en appliquant les memestransformations aux inconnues hors base.

I Les resultats sont donc donnes par des formules de Cramer.

I On peut faire les calculs en virgule flottante. Il y a alorsaccumulation d’erreurs d’arrondi, qui peuvent faire que lasolution finale n’est pas faisable (en particulier pour lescontraintes saturees).

I Il faut alors developper des methodes de correction. En generalla solution est faisable, mais l’optimalite n’est pas garantie.

Questions numeriques II / II

I On peut rendre la matrice des contraintes entieres, et essayerde mener les calculs exactement (algorithmes «tout entiers»).

I Les nombres a manipuler sont des determinants de Cramer.On peut donc les borner a l’aide de l’inegalite de Hadamard:

|det(A)| 6 |A1| . . . |An|,

ou les Ai sont les vecteurs colonnes (ou les vecteurs lignes) deA.

I Il en resulte que la taille des nombres a manipuler est borneepar n fois la taille du plus grand element de A. Cette borne estrarement atteinte.

I Il faut utiliser des arithmetiques en precision arbitraire, telle lalibrairie GMP.

Algorithme primal

I On prend le probleme sous la forme equivalente suivante :

min f (x) = c.x

Ax = b

x > 0

I On peut supposer que les lignes de la matrice des contraintesA sont lineairement independantes : on peut eliminer les lignesredondantes.

I A est de dimension m × n avec necessairement m < n.

Dans le cas contraire, le systeme Ax = b aurait auplus une solution et le probleme serait trivial.

Base

I Une «base» est une matrice carree n × n extraite de Ainversible. On partitionne A en deux blocs B, la base, et N lereste de la matrice. On partitionne de meme x en xB , xN et cen cB , cN .

I La solution associee a une base B est le vecteur (B−1b, 0)T . Ilsatisfait evidemment a la contrainte Ax = b.

I La base B est realisable si et seulement si la solutioncorrespondante satisfait egalement a la contrainte x > 0,c’est-a-dire si x = B−1b > 0.

I A une base realisable correspond une valeur de l’objectif,cB .B−1b.

I Est-il possible d’ameliorer cet objectif en faisant varier xN ?

Recherche de l’optimum I / III

I Si xN n’est plus nul, on a :

xB = B−1(b − NxN)

f (x) = cB .B−1b + (cN − cB .B−1N)xN

Le vecteur c = cN − cB .B−1N est le vecteur des couts reduits.

I Si xi fait partie de xN , comme il est nul on ne peut quel’augmenter pour que la solution reste faisable. Ceci faitdecroıtre f (x) a condition que c i < 0.

I Si tous les couts reduits sont positifs, on a trouve l’optimum.

I Sinon, on choisit un xi dont le cout reduit est negatif (parexemple celui dont le cout reduit est minimum).

Recherche de l’optimum II / III

I Puisque on fait croıtre xi et que les autres composantes de xN

restent nulles, la seule contrainte sur la valeur de xi estB−1(b − NxN) > 0. Il y a deux cas possibles :

I Toutes les composantes de la colonne i de B = B−1N sontnegatives. Alors xi n’est pas borne, et le minimum est −∞.

I Sinon, a chaque composante B ik > 0 correspond la bornexi 6 xk/B ik . Soit j l’indice de la plus petite de ces bornes.

I Le point correspondant a xk = 0 sauf pour k = j : xj = x j/B ij

est faisable et la valeur de f (x) est inferieure a celle du pointde depart.

Recherche de l’optimum III / III

I La base qui correspond au nouveau point courant s’obtient enremplacant dans b le colonne i par la colonne j .

I On poursuit l’algorithme en inversant la nouvelle base et encalculant la nouvelle solution et les nouveaux couts reduits.

I L’algorithme se termine si a chaque pas la valeur de l’objectifdecroıt strictement.

En effet il n’y a que Cmn bases possibles et la

condition de decroissance stricte empeche toutbouclage.

I Cependant l’algorithme peut boucler en cas de degenerescence(il semble que ce soit tres rare).

I Comme pour l’algorithme dual, on peut mener les calculs defacon incrementale (il suffit d’un seul pivot de Gauss pourinverser la nouvelle base).

Recherche du point faisable initial

I Il s’agit de trouver un point dans le polyedreP = {x | x > 0,Ax > b}. Soit 1 le vecteur dont tous leselements sont egaux a 1, et soit y un nouveau vecteur dememe taille que x . On considere le probleme :

min 1.y

x > 0

y > 0

Ax + y > b

I Il est facile de voir que le point x = 0, y = max(b, 0) estfaisable. On peut donc appliquer l’algorithme precedent.

I Si y∗ = 0, il est facile de voir que le point x∗ ∈ P.I Reciproquement, si x∗ ∈ P, alors (0, x∗) est faisable pour le

probleme augmente, donc le minimum est nul. Si inversementle minimum n’est pas nul, P est vide.