OPTIMISATION COMBINATOIRE

(DISCRÈTE)

SEDDIK ILIAS INTTIC

1
 Optimisation
numérique

Optimisation continue Optimisation

combinatoire

Sans contrainte Avec contrainte Méthodes exactes Méthodes

approchées

Linéaires Non linéaires

Descente de gradient,
Heuristiques Métaheuristiques
méthodes
newtonniennes…etc
Programmation
dynamique,
Branch&Bound… Hill climbing, recuit
Résolution Lagrangien augmenté, etc simulé, algorithmes
géométrique, méthode d’Uzawa… évolutionnistes…etc
simplexes…etc etc

2
 DÉFINITIONS
Optimisation discrète:
 Les problèmes d’optimisation discrète, par opposition à l’optimisation continue, forment une
classe de problèmes d’optimisation particulièrement étudiée. Tout ou partie des variables de ce
type de problèmes appartiennent à l’ensemble des entiers.
Autrement dit: X ⊆ m × n−m , avec 0 ≤ m ≤ n.
 Si m = n, alors on parle de problème à nombres entiers, sinon il fait partie des problèmes
d’optimisation mixtes en nombres entiers.
 Les ensembles réalisables des problèmes d’optimisation et des problèmes mixtes peuvent être
infinis, et ceux des problèmes en nombres entiers sont au plus dénombrables.

3
 DÉFINITIONS
Optimisation combinatoire:
 Les problèmes d’optimisation combinatoire sont habituellement définis comme une problématique
de choix d’une meilleure alternative dans un ensemble très grand mais fini d’alternatives.
 Les problèmes d’optimisation combinatoire peuvent s’avérer très difficiles à résoudre bien qu’ils
soient généralement faciles à formaliser. La difficulté de ces problèmes a pour origine soit la
structure de l’ensemble réalisable soit la nature de la fonction objectif.
 Le nombre de solutions réalisables des problèmes combinatoires augmente exponentiellement en
fonction de la taille du problème, et c’est ce qui exclut des méthodes de résolution basées sur
l’énumération de toutes les solutions réalisables.
 En plus des formulations en programmes mathématiques, il est souvent possible de les
formuler comme des problèmes de la théorie des graphes.

4
 EXEMPLES DE PROBLÈMES
 Affectation de fréquences en téléphonie
 Problème du sac à dos
 Conception de routes ou de chemins de fer
 Problème du voyageur de commerce
 Gestion de ressources humaine ou matérielles énumérables
 La planification des tâches des employés d’une entreprise.
 Le calcul d’itinéraire pour les applications de géolocalisation

5
 EXEMPLES DE PROBLÈMES
Problème du voyageur de commerce (Travelling Salesman Problem)
 Un agent commercial doit visiter une liste de villes et retourner à sa ville de départ. Cette
tournée entre toutes les villes doit prendre le chemin le plus cours. Le plus court chemin peut se
traduire par la distance, le temps ou même le carburant.
 En suivant un chemin Hamiltonien, on se retrouve avec ((n-1)!)/2 possibilité.

6
 COMPLEXITÉ
Problème NP-Complet:
En théorie de la complexité, un problème NP-complet ou problème NPC est un problème de
décision vérifiant les propriétés suivantes :
 il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes
vérifiant cette propriété est notée NP ;
 tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela
signifie que le problème est au moins aussi difficile que tous les autres problèmes de la classe NP.

Bien qu'on puisse vérifier rapidement toute solution proposée d'un problème NP-complet, on
ne sait pas en trouver efficacement. C'est le cas, par exemple, du problème du voyageur de
commerce ou de celui du problème du sac à dos.

7
 COMPLEXITÉ
Problème du voyageur de commerce (Travelling Salesman Problem)
 Un agent commercial doit visiter une liste de villes et retourner à sa ville de départ. Cette
tournée entre toutes les villes doit prendre le chemin le plus cours. Le plus court chemin peut se
traduire par la distance, le temps ou même le carburant.
 En suivant un chemin Hamiltonien, on se retrouve avec ((n-1)!)/2 possibilité.

8
 MÉTHODES
Classes de méthodes:
 Méthodes exactes (complètes): Elles se basent généralement sur une recherche complètes de
l’espace des combinaisons afin de trouver une solution optimale.
 Méthodes approchées (incomplètes): Elles permettent de trouver une bonne solution (pas
forcément optimale) dans un temps raisonnable.

