I. introduction

RO I : OPTIMISATION COMBINATOIRE Notes de Cours R.O MASTER M1

CHAPITRE II

Méthodes de résolution des problèmes combinatoires

I. INTRODUCTION

On distingue deux classes de méthodes de résolution des problèmes d’optimisation combinatoire :
Les méthodes exactes :

Ces méthodes sont capables de trouver une solution optimale d’un problème donné dans un intervalle de temps bien déterminé mais exponentiel sur les problèmes NP-complets (notamment les PLNE). Parmi ces méthodes on retrouve la Méthode de séparation et d’évaluation (Branch & Bound), la Méthode des coupes (Cutting planes), la Programmation dynamique…
Les méthodes approchées :

Ces algorithmes appelés généralement heuristiques consistent à trouver une solution proche de l’optimum en un temps raisonnable. Les heuristiques peuvent aller d’un simple algorithme de recherche locale à une classe générale d’heuristiques appelées méta-heuristiques telles que le Recuit simulé, la Recherche tabou, les Algorithmes génétiques…

• 
  Difficultés de résolution des PLNE
  

On pourrait penser que pour résoudre un PLNE, il suffit d’appliquer le simplexe sur le PL (ou PLC) obtenu après relaxation linéaire (continue) du PLNE (x  IN  x  IR), puis de faire un arrondi de la solution réelle obtenue. Sauf que cette solution arrondie ne correspond que dans certains cas à la solution optimale. Elle peut même être très éloignée de la solution optimale du PLNE (Voir Exemple). Néanmoins une propriété importante est mise en évidence :
Soient :

Z_PLNE  : Valeur de la fonction objectif de la solution optimale du PLNE (qu’on notera souvent Z_opt)

Z_PL  : Valeur de la fonction objectif de la solution optimale du PL (obtenue par relaxation, notée aussi Z*)

Z_PLarr  : Valeur de la fonction objectif de la solution arrondie du PL (notée aussi ).
Nous avons : Min Z_PL  Z_PLNE  Z_PLarr

Max Z_PLarr  Z_PLNE  Z_PL
Ainsi la solution optimale réelle Z_PL représente une borne inférieure ou minorant (resp. supérieure ou majorant) par rapport à la solution optimale du PLNE Z_PLNE dans le cas min (resp. max).
Exemple : Soit le PLNE suivant résolu graphiquement :
Max Z = x₁ + 0.64 x₂

Avec 50x₁ + 31x₂  250 Sol. optimale du PLC  : X_PL = (1.95 , 4.92) Z_PL = 5.098

3x₁ - 2x₂ ≥ -4 Sol. Arrondie : X_PLarr = (2 , 4) Z_PLarr = 4.56



X_PL = (1.95 , 4.92)

X_PLNE = (5 , 0)

X_PLarr = (2 , 4)

x₁ , x₂  IN Sol. optimale du PLNE : X_PLNE = (5 , 0) Z_PLNE = 5

Remarques :

• 
  En cas de max, on arrondit souvent les valeurs des variables à l’entier inférieur, sinon la solution devient non réalisable. En cas de min, l’arrondi se fait à l’entier supérieur. On peut être amené aussi à combiner les deux types d’arrondi pour obtenir une solution réalisable au PLNE.
  
• 
  Cet exemple montre que la solution du PLNE peut être très éloignée de la solution réelle.
  

II. METHODES EXACTES
II.1. La procédure de séparation et d’évaluation progressive (Branch & Bound)
a) Introduction

Il s’agit essentiellement de diviser (divide and conquer) l’ensemble de toutes les solutions réalisables (problème initial) en sous-ensembles plus petits (sous problèmes) et mutuellement exclusifs. C’est la phase « séparation » (Branch). Puis divers critères sont utilisés pour identifier les sous-ensembles qui peuvent contenir la solution optimale et les sous-ensembles qui ne doivent pas être explorés plus à fond car ils ne peuvent pas contenir la solution optimale. C’est la phase « évaluation » (Bound).
Cette méthode consiste donc à faire une énumération intelligente de l’espace des solutions, puisqu’elle arrive à éliminer des solutions partielles qui ne mènent pas à la solution optimale.
Pour ce faire, cette méthode se dote d’une fonction qui permet de mettre une borne inférieure (en cas de min) sur certaines solutions pour soit les exclure soit les maintenir comme des solutions potentielles. Bien entendu, la performance d’une méthode de branch and bound dépend, entre autres, de la qualité de cette fonction (de sa capacité d’exclure des solutions partielles tôt).

P

P₁

P₂

P_k

P₂₁

P₂₂

P_2k

……………

……

Le processus de séparation d’un sous-ensemble P_i s’arrête dans l’un des cas suivants (cas Min) :

• 
  Lorsque la borne inférieure de P_i est  à la meilleure solution trouvée jusqu’à maintenant pour le problème initial.
  
• 
  Lorsque P_i n’admet pas de solution réalisable.
  
• 
  Lorsque P_i admet une solution complète du problème initial.
  

b) Algorithme général (cas Min)

A chaque instant, on maintient :

- une liste de sous problèmes actifs P_i

