Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Mthodes et outils d'optimisation

Optimisation

[Link]@[Link] [Link]

Mathias Kleiner

Septembre 2012
[Link]

Plan du cours
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

1 2 3 4 5 6 7

Introduction Programmation linaire Nombres entiers Programmation par Contraintes Meta-heuristiques Conclusion Biblio

Plan du cours
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Meta-heuristiques

2 3 4 5

Introduction
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Problme d'optimisation = minimisation (ou maximisation) d'une fonction objectif (de cot) Cette fonction comporte des paramtres et est gnralement soumise des contraintes En fonction des caractristiques du problmes (paramtres fortement variables, domaines discrets, types de contraintes, etc.), le problme peut tre dicile rsoudre Necessite des outils avancs pour la modlisation et la rsolution
Variables (paramtres) Fonction objectif Contraintes

Premire dnition
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

fonction objectif f : A R Gnralement, A Rn , et est dni par un ensemble de contraintes Le domaine de A est appel espace de solutions, les lments de A sont appels solutions candidates une solution candidate ai qui minimise f (aj A, f (ai ) f (aj )) est appele solution optimale

Optimisation et mthodes numriques

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

il existe des mthodes numriques pour rsoudre certains problmes d'optimisation cette possibilit depends de caractristiques du problme. Par exemple, la mthode (de base) du gradient requiert que f soit doublement drivable, que le problme ne soit pas contraint, et, si l'on cherche un optimum global, que la rgion dnie par f soit convexe. dans ce cours nous tudierons plus particulirement les cas o ces techniques ne sont pas (ou dicilement) applicables En particulier, nous verrons des problmes pour lesquels l'ensemble A est discret

Exemples de problmes : revenu

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Un agriculteur possde un certain nombre d'hectares, d'engrais et d'insecticide Possibilit de planter du mas ou du bl Les cultures requirent des quantits direntes d'engrais et d'insecticide Les cultures fournissent un revenu dirent Objectif : maximiser le revenu net

Exemples de problmes : revenu

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Un restaurateur possde des oursins, crevettes et hutres Dispose de deux types d'assiettes Objectif : dterminer le nombre d'assiette de chaque type proposer pour maximiser le revenu net

Exemples de problmes : ux de transport

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Une cooprative laitire eectue quotidiennement le ramassage de lait dans direntes fermes Objectif : eectuer la tourne la plus courte

Exemples de problmes : couverture de charge

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Courbe de charge (compagnie arienne, supermarch, pages, . . .) Objectif : Assurer la couverture avec un minimum de personnel

Exemples de problmes : emploi du temps

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Une universit doit eectuer un certain nombre de cours un certain nombre d'lves, avec un certain nombre d'enseignants-chercheurs contraintes de prcdences de cours, salles, dsidratas Objectif : trouver une solution !

Exemples de problmes : rangement

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

On dispose de containers et d'lments de tailles direntes ranger dans ces containers (pour envoi) Objectif : trouver un arrangement pour minimiser le nombre de containers

Exemples de problmes : rseaux

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

On souhaite approvisionner une rgion en eau potable dirents consommateurs, dirents points de pompage contraintes de pression Objectif : minimiser le nombre points de pompage et la longueur du rseau

Exemples de problmes : conception produit

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Fabrication d'un systme de traction Dirents matriaux, contraintes de traction Objectif : minimiser le cot de fabrication

Exemples de problmes : sparation d'un stock

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

On dispose de rouleaux de tissu d'une certaine longueur On souhaite les couper pour obtenir des bandes de longueurs direntes donnes Objectif : minimiser le nombre de rouleaux acheter

Exemples de problmes : ordonnancement

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Planier des tches sur des machines de production Contraintes de prcdences sur les tches, dlais sur machines, . . . Objectif : minimiser le temps de compltion des tches

Exemples de problmes : autres

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Euler : "Il n'y a rien dans le monde qui ne se ralise sans la volont de minimiser ou maximiser quelque chose." Encore beaucoup d'autres domaines d'application :

Economie/Finances Biologie Transport Organisation/Logistique/SCM Robotique/Intelligence articielle Ingnierie ...

Caractristiques
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Continuit, linarit, bornes de la fonction de cot ? Variables discretes ? Domaine des variables ? mono-objectif, multi-objectifs ? Contraintes linaires ? Quadratiques ? Connaissances stochastiques (i.e pseudo-alatoires) ou incertaines les caractristiques d'un problme inuent sur :
la modlisation (puissance expressive ncessaire) les techniques de rsolution la dicult (ecacit des mthodes/algorithmes)

Complexit
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Dicult de rsolution d'un problme par un algorithme/mthode : On s'intresse un ordre de grandeur en fonction des donnes en entre (indpendant de la puissance machine) :
linaire ou pseudo-linaire polynomial exponentiel/factoriel (on parle de problmes NP-diciles) (in)dcidable, (in)calculable quantit d'oprations/tapes eectuer (complexit en temps) quantit d'informations stocker (complexit en espace)

Thorie des automates (deterministes ou non-deterministes) par [Link] (machine de Turing)

Complexit : exemple
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Soit un graphe G = (V, E)

G est-il connexe ?

Complexit : exemple
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Soit un graphe G = (V, E) G possde-t-il un chemin hamiltonien ?

