Master P6, Mention informatique, M2IAD Module DMDC 2010-2011
Exercices DMDC
Introduction à l'optimisation multicritère
Exercice - 1 Algorithme de Dijkstra multicritère
Appliquer l'algorithme de Dijkstra multicritère pour trouver les chemins e caces dans le graphe
suivant :
(0, 10, 12, 1)-
2 4
(10, 4, 2, 10) (10, 1, 1, 1)
6
(4, 0, 0, 3)
R
1 (6, 2, 10, 10) 6
(5, 1, 3, 7)
(6, 1, 18, 10) (6, 0, 0, 6)
R 3
(1, 4, 8, 1)
5
Exercice - 2 Algorithme de Ford multicritère
Appliquer l'algorithme de Ford multicritère pour trouver les chemins e caces dans le graphe sui-
vant :
2
>(−1, 0, 3)
(1, −1, 2)
~
1 (−1, 2, 4) 4
>
(0, 3, −2)
? (5, 3, 3)
3
~
Exercice - 3 Sac-à-dos multicritère
Le problème du sac-à-dos multicritère s'énonce comme suit :
Pn
max j=1 p1j xj
P.n. .
max j=1 pqj xj
Pn
s.c. j=1 wj xj ≤ b
xj ∈ {0, 1} ∀j ∈ {1, . . . , n}
où n désigne le nombre d'objets, q le nombre de critères, pij le pro t engendré par l'objet j sur le
critère i et wj le poids de l'objet j . Exhiber une instance bicritère générale pour laquelle il y a un
nombre exponentiel de solutions réalisables e caces de valeurs distinctes.
UPMC 1
Master P6, Mention informatique, M2IAD Module DMDC 2010-2011
Exercice - 4 Optimisation bicritère
On s'intéresse dans cet exercice au problème bicritère consistant à déterminer l'ensemble des sous-
ensembles e caces de cardinal p d'un ensemble à n éléments. On suppose ici qu'on cherche à
minimiser sur chacun des critères. Étant donné un ensemble E de cardinal n et une fonction
ϕ : E → N2 , il s'agit d'énumérer les sous-ensembles de cardinal p (p ≤ n) e caces (i.e., non-
dominés) au sens de Pareto. Par exemple, considérons l'ensemble E = {1, 2, 3} et posons p = 2.
Supposons que la fonction ϕ se dé nit ainsi : ϕ(1) = (2, 2), ϕ(2) = (1, 5) et ϕ(3) = (4, 3). Il y a
trois sous-ensembles de cardinal 2 : {1, 2}, {1, 3} et {2, 3}, de valeurs respectives (3, 7), (6, 5) et
(5, 8). Il y a donc deux sous-ensembles e caces qui sont {1, 2} et {1, 3}. Dans la suite de l'exercice,
pour simpli er, on se contentera de déterminer l'image de ces sous-ensembles dans l'espace des
critères (dans l'exemple, il s'agit de l'ensemble de vecteursP{(3, 7), (6, 5)}). L'image d'un sous-
ensemble S ⊆ E dans l'espace des critères sera notée ϕ(S) = i∈S ϕ(i). On va chercher à résoudre
l'instance suivante du problème : E = {1, 2, 3, 4, 5, 6, 7} (autrement dit n = 7) et p = 3. La fonction
ϕ se dé nit comme suit :
i 1 2 3 4 5 6 7
ϕ(i) (1,4) (2,3) (5,2) (2,2) (3,1) (2,5) (3,4)
L'objet de la question qui suit est d'établir les équations de récurrence qui permettront de
résoudre le problème par programmation dynamique multicritère. On désigne par OPT(i, j) l'image
dans l'espace des critères des sous-ensembles de cardinal i e caces dans {1, . . . , j}. Rappelons qu'il
s'agit d'un ensemble de vecteurs.
Question 1 - (2 pts) Donner l'expression de OPT(i, j) en fonction de OPT(i − 1, j − 1) et
OPT(i, j − 1). Pour ce faire, on utilisera la notation M (X) pour désigner l'ensemble des vecteurs
e caces dans un ensemble X de vecteurs, et la notation ϕ(i) + X pour désigner {ϕ(i) + x : x ∈ X}.
L'objet de la question suivante est de permettre l'initialisation de l'algorithme de programma-
tion dynamique.
Question 2 - (2 pts) Dé nir OPT(i, j) pour i > j puis pour i = 0.
Question 3 - (2 pts) Application numérique. Résoudre par programmation dynamique l'instance
numérique donnée plus haut. Les résultats seront présentés sous la forme d'un tableau comme
indiqué ci-dessous :
i\j 1 2 3 4 5 6 7
0
1
2
3
Exercice - 5 Plus court chemin biobjectif
L'objet de cet exercice est d'étendre au cas multiobjectif une méthode de calcul de borne inférieure
proposée dans le cadre d'un problème de plus court chemin standard (valuations scalaires). Cette
méthode fonctionne comme suit dans le cas standard.
Etant donné un graphe G = (V, E), un sommet d'origine v ∈ V , un sommet de destination
w ∈ V , et un sommet de référence r qu'on supposera proche de v , la méthode s'appuie sur la
connaissance des valeurs des plus courts chemins de r à tous les autres sommets de V (calculées
lors d'une phase de prétraitement, puis stockées en mémoire). En notant d(v, w) la valeur d'un
plus court chemin de v à w, et d(v) la valeur d'un plus court chemin de r à v , on se convaincra
facilement qu'on véri e : d(w) − d(v) ≤ d(v, w). La diérence d(w) − d(v) constitue donc une borne
inférieure de la valeur d'un plus court chemin de v à w.
UPMC 2
Master P6, Mention informatique, M2IAD Module DMDC 2010-2011
En optimisation multiobjectif, on sait qu'à la notion de borne se substitue la notion de couver-
ture,où un ensemble de vecteurs Y 0 couvre un ensemble Y si pour tout point de Y il existe un
point de Y 0 qui le domine au sens faible. Dans un contexte de plus court chemin multiobjectif, il va
donc s'agir de déterminer un ensemble de points qui couvrent l'image (dans l'espace des objectifs)
des chemins non-dominés entre v et w, en s'appuyant sur un point de référence r. Considérons
l'exemple biobjectif suivant : on suppose qu'on dispose de l'image D(v) = {(1, 3), (2, 1)} des che-
mins non-dominés de r à v , et de l'image D(w) = {(4, 8), (6, 7), (7, 3)} des chemins non-dominés de
r à w. En proposant une extension de la méthode proposée dans le cas standard, en déduire une
couverture (i.e., un ensemble de vecteurs) de l'image D(v, w) des chemins non-dominés de v à w.
UPMC 3