- Le coût Z de la meilleure solution obtenue jusqu’à maintenant (Initialisé à + ou à celui d'une solution initiale connue).

A une étape typique :

- Sélectionner un sous problème actif P_i

- Si P_i n’est pas réalisable, le supprimer (stop branch) sinon calculer sa borne inférieure Z_inf(P_i)

- Si Z_inf(P_i)  Z supprimer P_i (stop branch)

- Si Z_inf(P_i) < Z soit résoudre P_i directement, soit créer de nouveaux sous problèmes et les ajouter à la liste des sous problèmes actifs.
En pratique, il reste quelques petits détails à régler pour pouvoir appliquer cette méthode, en particulier :
- Comment déterminer la borne d’évaluation (borne inférieure en cas de min) ?

Une possibilité est de calculer la solution du PLC obtenue par relaxation linéaire du PLNE. Cette méthode donnera une bonne évaluation, mais pourra être coûteuse et longue à calculer. Suivant le problème on pourra essayer de trouver une méthode heuristique/astucieuse faisant un compromis entre vitesse d’obtention de la borne et sa fiabilité.
- Quel sommet explore t’on à chaque étape de la recherche ?

Là, il n’y a pas de bonne méthode, c’est suivant le problème en question. Les principales stratégies utilisées sont : - En profondeur (DFS)

- En largeur (BFS)

- Meilleur d’abord. (Best First)
- Suivant quel x_i construit-on l’arbre ?

Ce choix peut être déterminant pour la rapidité de la solution optimale. Dans le cas du problème du sac à dos par exemple, il est plus efficace de prendre l’ordre des x_i par coût décroissant.
c) Exemples
Exemple 1 : Soit le PLNE (noté P) Min x₁ – 2x₂

s.c. –4x₁ + 6x₂ ≤ 9

x₁ + x₂ ≤ 4

x₁, x₂ ≥ 0 et entiers
Z* sera le coût optimal de la relaxation linéaire (borne inférieure).

• 
  Si la solution de la relaxation est entière, pas besoin de partitionner le sous problème.
  
• 
  Sinon, on choisit un non entier, et on crée deux sous problèmes en ajoutant les contraintes :
  

x_i ≤ ëû et x_i ≥ éù
La solution optimale réelle obtenue par le simplexe (de P relaxé) est x* = (1.5 , 2.5) et Z* = -3.5.
En cas de minimisation cette solution représente donc une borne inférieure : Z_inf = Z* = -3.5. L’arrondi de cette solution donne une solution réalisable (borne supérieure Z_sup), on a : = (1 , 2) et = Z_sup = -3. Ainsi on peut borner la solution optimale du PLNE comme suit : -3.5 ≤ Z_opt ≤ -3

• 
  Création des sous problèmes P₁ et P₂ en rajoutant les contraintes x₂ ≤ 2 et x₂ ≥ 3
  

P1	P2
min x1 – 2x2 s.c. –4x1 + 6x2 ≤ 9 x1 + x2 ≤ 4 x2 ≥ 3 x1, x2 entiers	min x1 – 2x2 s.c. –4x1 + 6x2 ≤ 9 x1 + x2 ≤ 4 x2 ≤ 2 x1, x2 entiers

Liste des sous problèmes actifs : {P₁ , P₂}

1

- 4x₁+6x₂ 9

x₁+x₂  4

x₂  3

x₂  2

(0.75,2)
Le problème P₁ n’est pas réalisable  Liste des problèmes actifs (P₂}

• 
  La solution optimale réelle de P₂ relaxé est x* = (0.75 , 2) et Z* = -3.25.
  

La borne inférieure trouvée (-3.25) étant inférieure à la meilleure solution trouvée (-3) 

Création des sous problèmes P₃ et P₄ en rajoutant les contraintes x₁ ≤ 0 et x₁ ≥ 1

P3	P4
min x1 – 2x2 s.c. -4x1 + 6x2 ≤ 9 x1 + x2 ≤ 4 x2 ≤ 2 x1 ≥ 1 x1, x2 entiers	min x1 – 2x2 s.c. -4x1 + 6x2 ≤ 9 x1 + x2 ≤ 4 x2 ≤ 2 x1 ≤ 0 x1, x2 entiers

1

- 4x₁+6x₂ 9

x₁+x₂  4

x₂  2

x₁  0

x₁  1

P₃ (1,2)
P₄ (0,1.5)
Liste des problèmes actifs (P₃ , P₄}

• 
  La solution optimale de P₃ relaxé est entière donc x = (1 , 2) et Z = -3.
  
• 
  La solution optimale réelle de P₄ relaxé est x* = (0 , 1.5) et Z* = -3.
  

Cette branche est arrêtée car Z* (borne inférieure) ≥ -3.
La solution optimale est donc x_PLNE = (1 , 2) avec Z_opt = -3

x = (1,2) Z = -3
P

P₁

P₂

P₃

P₄

Non réalis.

x* = (0.75,2) Z_inf = -3.25

x₂  3

x₂  2

x₁  0

x₁  1

x* = (0,1.5) Z_inf = -3
x* = (1.5 , 2.5) Z* = -3.5
Exemple 2 : Problème du sac à dos (Pb. de maximisation)

• 
  Deux simplifications
  

1. 
   Les variables sont binaires.
   
2. 
   La relaxation linéaire peut être résolue efficacement par un algorithme simple : prendre d’abord les articles à meilleur rendement, jusqu’à atteindre la capacité.
   

• 
  Une société dispose de 1 400 000 DA à investir.
  
• 
  Les experts proposent 4 investissements possibles :
  

		Coût	Bénéfice	Rendement
	Inv. 1	500 000	1 600 000	3.20
	Inv. 2	700 000	2 200 000	3.14
	Inv. 3	400 000	1 200 000	3.00
	Inv. 4	300 000	800 000	2.67

Résolution :

	ai	ci	Rdt	P	P1	P3	P4	P5	P6	P2	P7	P8	P9	P10	P11	P12
1	500 000	1 600 000	3.20	1	1	1	3/5	0	1	1	1	1	1	4/5	0	1
2	700 000	2 200 000	3.14	1	5/7	0	1	1	1	1	1	6/7	0	1	1	1
3	400 000	1 200 000	3.00	1/2	1	1	1	1	1	0	0	0	0	0	0	0
4	300 000	800 000	2.67	0	0	1	0	1	?	2/3	0	1	1	1	1	1