9
 MÉTHODES
Classes de méthodes:

10
 MÉTHODES EXACTES
Méthodes exactes:
Le principe des méthodes exactes consiste généralement à énumérer, souvent de manière
implicite, l'ensemble des solutions dans le but de trouver la solution optimale:
 Avantage: Certitude de trouver la solution optimale.
 Inconvénient: Temps d’exécution prohibitif.

11
 MÉTHODES EXACTES
Méthodes à base de relaxation:
Une relaxation d’un problème (P) est un nouveau problème (P`) construit à partir de (P) et auquel
on a retiré au moins une contrainte.
Toutes les solutions de P sont des solutions de (P`), mais la réciproque est fausse.

 L’algorithme le plus connu se basant sur ce principe est celui de Séparation et Évaluation
(branch & bound)

12
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Un algorithme de Séparation et Evaluation (ou branch-and-bound) pour résoudre le problème de
maximisation (P) est fondé sur cette l’idée d’utiliser des bornes supérieures pour choisir quelles
solutions éliminer en étant sûr quelles ne seront pas meilleures que la meilleure solution courante.

13
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
• Comment résoudre de façon exacte (= trouver une solution optimale à) un PLNE :

Obtenir une évaluation (borne) de la valeur optimale

 Déterminer une borne inférieure de cette valeur? Valeur de n’importe quelle solution
admissible!
 Déterminer une borne supérieure de cette valeur? En général, on a recours à des relaxations

Si ces deux bornes sont égales, alors on a fini!

14
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Une Borne primale est la valeur d’une solution admissible.
 Si on maximise, c’est une borne inférieure
 Si on minimise, c’est une borne supérieure
C’est une tâche souvent difficile
Borne duale
 Si on maximise, c’est une borne supérieure
 Si on minimise, c’est une borne inférieure
On détermine des bornes duales via des relaxations :
– Idéalement, problème plus simple (plus rapide) à résoudre que le problème initial
– Problème dont chaque solution a une valeur plus grande (si on maximise) ou plus petite (sinon) que
celle de toute solution admissible du problème initial 15
 MÉTHODES EXACTES
Algorithme de Branch and Bound
On note :
– la liste des sommets actifs sommets à séparer
– le cout de la meilleure solution admissible connue solution entière
– Chaque sommet de est stocké avec sa solution relaxée et son évaluation.
• Initialisation : sommet racine, (cas de minimisation)
• Choisir un sommet de et une variable non entière de
• Séparer le sommet suivant la variable sommets et
Supprimer le sommet de la liste
• Évaluer le sommet
– Si la solution est admissible, mettre à jour abandonner
– Sinon Si il n'est pas nécessaire de séparer abandonner
– Sinon ajouter le sommet à la liste
• Évaluer de même le sommet 16
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Exemple: Soit le problème
sous contraintes

• Note: est admissible. Donc .

17
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :

18
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Résolution graphique (sans intégrité):

19
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Branching:

20
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Branching:

21
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Résumé:

22
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Nouveau domaine admissible:

23
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Résolution graphique P01:

24
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Nouveau domaine admissible:

25
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Résumé:

26
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Nouveau domaine admissible:

27
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Résolution graphique P011:

Solution (0,1.5)
=> Non entière

28
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Résolution graphique P012:

Solution (1,2)
ÞSolution entière
Þ C’est donc la solution optimale

U = -3

29
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Résumé final:

30
 MÉTHODES EXACTES
Séparation et Évaluation (branch & bound) :
Résumé final:

31
 MÉTHODES EXACTES
Algorithme glouton (greedy algorithm)
C’est une classe d’algorithmes qui suit le principe
de faire, étape par étape, un choix optimum local,
dans l'espoir d'obtenir un résultat optimum global.
• Par exemple, dans le problème du rendu de
monnaie (donner une somme avec le moins
possible de pièces), l'algorithme consistant à
répéter le choix de la pièce de plus grande
valeur qui ne dépasse pas la somme restante est
un algorithme glouton.

32
 MÉTHODES EXACTES
Programmation dynamique
La programmation dynamique est basée sur le principe de Bellmann :
• "Si C est un point qui appartient au chemin optimal entre A et B, alors la portion de ce même
chemin allant de B à C est le sous-chemin optimal entre B et C"
Cette approche consiste donc à construire les sous-chemins optimaux pour ensuite construire
par récurrence le chemin optimal pour le problème entier.

33
 MÉTHODES EXACTES
Programmation dynamique

34
 MÉTHODES EXACTES
Programmation dynamique
Dans la figure suivante, le chemin vert entre A et B est optimal. Ce chemin passe par le point
C. Le sous-chemin vert [C, B] est donc optimal et le sous-chemin gris [C, B] ne peut exister car
il est plus court que le sous-chemin vert. Autrement dit, si le sous-chemin gris existe alors la
solution optimale devient la séquence formée du sous-chemin vert [A, C] et du sous-chemin
gris [C, B] au lieu du chemin vert [A, B].

 La programmation dynamique s'appuie sur le principe de Bellman et consiste à prolonger le

problème étudié en un problème plus général dont les paramètres sont entiers. Il faut
généralement déterminer des relations de récurrence permettant de résoudre le problème d'un
ordre donné en fonction de ses solutions pour les ordres inférieurs.

35
 MÉTHODES EXACTES
Programmation dynamique (Principe algorithmique)
L’objectif de la programmation dynamique sera de formaliser un problème d’optimisation en
algorithme récursif.
Le point faible de ces fonctions récursives est la répétition régulière des mêmes opérations.
 La programmation dynamique favorisera la mémorisation(memoization) des données

 Cette approche permet de réduire la complexité initiale de O(2n) à une complexité entre
O(n2) et O(n3)

36
 MÉTHODES EXACTES
Programmation dynamique (Principe algorithmique)
Exemple: Suite de Fibonacci en récursivité pure:
int fib (int n) {
if (n < 2)
return 1;
return fib(n-1) + fib(n-2);
}
 En programmation dynamique:
void fib () {
fibresult[0] = 1;
fibresult[1] = 1;
for (int i = 2; i<n; i++)
fibresult[i] = fibresult[i-1] + fibresult[i-2];
37
}
 MÉTHODES EXACTES
Programmation dynamique (Principe algorithmique)
Marche arrière (backtrack): La possibilité de faire marche arrière est également l’un des
points fort de la programmation dynamique. C’est-à-dire qu’on peut revenir à un état précédent
qui n’était pas optimal sur N-1, afin de vérifier si il l’est sur N.

38
 MÉTHODES EXACTES
Programmation dynamique
La programmation dynamique est efficace dans le cas de problèmes où les solutions ont des
structures fortement liées entre elles, on peut détecter des dominances entre solutions : si dans
une arborescence, on peut montrer que tout sous-problème descendant d'un sous-problème a
est au moins aussi bon que tout descendant d'un sous-problème b : on dit que a domine b. Dans
ce cas, il suffit d'explorer a.
Ces dominances se rencontrent dans les problèmes à forte structure, par exemple des problèmes
d'ordonnancement ou d'optimisation sur les graphes, où les solutions ont des points ou des
parties en communs.

39
 MÉTHODES EXACTES
Programmation dynamique (cas d’utilisation)
Les problèmes les plus adaptés seront surtout ceux qui peuvent être modélisés en graphe:
 Problèmes du plus court chemin
 L’alignement de séquences génétiques
 Problème du sac à dos
 Tour de Hanoi

40
 MÉTHODES EXACTES
Programmation dynamique (Exemple)
Problème: Imaginez que vous ayez une collection de N timbres placés les uns à côté des autres.
Pour plus de simplicité, numérotons les timbres de gauche à droite car ils se trouvent avec des
nombres entiers de 1 à N, respectivement. Le prix du ième timbre est Pi. (les prix des différents
timbres peuvent être différents).
Parce que les timbres prennent de la valeur chaque année, supposons qu'aujourd'hui soit l'année 1,
l'année y, le prix du ième timbre sera y* Pi, c'est-à-dire y fois la valeur de l'année en cours.
Vous voulez vendre tous les timbres que vous possédez, mais vous voulez vendre exactement un
timbre par an, à partir de cette année.
Les prix des timbres sont: p1=2, p2=3, p3=5, p4=1, p5=4
 Vous voulez savoir quel est le profit maximum que vous pouvez obtenir si vous vendez les
timbres dans un ordre optimal, sachant qu’on ne peut vendre que le dernier ou le premier à
chaque itération ? 41
 MÉTHODES EXACTES
Programmation dynamique (Exemple)
Solution: L’algorithme suivant nous garantira de trouver le meilleur ordre:

int N; // read-only nombre de timbres au début

int p[N]; // read-only tableau des prix
int cache[N][N]; // toutes les valeurs, initialisées à -1
int profit(int be, int en) {
if (be > en) {
return 0;
}
// Mise en cache des résultats
if (cache[be][en] != -1) {
return cache[be][en];
}
int year = N - (en-be+1) + 1;
// Ne pas oublier de mettre en cache dès qu’une nouvelle solution est trouvée
return cache[be][en] = max(profit(be+1, en) + year * p[be], profit(be, en-1) +
year * p[en]);
}

42
 MÉTHODES EXACTES
Programmation dynamique (Exemple)
Solution: En utilisant une résolution par « force brute » ou un algorithme glouton (qui ne va
prendre que la meilleure solution à chaque étape), on obtiendrait la solution: p1, p2, p5, p4, p3
qui nous fixerait la fonction objectif à 49.
En éxecutant l’algorithme précédent (grâce aux marches arrières), on obtiendra la solution:
p1, p5, p4, p2, p3 qui maximisera la valeur à 50 (meilleure solution).

43
 MÉTHODES EXACTES
Programmation dynamique (Exemple problème du sac à dos)
Des objets de différents volumes et valeurs sont à mettre dans un sac à dos qui a un volume
maximum. On doit donc choisir les items à mettre dans le sac (problème binaire)
=11, =8, =5, =7, =6, =4, et =10
• notre problème peut être formulé comme suit :
Maximiser 11 +8 +5
tel que : 7 +6 +4 ≤ 10, ∈ {0,1} ∀ 1 ≤ i ≤ 3

44
 MÉTHODES EXACTES
Programmation dynamique
Algorithme pour le problème du sac à dos :
• E(0)={[0,0]} Ensembles d'états E(i)

• Pour i=1,2,3,...,N i E(i)

– Initialiser E(i)={}. 0 {[0,0]}
– Créer pour chaque [u,v] de E(i-1) deux états 1 {[0,0] ; [11,7]}
[u + wi, v + vi] si v + vi ≤Vmax et [u,v] et les insérer 2 {[0,0] ; [8,6] ; [11,7]}
dans E(i).
3 {[0,0] ; [5,4] ; [8,6] ; [13,10] ;[11,7]}
– Supprimer E(i-1).
– Pour chaque valeur v, garder au maximum un état
[u,v] dans E(i) avec u maximal.
• Retourner max [u,v] dans E(n) {u}

45
 MÉTHODES EXACTES
Programmation dynamique

États de l'ensemble E(i)

24 E(0)

E(1)
20 solution optimale
E(2)

15
E(3)

10

0 v
1 3 6 10

46
 MÉTHODES APPROCHÉES
Les méthodes approchées ont pour but de trouver une solution admissible en un temps
raisonnable, mais sans garantie l’optimalité de cette solution. L’avantage principale de ces
méthodes est qu'elles peuvent s'appliquer à n'importe quelle classe de problèmes, faciles ou très
difficiles. De plus, elles ont démontré leurs robustesses et efficacités face à plusieurs problèmes
d’optimisation combinatoires.
 Elles englobent deux classes : Heuristiques & Métaheuristiques

47
 MÉTHODES APPROCHÉES
Heuristiques:
Les heuristiques sont des règles empiriques simples basées sur l'expérience, ne fournissant pas
nécessairement une solution optimale.
Du fait de la relation forte entre l’ordre d’affectation des variables et la taille de l’arbre de
recherche développé, une « bonne » heuristique de branchement est déterminante pour l’efficacité
d’un algorithme de recherche.

48
 MÉTHODES APPROCHÉES
Méta-heuristiques:
Le mot Méta-Heuristique est dérivé de la composition de deux mots grecs:
 heuristique qui vient du verbe heuriskein (ευρισκειν) et qui signifie ‘trouver’
 méta qui est un suffixe signifiant ‘au-delà’, ‘dans un niveau supérieur’

Une Méta-heuristique peut être définie comme une méthode algorithmique capable de guider et
d’orienter le processus de recherche dans un espace de solution (souvent très grand) à des régions
riches en solutions optimales dans le but de trouver des solutions, peut-être pas toujours
optimales, en tout cas très proches de l’optimum, en un temps raisonnable.

49
 SUPPORTS COMPLÉMENTAIRES
 Introduction générale à l’optimisation combinatoire
 Branch & Bound
 Programmation dynamique
 Application Web pour tester des méthodes

50