Complexit : exemple
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Soit un graphe G = (V , Ep ) complet

Quel chemin passant exactement une fois par chaque point minimise le poids total ? 69 villes nombre 100 chires !

Complexit : consquences
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Temps de rsolution d'un problme selon sa complexit (10ns par tape)

O (n) O (n 2 ) O (n 3 ) O (e n ) O (n!)
Not.

lineaire quadratique(P) cubique(P) exponentielle factorielle

Complexite

n=20 200ns 4s 80ms 10ms 770ans

n=50 500ns 25s 1.25ms 130jours 1048 ans

n=250 2.5s 625s 156ms 1059 ans ?

n=1000 10s 10ms 10s ? ?

n=104 100s 1s 2.7h ? ?

n=106 10ms 2.8h 316ans ? ?

ce n'est pas anodin ! distingue complexite pire des cas, en moyenne, en pratique il existe des classes polynomiales pour des problmes NP-diciles sous certaines conditions

Processus d'optimisation
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Processus d'optimisation
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Analyse du problme Modlisation et choix de mthode Rsolution Interprtation des rsultats

Processus d'optimisation : Analyse du problme

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Comprhension du systme Dnition des objectifs, du champ de couverture Obtention des donnes ...

Processus d'optimisation : Modlisation

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Choix d'un langage (formel), de la mthode Traduction du problme : paramtres, domaines, contraintes, incertitude, . . . simplication : rsultat d'un consensus entre acteurs ...

Processus d'optimisation : Rsolution

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Mise en oeuvre algorithmique, utilisation d'un outil/solveur Analyse de la robustesse, pertinence des rsultats ...

Processus d'optimisation : Interpretation

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Interprter les rsultats dans le monde rel Prsenter aux acteurs ...

Processus d'optimisation : Mise en oeuvre

Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Mise en oeuvre oprationnelle Suivi des impacts, actions correctives peut donner lieu la dnition d'un nouveau problme !

