Recherche Op´ erationnelle Premi` ere Partie Paul Feautrier ENS Lyon 1er novemb

Recherche Op´ erationnelle Premi` ere Partie Paul Feautrier ENS Lyon 1er novembre 2005 Plan ▶Introduction et principaux concepts ▶Optimisation continue sans contrainte ▶Programmation lin´ eaire ▶Optimisation continue sous contrainte ▶Optimisation combinatoire ▶Programmation lin´ eaire en nombres entiers. ▶Exploration ▶M´ etaheuristiques ▶Programmation dynamique ▶´ El´ ements de Complexit´ e Plan Principaux concepts Un exemple Mod´ elisation R´ esolution Conclusion Optimisation continue sans contrainte Programmation lin´ eaire Qu’est ce que la recherche op´ erationnelle ? ▶Vocabulaire: Recherche op´ erationnelle = programmation math´ ematique = optimisation (mais pas optimisation de programme). ▶Recherche op´ erationnelle = mod´ elisation math´ ematique des processus de prise de d´ ecision. ▶Inconnues : les variables de d´ ecision. ▶´ Evaluation de la d´ ecision = fonction ´ economique ou fonction «objectif». ▶Trouver les valeurs des variables de d´ ecision qui minimisent (ou maximisent) la fonction objectif. Recherche op´ erationnelle modélisation optimisation action ▶La mod´ elisation est un art, l’optimisation est une science. ▶Applications : planification du d´ ebarquement de Normandie, optimisation d’un programme de calcul intensif, investissement en bourse. ▶Investissement en bourse = optimisation avec information incompl` ete ou al´ eatoire. ▶Planification d’une op´ eration militaire = il y a un adversaire = th´ eorie des jeux. ▶Optimisation d’un programme = en principe, on a une information compl` ete. ▶Le cours est essentiellement consacr´ e ` a l’optimisation avec Informatique ou math´ ematique ? Mathématique Informatique Recherche Opérationelle Complexité Théorèmes d’existence Convergence Algorithmes Preuves de terminaison Artificielle Intelligence Vocabulaire courbes de niveau de la fonction objectif optimum contraintes Forme canonique : trouver x ∈D qui minimise f . min f (x) x ∈ D Optimum local, global ▶Minimum local : a est un minimum local de f s’il existe un voisinage V de a tel que : x ∈V ⇒f (x) ⩾f (a). ▶Minimum global : a est un minimum global de f dans D si et seulement si : x ∈D ⇒f (x) ⩾f (a). local global Convexit´ e Un ensemble S est convexe si, pour toute paire de points a, b de S, S contient aussi le segment ab. a, b ∈S ⇒(0 ⩽λ ⩽1 ⇒λa + (1 −λ)b ∈S. convexe convexe convexe non convexe Fonction convexe ▶f est convexe dans un ensemble convexe S si et seulement si : x, y ∈S, 0 ⩽λ ⩽1 ⇒f (λx +(1−λ)y) ⩽λf (x)+(1−λ)f (y) S f x y Int´ erˆ et de la convexit´ e Th´ eor` eme Si f est convexe dans un ensemble convexe S, alors tout minimum local de f est un minimum global. D´ emonstration. Soit a un minimum local, et V l’ouvert contenant a dans lequel : x ∈V ⇒f (x) ⩾f (a). Si on suppose qu’il existe un point b ∈S tel que f (b) < f (a) alors on a : f (λa + (1 −λ)b) ⩽λf (a) + (1 −λ)f (b). Il est possible de trouver un λ suffisamment proche de 1 pour que x = λa + (1 −λ)b soit dans V . Contradiction en ce point : f (x) ⩽λf (a) + (1 −λ)f (b) ⩽f (a), Classification ▶Selon la nature des variables de d´ ecision : ▶Optimisation continue. ▶Optimisation discr` ete ou optimisation combinatoire. ▶Selon la nature des contraintes : ▶Pas de contraintes ou contraintes faciles ` a satisfaire (un segment de la droite r´ eelle) : optimisation sans contraintes. ▶Optimisation sous contraintes : il est difficile de trouver un point satisfaisant les contraintes. ▶Propri´ et´ es sp´ eciales des ´ el´ ements du probl` eme : lin´ earit´ e, convexit´ e. Plan Principaux concepts Un exemple Mod´ elisation R´ esolution Conclusion Optimisation continue sans contrainte Programmation lin´ eaire Un exemple: l’allocation de registre ▶Les processeurs modernes utilisent des registres pour ´ eviter les acc´ es ` a la m´ emoire. ▶Il est int´ eressant de conserver une donn´ ee en registre le plus longtemps possible ... ▶Mais les registres sont en nombre fini. ▶Le compilateur commence par ´ ecrire le code comme s’il y avait un nombre illimit´ e de registres virtuels, puis alloue les registres virtuels aux registres physiques. ▶Il ne faut pas utiliser plus de registres physiques qu’il n’y en a sur le processeur. Plan Principaux concepts Un exemple Mod´ elisation R´ esolution Conclusion Optimisation continue sans contrainte Programmation lin´ eaire Intervalle de vivacit´ e ▶Bloc de base : suite d’instructions sans test et sans goto entrant ni sortant. En premi` ere approximation, on alloue les registres ind´ ependemment pour chaque bloc de base. ▶Un registre virtuel est vivant depuis sa premi` ere ´ ecriture jusqu’` a sa derni` ere lecture. 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’interf´ erence ▶Deux registres virtuels interf` erent s’ils peuvent ˆ etre simultan´ ement vivants, i.e. si leurs intevalles de vivacit´ e ont une intersection nulle. ▶Deux registres virtuels qui interf` erent ne peuvent pas ˆ etre allou´ es au mˆ eme registre physique. ▶On peut construire le graphe d’interf´ erence d’un bloc de base. V2 V3 V4 V1 V9 Colorier le graphe d’interf´ erence ▶Contrainte : Il faut affecter un registre physique ` a chaque registre virtuel de fa¸ con ` a ce que deux registres virtuels adjacents ne soient pas affect´ es au mˆ eme registre physique. ▶Objectif minimiser le nombre de registres physiques. ▶C’est un probl` eme classique de coloriage de graphe. ▶On peut le prendre de deux fa¸ cons: ▶Existe-t-il un coloriage avec k couleurs ? ▶Quel est le nombre minimum de couleurs n´ ecessaires (nombre chromatique = register pressure). ▶On va se concentrer sur la deuxi` eme question. Plan Principaux concepts Un exemple Mod´ elisation R´ esolution Conclusion Optimisation continue sans contrainte Programmation lin´ eaire NP-compl´ etude ▶On doit toujours commencer par une estimation de la difficult´ e du probl` eme. ▶Probl` eme NP: probl` eme dont on peut v´ erifier la solution en temps polynomial. ▶Il existe une liste (provisoire) de probl` emes NP pour lesquels on ne sait pas (aujourd’hui) trouver la solution en temps polynomial, et qui peuvent ˆ etre r´ eduits l’un ` a l’autre en temps polynomial : les probl` emes NP-complets. Exemples canoniques : SAT (une formule bool´ eenne est-elle satisfiable) et PLNE (un syst` eme d’in´ equations en nombres entiers est-il satisfiable). ▶Le probl` eme du coloriage est NP-complet: on peut le r´ eduire ` a un probl` eme SAT, et on peut r´ eduire un probl` eme SAT ` a un probl` eme de coloriage. ▶Il ne faut donc pas esp´ erer une solution facile. Programmation lin´ eaire en nombres entiers ▶On num´ erote les couleurs par des entiers ; soit ci la couleur du sommet Vi. Les contraintes sont: ci ⩾ 0 ci ̸= cj, Vi adjacent Vj. ▶Objectif: minimiser max ci: min z, z ⩾ ci. ▶Pour rendre le probl` eme convexe, on pose: xij = 1 ssi ci > cj. On obtient un probl` eme en variables enti` eres dont les contraintes sont: ci −cj + (1 −xij)M > 0, cj −ci + xijM > 0. o` u M est un“grand nombre” . On s’est ramen´ e ` a un PLNE. Branch-and-Bound, I/III ▶M´ ethode : on construit un arbre de sous-probl` emes en divisant l’espace des solutions r´ ecursivement en deux. ▶La recherche s’arrˆ ete quand la solution est“´ evidente” . ▶On utilise une borne inf´ erieure pour ignorer les sous-probl` emes qui ne sont pas“prometteurs” . Branch-and-Bound, II/III ▶On engendre les sous-probl` emes en rempla¸ cant ci ̸= cj par ci > cj ou par cj > ci. Chaque sous-probl` eme est un probl` eme de plus court chemin, qui se r´ esoud en temps polynomial. ▶S’il n’y a pas de solution (cycle de poids positif) il est inutile de poursuivre l’exploration. ▶Sinon, on compare la valeur du probl` eme ` a la meilleure solution connue. On arrˆ ete l’exploration si elle est sup´ erieure. ▶On obtient une solution (candidate) quand on a exploit´ e toutes les contraintes. Branch-and-Bound, III/III                                                                                                          = + i j ij i j ▶S´ electionner deux sommets i et j non connect´ es. ▶Il y a deux possibilit´ es: ▶Ils ont uploads/Science et Technologie/ coursrechercheoperationnelle-pdf 1 .pdf

Tags
Science et Technologiepoint contrainte syst` probl` minimum
Documents similaires
  • 11
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager