1/3
2/3
3/3
Introduction
MTH6311
S. Le Digabel, Ecole
Polytechnique de Montr
eal
H2014
(v2)
MTH6311: Introduction
1/16
1/3
2/3
3/3
Plan
1. Introduction
2. Exemples de probl`
emes
3. Algorithmes
MTH6311: Introduction
2/16
1/3
2/3
3/3
1. Introduction
2. Exemples de probl`
emes
3. Algorithmes
MTH6311: Introduction
3/16
1/3
2/3
3/3
Optimisation combinatoire
I
Loptimisation combinatoire est un domaine qui etudie les
probl`emes de la forme
min{f (x) : x }
xX
o`
u X est un ensemble discret et fini et X est lensemble
des solutions realisables. La fonction objectif f prend ses
valeurs sur X .
I
En theorie, une solution optimale peut etre obtenue en
enumerant toutes les solutions realisables et en conservant la
meilleure.
En pratique, ce procede est trop long. Meme lenumeration
peut poser probl`eme : comment formuler une solution
realisable ?
MTH6311: Introduction
4/16
1/3
2/3
3/3
Optimisation combinatoire
I
On veut donc resoudre ce probl`eme en un temps raisonnable,
que lon va etudier grace aux outils de la theorie de la
complexite.
On apprendra `a distinguer les probl`emes dits faciles des
probl`emes difficiles.
Pour les faciles, une resolution exacte en un temps court est
envisageable.
Un grand nombre de probl`emes sont difficiles. Des solutions
exactes sont envisageables, mais dans un delai acceptable, on
se contentera de solutions approchees obtenues par des
methodes heuristiques.
Certaines proprietes seront toutefois obtenues (garantie de
performance, ecart `a la solution optimale, etc.)
MTH6311: Introduction
5/16
1/3
2/3
3/3
Notions
Notions mathematiques de base.
Modelisation.
Theorie des graphes.
Conception dalgorithmes et programmation.
MTH6311: Introduction
6/16
1/3
2/3
3/3
1. Introduction
2. Exemples de probl`
emes
3. Algorithmes
MTH6311: Introduction
7/16
1/3
2/3
3/3
Probl`
eme v.s. Instance
I
Un probl`eme correspond au mod`ele
min{fa (x) : x a }
xX
dans lequel a est un ensemble de param`etres non determine
(cest le cas general).
I
Une instance du probl`eme est une formulation du mod`ele dans
laquelle a est determine (cest un cas particulier).
En pratique, on concoit souvent des algorithmes pour des
probl`emes, quon teste sur plusieurs instances.
On peut aussi sinteresser `a une seule instance ou a une
famille dinstances particuli`eres. Dans ce cas on concevra une
methode plus specialisee.
MTH6311: Introduction
8/16
1/3
2/3
3/3
Voyageur de commerce (TSP)
I
Un voyageur de commerce doit visiter un certain nombre de
villes, et chaque ville une et une seule fois. Etant
donne des
distances entre chaque paire de villes, il doit minimiser la
distance totale parcourue.
MTH6311: Introduction
9/16
1/3
2/3
3/3
TSP : variation pour distribution de courier
The Times and The Sunday Times e-paper - News Review - 6 Jan 2013 -...
MTH6311: Introduction
[Link]
10/16
1/3
2/3
3/3
TSP (suite)
I
On peut representer ce probl`eme par un graphe : chaque ville
correspond `a un sommet et chaque arete `a une paire de villes
pouvant etre visitees lune `a la suite de lautre.
Le probl`eme correspond `a trouver un tour complet (circuit
Hamiltonien) dans ce graphe qui minimise la somme des
distances (f ).
Lensemble X correspond `a un chemin dans le graphe, soit
une liste de villes, et lensemble X est lensemble des
circuit Hamiltoniens.
Le nombre de solutions pour n villes est de (n 1)!/2. Si
n = 4, il y a trois solutions possibles. Si n = 30, il y en a
4 420 880 996 869 850 977 271 808 000 000 !
Voir liens sur le site web.
MTH6311: Introduction
11/16
1/3
2/3
3/3
Probl`
eme daffectation
I
I
I
I
I
n taches `a affecter `a n machines de telle sorte que chaque
machine soit affectee `a une seule tache et chaque tache soit
affectee `a une seule machine.
Le co
ut daffecter la tache j `a la machine i est cij .
Lobjectif est de minimiser la somme des co
uts
est lensemble de toutes les affectations possibles des n
taches aux n machines. Il y en a n!.
Mod`ele en variables binaires :
n X
n
X
min
f (x) =
cij xij
xX ={0,1}n
i=1 j=1
Pn
x = 1, i = 1, 2, . . . , n
Pnj=1 ij
sujet aux 2n contraintes
i=1 xij = 1, j = 1, 2, . . . , n
(cest lensemble ).
MTH6311: Introduction
12/16
1/3
2/3
3/3
Liste non exhaustive de probl`
emes
Colorations de graphes.
Routage.
Satisfaisabilite.
Classification.
Horaires.
Botes noires (projet).
MTH6311: Introduction
13/16
1/3
2/3
3/3
1. Introduction
2. Exemples de probl`
emes
3. Algorithmes
MTH6311: Introduction
14/16
1/3
2/3
3/3
Algorithme
Un algorithme est la description dune sequences dinstructions `a
entreprendre afin de resoudre un probl`eme. Par exemple :
MTH6311: Introduction
15/16
1/3
2/3
3/3
Il faut choisir un algorithme selon les exigences sur la qualite de la
solution et le temps de calcul. Ces objectifs sont souvent
contradictoires.
I Algorithmes exacts : garantissent une solution optimale
globale mais peuvent etre tr`es longs si le probl`eme est difficile.
I
I
I
Algorithmes locaux : garantissent une solution locale.
I
I
Separation et evaluation (branch and bound).
Programmation lineaire pour loptimisation continue.
Programmation dynamique.
Methodes de descente.
Gradient / Newton pour loptimisation continue.
Metaheuristiques : tr`es peu de garanties sur la qualite de la
solution, mais convergent rapidement.
I
I
I
I
Algorithme glouton.
Recherche tabou.
Recherche `a voisinages variables (VNS).
Algorithmes genetiques.
MTH6311: Introduction
16/16