Mthodes d'optimisation
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Mthodes gnriques : Programmation linaire (modlisation sous forme d'quations linaires) Programmation en nombres entiers (variables entires) Programmation quadratique Programmation dynamique Mthodes numratives (PPC) : SAT, CSP, Models Mta-heuristiques (optimisation stochastique) ... domaines de recherche/activit : recherche oprationnelle, intelligence articielle, . . .

Mthodes d'optimisation
Mthodes et outils d'optimisation Optimisation Introduction Introduction Exemples Caractristiques Complexit Processus Mthodes Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Mais pour des cas particuliers, il peut exister des mthodes ddies ecaces (optimales ou approches). Par exemple : Sac dos, sous conditions : algorithme glouton Ordonnancement : mthode du chemin critique (PERT) Ordonnancement 2 machines : algorithme de Johnson ... longue liste en volution : requiert une veille technologique ou une tude approfondie, par exemple lorsque la rsolution d'un problme par les mthodes gnriques n'est pas satisfaisante (e.g. temps de calcul trop important).

Plan du cours
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

1 2

Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes

3 4

Dnition
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Techniques d'optimisation pour des problmes caractriss par :

une fonction objectif linaire soumise des contraintes d'galit et/ou d'ingalits linaire

modlisation par un ensemble d'quations linaires

on peut noter que les contraintes dnissent alors un polytope convexe

Forme canonique
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Denition maximiser soumis c x Ax b, x 0

o x est un vecteur de variables, c et b des vecteurs de coecients, et A une matrice de coecients. D'autres formes (minimisation, variables ngatives, etc.) peuvent tre recrites de manire quivalente en forme canonique.

Exemple de l'agriculteur
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Un agriculteur possde un certain nombre d'hectares, d'engrais et d'insecticide Possibilit de planter du mas ou du bl Les cultures requirent des quantits direntes d'engrais et d'insecticide Les cultures fournissent un revenu dirent Objectif : maximiser le revenu net

Exemple de l'agriculteur
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Un agriculteur possde un certain nombre d'hectares (T ), d'engrais (E ) et d'insecticide (I ) Possibilit de planter du mas (x1 ) ou du bl (x2 ) Les cultures requirent des quantits direntes d'engrais et d'insecticide (E1 ,I1 ,E2 ,I2 ) Les cultures fournissent un revenu dirent (S1 ,S2 ) Objectif : maximiser le revenu net

Exemple de l'agriculteur
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Maximiser soumis

S1 x1 + S2 x2 x1 + x2 T E1 x1 + E2 x2 E I1 x1 + I2 x2 I x1 0, x2 0

(fonction objectif) (limite terrain) (limite engrais) (limite insecticide) (terrain positif !)

Exemple de culture
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Culture de courgettes et de navets 8l d'engrais A disponible 2l /m2 pour courgettes, 1l /m2 pour navets 7l d'engrais B disponible 1l /m2 pour courgettes, 2l /m2 pour navets 3l anti-parasite disponible 1l /m2 pour navets Objectif : produire le maximum (en poids) de lgumes, sachant que rendements = 4kg /m2 courgettes, 5kg /m2 navets

Exemple de culture
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Variables de dcision : xc (surface de courgettes), xn (surface de navets) Maximiser soumis 4xc + 5xn 2xc + xn 8 xc + 2xn 7 xn 3 xc , xn 0 (fonction objectif) (limite A) (limite B) (limite anti-parasite) (terrain positif !)

Caractristiques
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Simplex = polytope N + 1 sommets (pour N dimensions) Caractristiques du problme :

chaque ingalit du PPL n variables dnit un demi-espace dans un espace Euclidien n dimensions leur intersection est l'ensemble des solutions candidates l'ensemble des points pour lesquels la fonction objectif ralise la valeur v est un hyperplan la fonction objectif tant linaire et concave sur le polytope, elle admet un minimum sur (au moins) un de ses sommets

Interprtation gomtrique
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Culture de courgettes et de navets

Interprtation gomtrique
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Les lignes de niveau (f = constante) sont des droites parallles maximum en 1 sommet ou en 1 arte

Interprtation gomtrique
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Les lignes de niveau (f = constante) sont des hyperplans anes

Solutions PPL
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

La rgion admissible peut-tre :

vide pas de solution (optimale) non vide et borne 1 ou solutions optimale non vide et non borne 0 ou 1 ou solutions optimales

Algorithme naf de rsolution

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Algorithme naf : numrer tous les sommets du polytope, valuer f , prendre le minimum nombre important de sommets pas ecace (confre complexit)

Algorithme du Simplexe
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Algorithme cre par George Dantzig en 1947 Ide : partir d'un sommet, chercher un sommet voisin qui amliore l'objectif Denition (Principe d'amlioration locale) Soit x0 non optimum, alors il existe un sommet voisin x tel que f (x ) > f (x0 )
Mthode de rsolution itrative : on part d'un

sommet quelconque, on trouve un sommet voisin qui amliore l'objectif (rgle de pivotage), on ritre Note : on est pass d'un problme continu un problme discret !

Algorithme du Simplexe - Culture

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Illustration courgettes et navets

Algorithme du Simplexe - tapes

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Necessaire de passer en forme standard : galits (variables d'cart) plus de dimensions mais manipulations algbriques plus simples Maximiser 4xc + 5xn Maximiser 4xc + 5xn soumis 2xc + xn 8 soumis 2xc + xn + e1 = 8 xc + 2xn 7 xc + 2xn + e2 = 7 xn 3 xn + e3 = 3 xc , xn 0 xc , xn , e1 , e2 , e3 0

Algorithme du Simplexe : histoire

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Application aprs-guerre :
Oprations Vittles et Plainfare pour ravitaillement de la trizone pendant le blocus de Berlin par pont arien (23 juin 1948  12 mai 1949) Simplexe excut la main (des milliers de variables), jusqu' 12 000 tonnes de matriel par jour !

1975 : prix Nobel conomie Kantorovitch aujourd'hui : PL largement rpandue de nombreux domaines d'application

Problme Dual
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Soit P un problme de PL, appel problme primal Il existe un problme D , appel dual, utilisant les mmes donnes mais un objectif dirent (inverse) Ce problme a une illustration conomique importante : si P est un problme de minimisation de cot pour un acheteur, D est un problme de maximisation du prot pour un vendeur tout en restant comptitif

Exemple : Primal
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

une famille utilise 6 produits alimentaires comme source de vitamine A et C produits (units/kg) demande 1 2 3 4 5 6 (units) vitamine A 1 0 2 2 1 2 9 vitamine B 0 1 3 1 3 2 19 prix/kg 35 30 60 50 27 22 Objectif : minimiser le cot total

Exemple : Dual
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

un producteur de cachets de vitamines synthtiques veut convaincre la famille d'acheter des vitamines Quel prix de vente wA et wB ?
pour tre comptitif et maximiser le prot

Exemple : Dual
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Maximiser soumis

9wA + 19wB wA 35 wC 30 2wA + 3wc 60 2wA + wc 50 wA + 3wc 27 2wA + 2wc 22 wA , wC 0

(fonction objectif) (produit 1) (produit 2) (produit 3) (produit 4) (produit 5) (produit 6) (prix positif)

Dualit : gnralisation conomique

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

produit j cot i

ressource i aij bi

demande j cj

Primal (demandeur) : quelle quantit xi de ressource i acheter pour satisfaire demande cot minimum min bi xi s .c . aij xi cj
j

Dual (vendeur) : quel prix wj proposer les produits pour maximiser le prot tout en restant comptitif max cj wj s .c . aij wi bi
i

Dualit : proprits
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Le dual du dual est quivalent au primal Thorme de dualit faible (pour prouver l'optimalit) Denition Pour chaque paire de solutions admissibles x de P et w de D cx wb
Si le primal est non-born, le dual est insatisable (et

inversement). Thorme de dualit forte (pour garantir qu'une preuve d'optimalit est possible) Denition Si P et D ont des solutions, alors cx w b Ecarts complmentaires (pour trouver une solution optimale du dual connaissant celle du primal)

Autres mthodes
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Amliorations du simplexe, barrires Algorithme de l'ellipsode [Khachiyan, 1979] Mthodes du point intrieur [Karmakar, 1984] Versions spciques un problme particulier, combinaisons ...

Outils
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Dnition Exemples Caractristiques Simplexe Dualit Autres mthodes Outils Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion

Outils non-commerciaux et/ou libres : glpk, CLP, Cassowary, SciLab, . . . Outils commerciaux : ILOG/IBM CPLEX, MatLab (opt toolbox), Mathematica, Excel, . . .

Plan du cours
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

1 2 3

Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-and-Bound Autres mthodes Outils Programmation par Contraintes

Introduction
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Programmation linaire en nombres entiers (PLNE) Variables de dcision discrtes (entiers, boolens) (contre-intuitivement ?) Pas de mthode gnrale ecace de rsolution branch-and-bound, cutting-planes, branch-and-cut, ... on entre dans l'optimisation combinatoire

Modlisation gnrique de l'optimisation combinatoire

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Un ensemble E = {e0 , . . . , en } de solutions candidates (espace de recherche) o ei est une assignation d'un ensemble de variables E , gnralement dni par des contraintes, a une cardinalit importante (ex. : n = 2m o m est dni par la taille du problme) objectif (maximisation) : ei E tel que j , f (ei ) >= f (ej )

Modlisation PLNE canonique

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Forme PLNE canonique : maximiser soumis c x Ax b x Zn

x 0

Exemples : rangement (packing)

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

On dispose de containers et d'lments de tailles direntes ranger dans ces containers (pour envoi) Objectif : trouver un arrangement pour minimiser le nombre de containers

Exemples : rangement 1D (bin packing)

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

un dmnageur souhaite empaqueter des objets en minimisant le nombre de cartons (de capacit C = 6) Objectif : trouver un arrangement pour minimiser le nombre de cartons Objets : livre (2), livre (2), pull (3), chaussettes (1), chaussures (2), assiettes (5), verres (6)

Exemples : rangement 1D (bin packing)

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

xij = 1 si l'article i est rang dans la bote j , 0 sinon yj = 1 si la bote j est utilise, 0 sinon minimiser soumis
n i =1 n j =1

yj

ci xij 6yj , j = 1, . . . , n
n j =1

xij = 1, i = 1, . . . , n

xij {0, 1}, yj {0, 1}

Exemples : sparation d'un stock (cutting-stock)

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

On dispose de rouleaux de tissu d'une certaine longueur On souhaite les couper pour obtenir des bandes de longueurs direntes donnes Objectif : minimiser le nombre de rouleaux acheter Gnralisation du bin packing

Exemples : sparation d'un stock (cutting-stock)

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

j = {0, . . . , m} commandes, avec j requiert quantit qj de pices de tissu i = {0, . . . , n} combinaisons de dcoupe, avec xi le nombre de fois o elle est utilise, et ci son cot (dchet) aij le nombre de fois o la commande j apparait dans la combinaison i minimiser soumis
n i =1 n i =1

ci xi

xi aij qj j = 1, . . . , m xi , aij , qj Z, xi 0

Exemple : Illustration cutting-stock

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

une machine peut produire des pices matres de 5600mm de largeur les commandes sont les suivantes : largeur quantit 1380 22 1520 25 1560 12 1710 14 1820 18 1880 18 1930 20 2000 10 2050 12 ... ...

Exemples : sparation d'un stock (cutting-stock)

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Direntes modlisations selon donnes/objectifs (nombre de pices matres, changements d'outil de dcoupe, . . .) diverses applications
1D : dcoupe de cables, matriaux 2D : dcoupe de verre, tissu liens avec d'autres problmes types

Exemples : sac--dos
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Remplir son sac--dos (max. 3kg) pour une randonne objet utilit poids carte 10 200 gourde A 7 1500 gourde B 3 1500 pull 6 1200 k-way 2 500 tomme 4 800 fruits secs 5 700 Objectif : maximiser l'utilit pour un poids limit

Exemples : sac--dos
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

xi = 1 si l'objet i est choisi, 0 sinon ui utilit de l'objet i , wi son poids maximiser soumis
n n i =1

ui xi

wi xi 3 i =1 xi {0, 1}

Exemples : sac--dos
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Problme classique : utiliser au mieux une capacit, allocation de ressources Nombreuses variantes (utilit dirente selon conteneur, combinaisons augmentent l'utilit, . . .) Applications
nances : gestion de portefeuille gestion de personnel pour un projet ...

Techniques de modlisation : ensembles discrets

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

x doit prendre sa valeur parmi P = {p1 , . . . , pk } yi {0, 1}, 1 pour x = pi

k i =1

yi = 1
k

x=

xi {0, 1}

i =1

pi yi

Techniques de modlisation : propositions logiques

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

x et y deux variables boolennes x y : contrainte : x y x y : contrainte : x + y 1

Techniques de modlisation : ordonnancement

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Deux tches de dure di et dj doivent tre usines sur une mme ressource ti et tj le temps de dpart d'usinage ti + di tj + M (1 yij ) tj + dj ti + M (yij ) yij {0, 1}

Techniques de modlisation : linarisation

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

linariser un terme quadratique simple ex. xx avec x , x {0, 1} introduit une variable y , y = 1 ssi x = 1 et x = 1 x y x y x +x 1y yij {0, 1}

Relaxation linaire
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Ide : peut-on rsoudre un PLNE X en rsolvant le PL associ ? relaxation linaire denit un polydre P = {X Rn |Ax b} Denition Un PL P est une formulation de X ssi X = P Zn Question : quel lien entre l'optimum du PL et l'optimum du PLNE ?

Relaxation linaire : illustration

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Relaxation linaire : illustration

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

peu d'indications, on ne peut pas simplement

rsoudre le PL associ

Mthodes numratives
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Ide : numrer les solutions possibles (nombre ni), les valuer, conserver la meilleure Problme : ce nombre peut tre trs important (car exponentiel) pas ecace C'est le challenge de l'optimisation combinatoire ! Eliminer a priori des solutions, sans les valuer explicitement

Branch-and-Bound : principe
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

On veut rsoudre z = {max cx |x X } Partitionne X en (X1 , X2 ) , z } Alors z = max {z1 2

Branch-and-Bound : principe
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

> z , alors il est inutile d'explorer X car il ne Si z1 2 2 contient pas de solution optimale

Comment dterminer de ne pas explorer X2 sans calculer ? z2 : borne suprieure estimation (par excs) de z2

Proprit de la relaxation linaire

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Soit un problme de maximisation, son PLNE IP , sa et relaxation linaire L et leurs optimums respectifs ZIP ZL La proprit suivante est vrie :
le PL fournit une borne suprieure au PLNE !
ZIP ZL Si ZL est un entier, c'est l'optimum du PLNE

Branch-and-Bound : principe
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

On partitionne l'ensemble X en {X1 , . . . , Xn } On calcule les bornes suprieures B (Xi ) de l'optimum pour chaque Xi Si B (Xi ) meilleure solution trouve, on lague Sinon on dcoupe rcursivement Xi arbre de recherche implicite

Branch-and-Bound : dcoupe
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Rsolution de la RL sur X (P ) si x non entier, on branche sur une variable non entire

Branch-and-Bound : dcoupe
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

X1 = x X et xi a X2 = x X et xi a + 1

Branch-and-Bound : dcoupe
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Recherche de la meilleure solution sur X2 RL sur X2 (P2 ), dcoupe, RL sur X21 (P3 ) et X22 (P4 )

Branch-and-Bound : dcoupe
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Recherche de la meilleure solution sur X1 RL sur X1 (P1 ), dcoupe, RL sur X11 (P5 ) et X12 (P6 )

Branch-and-Bound : dcoupe
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

, x ) x = max (x1 2

Branch-and-Bound : laguage
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

On lague une branche si :

La RL n'a pas de solution (discard) La RL a une solution entire (optimum) La borne sup. est infrieure la meilleure solution actuelle (discard)

Branch-and-Bound : exemple
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

maximiser z = 2x1 + 3x2 soumis 5x1 + 7x2 35 4x1 + 9x2 36 x1 , x2 0 Z

Branch-and-Bound : exemple
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

maximiser z = 2x1 + 3x2 soumis 5x1 + 7x2 35 4x1 + 9x2 36 x1 , x2 0 Z

Autres mthodes
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Amliorations (choix des partitions, ordre de rsolution, . . .) Coupes (cuts), plans scants (cutting-planes) Contraintes redondantes (symmtries) Mthodes mixtes (branch-and-cut) Versions spciques un problme particulier ...

Outils
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Introduction Modlisation Exemples Techniques de modlisation Branch-andBound Autres mthodes Outils Programmation par Contraintes Metaheuristiques

Outils non-commerciaux et/ou libres : glpk, LP_SOLVE, SciLab, . . . Outils commerciaux : ILOG/IBM CPLEX, MatLab (opt toolbox), Mathematica, Excel, . . .

Plan du cours
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

1 2 3 4

Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Meta-heuristiques

Introduction
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Programmation par contraintes = mthode de modlisation et de rsolution Variables de dcision et leur domaine Contraintes de dirents types, faciles vrier indpendamment, libert de modlisation Mthodes de rsolution numratives

Du Sudoku la PPC
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Principes de la PPC
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Raisonnement par limination : on ne cherche pas directement la valeur d'une variable mais ses valeurs possibles (rduction du domaine) Raisonnement numratif : on essaie direntes solutions par tapes successives de construction (arbre de recherche) Raisonnement local : on considre les contraintes indpendamment Raisonnement par propagation : lorsque le domaine d'une variable change, on s'intresse aux contraintes qui dpendent cette variable (propagation)

Modlisation gnrique de l'optimisation combinatoire

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Un ensemble E = {e0 , . . . , en } de solutions candidates (espace de recherche) o ei est une assignation d'un ensemble de variables E , gnralement dni par des contraintes, a une cardinalit importante (ex. : n = 2m o m est dni par la taille du problme) objectif (maximisation) : ei E tel que j , f (ei ) >= f (ej )

Modlisation SAT
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Un problme SAT est un doublet {X , C } o : X est un ensemble de variables boolennes (littraux) {x0 , . . . , xn } C est un ensemble de contraintes sous la forme CNF (forme normale conjonctive)
CNF = conjonction de clauses clause = disjonction de littraux

Dans un problme d'optimisation, on ajoute une fonction objectif f (ei ) o ei est une solution candidate (i.e. une assignation d'une valeur chaque variable)

Modlisation SAT : exemple

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Ringo Etoile, musicien londonien, appelle Scotland Yard pour signaler que son appartement vient d'tre cambriol. La police a tabli les faits suivants :
Il y a trois suspects : John, Paul et Georges, et personne d'autre ne peut tre coupable Si John est coupable, alors il a un et un seul complice Si Paul est innocent alors Georges l'est aussi Si Georges est innocent alors Paul l'est aussi Si il y a exactement deux coupables, alors John est l'un d'entre eux

Modlisez puis dessinez l'arbre de recherche

Modlisation SAT : exemple

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

X = {J,P,G} C = ( mettre sous forme CNF)

J P G J ((P G ) (G P )) P G G P ((J P G ) (J P G ) (J P G )) J

Modlisation CSP
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Un problme CSP est un triplet {X , D , C } o : X est un ensemble de variables {x0 , . . . , xn } D = {d0 , . . . , dn } est un ensemble de domaines de valeurs (discrets ou continus) correspondant aux variables de X C est un ensemble de contraintes (logiques, mathmatiques, etc.) Dans un problme d'optimisation, on ajoute une fonction objectif f (ei ) o ei est une solution candidate (i.e. une assignation d'une valeur chaque variable)

Modlisation CSP : exemple

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

On considre l'addition suivante : S E N D + M O R E = M O N E Y o chaque lettre reprsente un chire dirent compris entre 0 et 9. On souhaite connaitre la valeur de chaque lettre, sachant que la premire lettre de chaque mot reprsente forcment un chire dirent de 0.

Modlisation CSP : exemple

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Modlisation A (horizontale) : X = {S , E , N , D , M , O , R , Y } D (S ) = D (M ) = {1, 2, 3, 4, 5, 6, 7, 8, 9} D (E ) = D (N ) = D (D ) = D (O ) = D (R ) = D (Y ) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} C 1 : 1000 S + 100 E + 10 N + D + 1000 M + 100 O + 10 R + E = 10000 M + 1000 O + 100 N + 10 E + Y C 2 : all dierent ({S , E , N , D , M , O , R , Y })

Modlisation CSP : exemple

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Modlisation B (verticale) : X = {S , E , N , D , M , O , R , Y } D (S ) = D (M ) = {1, 2, 3, 4, 5, 6, 7, 8, 9} D (E ) = D (N ) = D (D ) = D (O ) = D (R ) = D (Y ) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} C 1 : D + E = Y + 10 R 1 C 2 : R 1 + N + R = E + 10 R 2 C 3 : R 2 + E + O = N + 10 R 3 C 4 : R 3 + S + M = O + 10 M C 5 : all dierent ({S , E , N , D , M , O , R , Y })

Types de contraintes
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Contraintes par extension (liste des valeurs possibles) ou par intention (formule logique ou mathmatique) l'ordre n'a pas d'importance Dclaratives (pas d'algorithme de vrication), non diriges (x 2y = z ), pas restreintes une forme particulire (i.e. linaire) Arit d'une contrainte = nombre de variables impliques (x 2 = 4, est pair (x ), x = y ) Contraintes globales (toutes dierentes (E )) Contraintes quanticatives, existentielles pour des problmes avancs

Jeu des reines

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

But : Placer 4 reines sur un chiquier 4x4 sans qu'elles se menacent.

Modlisation ?

Jeu des reines : modlisation A

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

But : Placer 4 reines sur un chiquier 4x4 sans qu'elles se menacent. Variables : Associe chaque reine i sa position en lignes (L = i =1..4 Li ) et en colonnes (C = i =1..4 Ci ) X = L C ) Domaines : i {1, 2, 3, 4}DLi = DCi = {1, 2, 3, 4} Contraintes : CoL = {i , j {1, 2, 3, 4}, i = j , Li = Lj } CoC = {i , j {1, 2, 3, 4}, i = j , Ci = Cj } CoD M = {i , j {1, 2, 3, 4}, i = j , Ci + Li = Cj + Lj } CoD D = {i , j {1, 2, 3, 4}, i = j , Ci Li = Cj Lj }

Jeu des reines : modlisation B

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

But : Placer 4 reines sur un chiquier 4x4 sans qu'elles se menacent. Variables : On place une reine par colonne, donc on associe une reine i sa position en lignes X = {X1 , X2 , X3 , X4 }) Domaines : i {1, 2, 3, 4}DXi = {1, 2, 3, 4} Contraintes : CoL = {i , j {1, 2, 3, 4}, i = j , Xi = Xj } CoD M = {i , j {1, 2, 3, 4}, i = j , Xi + i = Xj + j } CoD D = {i , j {1, 2, 3, 4}, i = j , Xi i = Xj j }

Jeu des reines : modlisation C

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

But : Placer 4 reines sur un chiquier 4x4 sans qu'elles se menacent. Variables : Une variable par case domaine Booleen modlisation SAT

Jeu des reines : plusieurs modlisations

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Il existe (toujours) plusieurs modlisations, laquelle est la meilleure ?

Celle qui correspond le mieux la ralit La plus intuitive, la plus simple trouver La plus ecace (voir rsolution)

Coloriage de cartes
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

But : Colorier une carte sans que deux pays contigus aient la mme couleur. Applications : allocation de ressources, emploi du temps, ordonnancement, . . .

Modlisation ?

Coloriage de cartes
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

But : Colorier une carte sans que deux rgions contigues aient la mme couleur. Applications : allocation de ressources, emploi du temps, ordonnancement, . . . Variables : une variable Xi pour chaque rgion Domaines : Di = {bleu , jaune , rouge , vert } Contraintes : en extension, ou, i , j tq voisines (i , j ), Xi = Xj

Rsolution nave
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Mthode nave :
on numre les aectations totales on vrie si elles sont consistantes

pas ecace !

Rsolution par tapes

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Construire une aectation totale par incrmentation d'aectations partielles (arbre de recherche) Revenir en arrire si une aectation partielle est inconsistante (backtrack) Restreindre les domaines des variables chaque tape (anticipation par propagation locale des contraintes) utiliser des heuristiques utiliser connaissances sur le problme (symtries, . . .) ...

Arbre et backtrack : exemple des reines

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Construire une aectation totale par incrmentation d'aectations partielles (arbre de recherche) Revenir en arrire si une aectation partielle est inconsistante (backtrack)

Anticipation
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Restreindre les domaines des variables chaque tape (anticipation/ltrage par propagation locale des contraintes) De manire gnrale, ltre consiste modier le domaines des variables non aectes en fonction de l'aectation partielle (A) courante
consistance de noeud (ou 1-consistance) : on enlve de D (Xi ) toute valeur v telle que A (Xi , v ) est inconsistante consistance d'arc (ou 2-consistance) : on enlve de D (Xi ) toute valeur v telle que qu'il existe une variable Xj dont toutes les valeurs donnent A (Xi , v ) (Xj , w ) inconsistante consistance de chemin (ou 3-consistance) ... Si il reste k variables aecter, quoi correspond la k consistance ?

Anticipation : exemple des reines

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Restreindre les domaines des variables chaque tape (anticipation/ltrage par propagation locale des contraintes) 1-consistance

Anticipation : exemple des reines

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Restreindre les domaines des variables chaque tape (anticipation/ltrage par propagation locale des contraintes) 2-consistance

Heuristiques
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Utiliser des heuristiques = parcourir l'arbre dans un ordre prfrentiel Prfrence non systmatique (sinon le problme est linaire !), mais trs ecace Types : Cration de l'ordre :
Heuristiques de variables (min-domain, max-constraints) Heuristiques de valeurs statique (une fois pour toutes au dpart) dynamique ( chaque tape)

Connaissances des symtries

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Utiliser connaissances sur le problme : symtries

manuel durant la modlisation automatique durant la recherche

Variantes
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

MAX-CSP : satisfaire un maximum de contraintes VCSP : valuation sur les contraintes, maximiser Conditional CSP : contraintes actives sur certaines conditions Dynamic CSP : ajout dynamique de variables au cours de la recherche ...

Outils
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Introduction Modlisation Exemples Rsolution Outils Metaheuristiques Conclusion Biblio

Outils non-commerciaux et/ou libres : Comet, Gecode, Choco, Cassowary, GNU Prolog, SWI Prolog, ECLiPSe (Prolog), Alloy (R-SAT), . . . Outils commerciaux : ILOG/IBM CPLEX, CHARME, CHIP v5, . . .

Plan du cours
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

1 2 3 4 5

Introduction Programmation linaire Nombres entiers Programmation par Contraintes Meta-heuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques

Introduction aux mthodes incompltes

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

Constat : pour de nombreux problmes (taille), aucune technique vue precdemment n'est ecace Les techniques tudies sont compltes (ou exactes) : si elles ne fournissent pas de solution, la solution n'existe pas Ide : peut-on trouver des mthodes incompltes qui soient ecaces dans certains cas ? Parmis ces mthodes, on trouve les mta-heuristiques

Introduction aux mta-heuristiques

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

Principe : on va parcourir partiellement l'espace de recherche, avec des heuristiques plus complexes Plusieurs manires de parcourir partiellement :

locale) repartir de la racine en ayant emmagasin de la connaissance ...

