Problème d’optimisation
Définition :
� Nom du problème : P
Méthodes arborescentes exactes et approchées � Paramètres génériques du problème (nombres, graphes, ...)
� Une caractérisation de ce qu’est une solution réalisable :
� Une instance I de P est une instanciation des paramètres génériques
Complexité, Algorithmes Randomisés et Approchés � A chaque I correspond un ensemble de solutions réalisables S(I ).
� Une fonction objectif f
October 1, 2018 Résolution :
Déterminer un algorithme A qui, pour chaque instance I retourne une
solution s ∗ (I ) de S(I ) t.q. :
problème de minimisation : ∀s ∈ S(I ), f (s ∗ (I )) ≤ f (s), ou
problème de maximisation : ∀s ∈ S(I ), f (s ∗ (I )) ≥ f (s).
Exemple : le voyageur de commerce euclidien (TSP) Trouver une solution optimale du TSP
Données : n points dans le plan
Solution réalisable : Un cy-
cle hamiltonien dans le graphe Première idée : énumérer l’ensemble des solutions réalisables du TSP :
(n−1)!
complet sous-jacent Kn 2 cycles possibles
Fonction objectif : La longueur
du cycle (que l’on souhaite min- But : Trouver une solution optimale sans énumérer toutes les solutions.
imiser)
Le problème de décision associé à ce problème est NP-complet.
⇒ ce problème est NP-difficile.
“Branch-and-bound” (séparation-évaluation) Brancher
La racine de l’arbre représente l’ensemble des solutions.
Chaque sous-arbre représente une solution partielle.
� “Branch” (brancher)
� Diviser (partitionner) l’espace de recherche
→ Arbre d’énumération (ou arbre de recherche)
� Explorer l’arbre de recherche
Espace des solutions
Brancher Brancher
La racine de l’arbre représente l’ensemble des solutions. La racine de l’arbre représente l’ensemble des solutions.
Chaque sous-arbre représente une solution partielle. Chaque sous-arbre représente une solution partielle.
Brancher Brancher
La racine de l’arbre représente l’ensemble des solutions. La racine de l’arbre représente l’ensemble des solutions.
Chaque sous-arbre représente une solution partielle. Chaque sous-arbre représente une solution partielle.
Brancher : exemple sur le problème du TSP “Branch-and-bound” (séparation-évaluation)
Soit 1 le premier sommet du cycle.
On choisit au niveau i le i eme sommet du cycle (n − i choix).
2
20
� “Branch” (brancher)
1
2 � Diviser (partitionner) l’espace de recherche
5
3
→ Arbre d’énumération (ou arbre de recherche)
2 3 4 5 � Explorer l’arbre de recherche
1 1
7
5
8 6
2
� “Bound” (borner) (présenté pour un pb de minimisation)
3 4 5 2 4 5 2 3 5 2 3 4 � Borne supérieure de la valeur d’une solution optimale
4 � Borne inférieure de la valeur d’un nœud (et de son sous-arbre)
5 7
4 5 3 5 3 4 4 52 5 2 4 3 5 2 52 3 3 4 2 4 2 3
Borner Borner : exemple sur le problème du TSP
Au noeud courant on a :
Soit G = (S, A) un graphe valué. Soit i ∈ S un sommet. Soit min1 (i)
� une borne supérieure Bsup d’une solution optimale. C’est souvent le le coût de la plus petite arête adjacente à i et min2 (i) le coût de la
coût d’une solution réalisable que l’on a déjà rencontrée. 2ème plus petite arête adjacente à i.
→ ce que l’on a déjà
� Propriété
une borne inférieure Binf du coût de toute solution issue du noeud � : Le coût d’un cycle hamiltonien de G est
courant (borne inf de toute solution du sous-arbre courant) ≥ 12 ni=1 min1 (i) + min2 (i).
→ ce que l’on peut espérer avoir de mieux en explorant le
sous-arbre Borne inférieure du coût d’une solution dont les sommets S’ forment un
cycle partiel (s1 , . . . , sk ) = coût des arêtes du cycle partiel
1 1�
Si Binf > Bsup alors on “élague” : on n’explore pas le sous-arbre + 2 (min1 (s1 ) + min1 (sk )) + 2 i∈S\S � (min1 (i) + min2 (i))
enraciné au noeud courant.
Exemple “Branch-and-bound” (séparation-évaluation)
2
20
2 Un algorithme de branch-and-bound pour un problème de minimisation
3 est basé sur
5
1
7 1 � une procédure de branchement qui décompose le problème,
5
8 6 et
2
� une borne inférieure pour éviter d’avoir à parcourir tout l’arbre.
4
5 7
Arbre d’énumération Explorer l’arbre d’énumération
Parcours en profondeur
� L’arbre d’énumération n’est pas complètement stocké en mémoire.
� En effet, sa taille est proportionnelle à la taille de l’ensemble des
solutions, qui est exponentielle.
� L’arbre d’énumération est exploré pour trouver la solution optimale.
Memory
Il y a deux façons classiques d’explorer l’arbre :
� Parcours en profondeur
� Parcours “le meilleur d’abord”
Explorer l’arbre d’énumération Explorer l’arbre d’énumération
Parcours en profondeur Parcours en profondeur
Memory
Memory
Charger le problème en mémoire Première branche = premier sous-problème
Explorer l’arbre d’énumération Explorer l’arbre d’énumération
Parcours en profondeur Parcours en profondeur
Memory
Memory
Descendre Première feuille
Explorer l’arbre d’énumération Explorer l’arbre d’énumération
Parcours en profondeur Parcours en profondeur
Memory
Memory
Premier retour en arrière Seconde feuille
Explorer l’arbre d’énumération Explorer l’arbre d’énumération
Parcours en profondeur Parcours en profondeur
Memory
Memory
Deuxième retour en arrière et retourner en arrière à nouveau
Explorer l’arbre d’énumération Explorer l’arbre d’énumération
Parcours en profondeur Parcours en profondeur
Memory
Memory
et ainsi de suite... ...jusqu’à la dernière feuille
Complexité Explorer l’arbre d’énumération
� Complexité temporelle : généralement exponentielle en la taille du
Parcours “le meilleur d’abord”
problème.
� A chaque itération, parmi les sommets ouverts, on choisit “le plus
� Complexité en espace : en O(hn) avec n taille du problème et h
hauteur de l’arbre d’énumération (h est polynomial en n). prometteur” (par exemple celui qui a la borne inférieure la plus
basse).
� Les feuilles intéressantes traversées pendant la recherche doivent � Les sommets ouverts sont stockés dans un tas
être stockées. (priorité d’un noeud = sa borne inférieure).
� En général on stocke seulement une solution : la meilleure solution � Inconvénient : la taille du tas peut être grande.
rencontrée (ou l’une parmi les meilleures).
La taille de la solution est O(n).
Comment trouver une borne inférieure ? Trouver une borne inférieure : relaxation du problème
� Coût de la solution partielle S’
S
� Solution “ad hoc” (propriété)
� Ignorer certaines contraintes définissant S, ou rendre ces
� Relaxation du problème contraintes moins fortes.
� Soit S � le nouvel ensemble de solutions (S ⊂ S � ).
� Le minimum du problème relâché est une borne inférieure.
minx∈S � f (x) ≤ minx∈S f (x).
� On cherche un problème relâché qui est polynomial.
Exemple : TSP TSP : borne inf pour une solution partielle
Coût d’une solution partielle ≥
� coût du tour partiel
� � + coût d’un arbre couvrant de poids minimum pour les sommets
Une chaı̂ne hamiltonienne (CH) est une châine qui passe
exactement une fois par chaque sommet du graphe. qui ne sont pas couverts par le tour partiel
� Une CH est un arbre couvrant avec la contrainte additionnelle que
l’arbre doit avoir seulement deux feuilles.
� Le problème de l’arbre couvrant de poids minimum (ACPM) est
une relaxation du problème de la CH la plus courte. Le coût d’un
ACPM est une borne inférieure de la CH la plus courte, qui est une
borne inférieure pour le TSP.
En pratique Construire une bonne solution
� Plus la borne inférieure est bonne, plus le nombre de nœuds visités � 1. Algorithmes gloutons
pendant la recherche est faible. Construire une solution à partir de règles simples
� Cependant, si la borne inférieure est meilleure, son temps de calcul � 2. Heuristiques basées sur une relaxation du problème
peut être plus long Construire une solution réalisable à partir d’une solution relâchée
� moins de nœuds visités qui viole certaines contraintes
� plus de temps passé à chaque nœud � 3. Branch and bound partiel
� il faut faire des tests pour savoir quelle solution est la meilleure.
Utiliser un arbre d’énumération pour obtenir une bonne solution
� Une bonne solution initiale est très importante. sans explorer tout l’espace des solutions.
Règle du PlusProcheVoisin pour le TSP Règle du PlusProcheVoisin pour le TSP
La solution est réalisable mais pas optimale
Une autre heuristique gloutonne Une autre heuristique gloutonne
Comme dans l’algorithme de Kruskal, connecter les points les plus L’arête la plus courte qui ne crée pas de nœud de degré 3 ni de cycle est
proches. choisie.
Une autre heuristique gloutonne Heuristique de Clarke-Wright
� Cette heuristique a été initialement introduite pour le problème de
tournées de véhicules (VRP).
� Le VRP est une généralisation du TSP dans laquelle
� il y a un dépôt à partir duquel tous les tours commencent et se
terminent.
� les véhicules ont une capacité limitée : les livraisons doivent être
divisées en plusieurs tournées.
� Pour construire un tour pour le TSP, on choisit arbitrairement une
ville comme étant le dépôt et les véhicules ont une capacité
illimitée.
Heuristique de Clarke-Wright Heuristique de Clarke-Wright
Créer un tour individuel entre chaque point et le dépôt. Le gain d’une arête mesure la diminution de la longueur du tour obtenu
en choisissant cette arête.
Heuristique de Clarke-Wright 2. Heuristiques basées sur la relaxation du problème
� Trouver une relaxation du problème
Le TSP euclidien est relaxé en un arbre couvrant de poids minimum
� Retourner une solution optimale pour le problème relâché
Algorithme de Prim ou de Kruskal
� Si la solution du problème relâché viole certaines contraintes du
problème initial, réparer cette solution pour la rendre réalisable.
L’arête avec le gain le plus important est choisie à chaque étape.
Construire un tour à partir d’un arbre couvrant de poids 3. Recherche partielle dans un arbre d’énumération
minimum
� Le but est d’utiliser une structure générale (l’arbre d’énumération)
afin d’avoir des algorithmes génériques.
� Au lieu de construire une seule solution, on construit plusieurs
solutions en visitant plusieurs feuilles de l’arbre.
� On a besoin d’une heuristique pour évaluer à priori les différents
choix représentés par les différentes branches descendant d’un
nœud.
Heuristique gloutonne dans un arbre de recherche Heuristique gloutonne dans un arbre de recherche
La meilleure branche est dessinée comme étant la branche gauche. La meilleure branche est dessinée comme étant la branche gauche.
Choisir la meilleure branche à priori et répéter le même processus de sélection
Heuristique gloutonne dans un arbre de recherche Greedy Randomized Adaptive Search Procedure
La meilleure branche est dessinée comme étant la branche gauche.
Choisir la branche gauche avec la probabilité 1 − p avec p < 0.5
jusqu’à trouver la solution
Greedy Randomized Adaptive Search Procedure Greedy Randomized Adaptive Search Procedure
Recommencer la procédure Et choisir la meilleure
Branch-and-Greed Branch-and-Greed
? ? ? ?
59 57
Comment choisir entre les deux premières branches du nœud racine? Exécuter l’algorithme glouton pour chaque sous-arbre
Branch-and-Greed Branch-and-Greed
? ? ? ?
? ? ? ?
59 57 59 57 62
et sélectionner la branche qui mène au sous-arbre avec la meilleure Exécuter à nouveau l’algorithme glouton pour chaque sous-arbre du
solution. sous-arbre courant
Branch-and-Greed Branch-and-Greed
? ? ? ?
? ? ? ?
? ? ? ?
59 57 62 59 57 55 62
Emprunter la meilleure branche Jusqu’à ce que le chemin rouge atteigne une feuille
Résumé : “Branch-and-bound” (séparation-évaluation) Ensemble dominant
� “Branch” (brancher)
� Diviser (partitionner) l’espace de recherche � Pour certains problèmes, on peut facilement déterminer un
→ Arbre d’énumération (ou arbre de recherche)
�
sous-ensemble S � de solutions de S tel que S � contient au moins
Explorer l’arbre de recherche
une solution optimale de S.
� “Bound” (borner)
� L’algorithme de branch-and-bound doit explorer S � au lieu de S.
� Borne supérieure de la valeur d’une solution optimale (solution
réalisable)
� Borne inférieure de la valeur d’un nœud
Pour réduire (encore) le nombre de noeuds explorés : ensemble
dominant, règle de dominance.
Règle de dominance Une règle de dominance pour le TSP
Le tour partiel (chemin) (s1 = 1, s2 , · · · , sk ) doit être un chemin
hamiltonien entre s1 et sk dans le sous-graphe défini par les nœuds
� On peut souvent prouver une propriété (P) qui doit être vérifiée {s1 , s2 , . . . , sk }.
par au moins une solution optimale du problème.
� En analysant une solution partielle à un nœud de l’arbre de
recherche, on peut quelquefois prouver que (P) ne peut pas être
vérifiée par les solutions qui complètent la solution partielle
courante.
� Le nœud est dominé par une solution partielle qui satisfait (P).
� La propriété (P) est appelée règle de dominance.
lgth=41.52 lgth=45.29
Une règle de dominance pour le TSP Une règle de dominance pour le TSP
Le tour partiel (chemin) (s1 = 1, s2 , · · · , sk ) doit être un chemin Le tour partiel (chemin) (s1 = 1, s2 , · · · , sk ) doit être un chemin
hamiltonien entre s1 et sk dans le sous-graphe défini par les nœuds hamiltonien entre s1 et sk dans le sous-graphe défini par les nœuds
{s1 , s2 , . . . , sk }. {s1 , s2 , . . . , sk }.
lght=118.10 lght=118.10 lght=118.10 lght=118.10
159.62 163.39 159.62 163.39
lgth=41.52 lgth=45.29 lgth=41.52 lgth=45.29
Une règle de dominance pour le TSP
Le tour partiel (chemin) (s1 = 1, s2 , · · · , sk ) doit être un chemin
hamiltonien entre s1 et sk dans le sous-graphe défini par les nœuds
{s1 , s2 , . . . , sk }.
lgth=41.52 lgth=45.29
Un tour partiel est dominé quand on peut montrer qu’il existe un tour
partiel plus court.