sauter d'une aectation totale une autre (rparation

Toutes ces mthodes se reposent sur des techniques alatoires (ou stochastiques) La plupart de ces mthodes sont inspires du monde rel (nature et notamment animaux) et de l'intelligence collective Nous n'en verrons qu'une toute petite partie

Recuit simul
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

Le recuit simul est une mthode inspire de la metallurgie Energie E du systme = Fonction minimiser Temperature T = paramtre contrlant la diversication Determine conditions initiales : E0 et T0 (alatoirement leve) A chaque tape :
Modie solution courante et value la variation d'nergie E
Si

E < 0,

elle est applique

Sinon, elle est applique avec une probabilit de (rgle de Metropolis)

E e T

Modication de la temprature : par paliers ou par une loi de dcroissance (Ti +1 = Ti avec < 1)

Particle Swarm Optimization

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

PSO = Particle Swarm Optimization un essaim de particule se dplace dans un espace n dimensions (n = nombre de variables) Une particule est caractrise par sa position (xi ) et sa vitesse (vi ) Initialise chaque particule pseudo-alatoirement (distribution uniforme) chaque tape, chaque particule se dplace (modication du vecteur vitesse et application la position) en fonction de 3 critres :
son meilleur score (pi ) le meilleur score de toutes les particules (g ) facteur alatoire

vi = vi + p rp (pi xi ) + g rg (g xi ) o , p , g sont des paramtres globaux

PSO : exemple 2D
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

Applications courantes : choix ou adquation de paramtres

PSO : exemple 2D
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

Local best Global best

Random factor

Applications courantes : choix ou adquation de paramtres

Ant Colony Optimization

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

ACO = Ant Colony Optimization Algorithme inspir de l'observation des colonies de fourmis : capacit trouver le chemin le plus court vers une source de nourriture Premire application algorithmique [Dorigo] : recherche du plus court chemin dans un graphe aux artes pondres Etendu depuis divers problmes d'optimisation, notamment les problmes de satisfaction de contraintes

???

20%

80%

Ant Colony Optimization : PPC

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

A chaque tour, un certain nombre de fourmis articielles parcourent l'espace de recherche an de construire une solution (par exemple, un graphe) Le trajet d'une FA (ici un choix xy ) est inuenc par :
une heuristique (xy ) les phromones dposes par toutes les FA (xy ) facteur alatoire (, )

k = pxy

xy xy

Aprs valuation de la solution, chaque FA dpose des phromones sur son trajet en fonction de la qualit de la k) solution (xy Les phromones s'vaporent () au cours du temps an d'oublier les mauvaises solutions k xy = (1 )xy + xy

z xz xz

Algorithmes gntiques
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

Les algorithmes gntiques sont inspirs de la slection naturelle Oprations (slections, enjambements/croisements, mutations) appliques une population de solutions candidates Principe : gnration d'une population initiale (alatoirement), puis, itrativement :
Evaluation puis selection (direntes mthodes) des meilleurs individus Croisements (direntes possibilits) par paires Mutations sur une faible partie de la population rsultante

Comment reprsenter les solutions sous forme de gnes (i.e squence de valeurs) ? importance du codage

Algorithmes gntiques : tapes

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

Selection : rang, roulette, tournoi, uniforme Croisements : place de l'enjambement Mutations : i.e. permutations

Algorithmes gntiques : exemple du VC

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

Exemple du voyageur de commerce Codage : un entier par ville, squence : suite ordonne de villes visits
S1 = 1 0 5 3 2 7 4 6 S2 = 7 1 3 5 6 2 0 4 Croisements : S1 = 1 0 5 3 2 7 6 4 S2 = 7 1 3 5 6 0 4 2 Mutation (par permutation) :

S1

=10732564

Caractristiques des meta-heuristiques

Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

Optimum global n'est pas garanti : il ne doit donc pas tre requis Prsence de nombreux paramtres : phases de tests ncessaires Contrle des facteurs d'exploration (ou diversication), d'intensication, d'aprentissage Importance du choix de modlisation : libert relative, fonction objectif simple calculer Robustesse face aux problmes stochastiques (donnes incertaines) Diverses preuves de convergence ont t fournies sous certaines conditions

Autres mthodes
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

Rseaux de neurones (classication) Autres rparations locales : recherche tabou Nombreuses variantes des mthodes prsentes Mthodes hybrides : hybridation globale/locale ou dterministe/stochastique ...

Outils
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Introduction Recuit simul PSO ACO Gntique Caractristiques Autres mthodes Outils Conclusion

Outils non-commerciaux et/ou libres : ParadisEO (evol.,local, PSO), ECj (evol.), oMetah (evol., local, ACO, RS), . . . Outils commerciaux : ILOG/IBM CPLEX (RS, local), Mathematica (RS), . . .

Plan du cours
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

1 2 3 4 5 6 7

Introduction Programmation linaire Nombres entiers Programmation par Contraintes Meta-heuristiques Conclusion Biblio

Conclusion
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Optimisation est un vaste domaine qui fait intervenir plusieurs types de comptences Comprendre le schma gnral pour attaquer un problme : Analyse, Modlisation, Rsolution, Interpretation, Application Comprendre les avantages et limitations des direntes mthodes an de choisir la plus adapte (caractristiques du problme ? objectifs ? contexte ? dicult de rsolution ?) Se ramener si possible un problme type an de proter de l'exprience accumule Suivre un fonctionnement itratif et tester abondamment Si vous faites appel une expertise extrieure pour une ou plusieurs tapes, la comprhension du domaine permet de chirer et de superviser

Conclusion
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Ce cours est loin d'tre exhaustif sur les types de problmes (optimisation multi-objectifs, contraintes temps et stochastiques, donnes incertaines, objectifs robustesse, . . .), les mthodes associes et les outils existants Ncessaire de maintenir une veille technologique ou de mettre jour ses connaissances une fois confront une problmatique prcise Associer connaissance thorique la matrise d'outils performants (et leur langage)

Plan du cours
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

1 2 3 4 5 6 7

Introduction Programmation linaire Nombres entiers Programmation par Contraintes Meta-heuristiques Conclusion Biblio

Bibliographie
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Portail RO sur wikipedia (maintenu par E/C) Recherche oprationnelle pour l'ingnieur [Hche&al.] Meta-heuristiques pour l'optimisation dicile [Dro&al.] Introduction la calculabilit [Wolper] ...

Crdits
Mthodes et outils d'optimisation Optimisation Introduction Programmation linaire Nombres entiers Programmation par Contraintes Metaheuristiques Conclusion Biblio

Une partie du contenu de ce cours est adapt du travail de :

Wikipedia : portail RO Nadia Brauner & al. - Laboratoire G-SCOP (Grenoble) Christine Solnon - Laboratoire LIRIS (Lyon) Philippe Chretienne - ISIMA Philippe Liberti - LIX Vincent Mousseau - Centrale Paris ...