Complexité des algorithmes exponentiels : application à lordonnancement Christophe LENTE Emmanuel NERON Ameur SOUKHAL Vincent TKINDT Laboratoire dInformatique

Complexité des algorithmes exponentiels : application à

l’ordonnancement

Christophe LENTEEmmanuel NERONAmeur SOUKHALVincent T’KINDT

Laboratoire d’Informatique (EA 2101)

Dépt. Informatique - Polytech’ToursUniversité François-Rabelais de Tours

[email protected]

Mathieu LIEDLOFF

Laboratoire d’Informatique Fondamental d’Orléans (EA 4022)

Université d’Orlé[email protected]

Complexité des méthodes exponentielles

Vincent T’kindt 2

Plan de la présentation

• Enjeux du calcul de la complexité d’algorithmes exponentiels,

• Présentation de techniques usuelles,

• Application à deux problèmes d’ordonnancement,– Problème d’ordonnancement d’intervalles avec multi-compétences,– Problème d’ordonnancement d’atelier de type Flowshop à deux

machines.


Vincent T’kindt 3

Enjeux

• On s’intéresse aux problèmes d’optimisation combinatoire,

Minimiser Z(x) sous contrainte x S

avec S, l’ensemble des solutions (définies par un ensemble de contraintes),

x, une solution, Z(x), le critère à minimiser.

(P)


Vincent T’kindt 4

Enjeux

• On s’intéresse à établir la complexité du problème (),

Classe P : temps polynomial (borné par p(Long)),

Classe NP-complet : temps non borné par p(Long),* Sens faible : temps borné par

p(Long, Max),* Sens fort : « exponentiel »

Classe NP-difficile : problèmes non montrés dans NP,


Vincent T’kindt 5

Enjeux

• Pour les problèmes de la classe P, étude de la complexité algorithmique :

– Complexité dans le pire des cas (notation O(X)),

– Un algorithme est en O(f(Long)) ssi sa complexité est bornée par un polynôme de f(Long),

Exemple: un algorithme est en O(n2) si sa complexité est bornée supérieurement par g(n2) avec g une fonction linéaire,


Vincent T’kindt 6

Enjeux

• Que se passe-t-il dans le pire des cas pour des problèmes NP-difficiles ?

a b

c

d

e f

g

Ensemble stable maximum (MAX-STABLE)

Entrée : un graphe G=(V,E)Objectif : trouver un plus grand stable de G, de cardinalité maximum.

Un ensemble S est stable si les sommets de S sont deux à deux non adjacents.


Vincent T’kindt 7

Enjeux

• Dans l’exemple du problème « Ensemble stable maximum »,

– Le problème est NP-difficile,– Objectif : est-il possible de calculer une borne supérieure à la

complexité dans le pire des cas d’une méthode exponentielle ?

• Trivialement, par énumération exhaustive : O(f(n).2n) O*(2n),• Peut-on faire mieux ? … oui en O*(1.2132n) !

Kneis, J., Langer, A., Rossmanith, P. (2009). A fine-grained analysis of a simple

independent set algorithm, Proceedings of the 29th Foundations of Software Technology and Theoretical Computer Science Conference (FSTTCS 2009).


Vincent T’kindt 8

Enjeux

• L’étude de la complexité d’algorithmes exponentiels connait un intérêt grandissant,

• Applications : problèmes issus de la théorie des graphes,

• Idée du projet : étudier comment les techniques de calcul peuvent être appliquées au domaine de l’ordonnancement,

• Union de compétences,– LIFO : compétences spécifiques en « algorithmes exponentiels »,

Mathieu Liedloff,– LI : compétences spécifiques en « ordonnancement »,

Christophe Lenté, Emmanuel Néron, Ameur Soukhal, Vincent T’kindt

• Projet subventionné par le GDR Recherche Opérationnelle (2009- ).


Vincent T’kindt 9

Quelques techniques usuelles

• Un certain nombre de techniques ont déjà été utilisées,

– Brancher & Réduire,– Inclusion-Exclusion,– Trier et Chercher,– Programmation dynamique,– Compression itérative,– Diviser pour Régner,– Recherche Locale,– …

techniques utilisées par la suite


Vincent T’kindt 10


• Les principes de la méthode Brancher & Réduire,

– Une des premières méthodes (début 1960),– Basée sur la construction d’un arbre de recherche,– On doit disposer d’une fonction d’évaluation du temps de calcul T,

P0

P1 P2

Branchement : Décomposition du problème T(P0) ≤ T(P1) + T(P2)

Réduction : Règle permettant à un nœud de réduire la taille de l’instance associée

Arrêt : règle définissant quand on sait résoudre en temps polynomial un sous problème Pj ou décider qu’il n’y a pas de solution pour Pj




• Les principes de Inclusion-Exclusion,

– Méthode particulière inspirée du dénombrement d’éléments présents dans l’union d’un nombre fini d’ensembles,

Exemple à 3 ensembles :|A1A2A3|= |A1|+|A2|+|A3|-|A1A2|-|A1A3| -|A2A3|+|A1A2A3|

A1

A2

A3

– Ce principe a notamment été appliqué sur le problème de k-coloration d’un graphe : algorithme en O*(2n) mais

espace exponentiel, Koivisto, M. (2006). An O*(2n) algorithm for graph coloring and other partitioning problems via inclusion- exclusion, Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 583- 590. Björklund, A., et Husfeldt, T. (2006). Inclusion-Exclusion algorithms for counting set partitions, Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 577-582.




• Trier & Chercher,

– Méthode basée sur le principe suivant : • Division en deux de l’instance,• Énumération des solutions pour chaque sous-instance (+tri),• Concaténation des solutions partielles pour trouver une solution à l’instance initiale.

I1 I2

instance I

S1

S2

O*(2n/

2) ?

x1 S1 x2 S2

x

Exemple : Problème du sac-à-dos.

* S1 trié par coût croissant, * S2 trié par poids croissant,

=> Recherche dichotomique sur S2

Algorithme en O*(2n/2) O*(1.4142n)



Problème d’ordonnancement d’intervalles• Définition du problème,

– n tâches à réaliser,– Chaque tâche i est définie par :

• Un intervalle Ii=[ri,Di] avec Dj=rj+pj,• Une compétence requise ci.

– m opérateurs sont disponibles,– Chaque opérateur Pj est défini par un ensemble Nj de compétences acquises.

– Existe-t-il un ordonnancement des opérateurs pour réaliser toutes les tâches ?

Problème polynomial si une seule compétence (coloration d’un graphe d’intervalles),

Problème NP-difficile dans le cas général.

I1 (P1,P3)

I2 (P2,P3)

I3 (P1,P3,P4)I5 (P1, P4)

I4 (P2,P3,P4)

I6 (P2,P3)

temps



Problème d’ordonnancement d’intervalles• Complexité de l’énumération basique Enum,

– On a au plus mn ordonnancement des opérateurs,

– Complexité en O*(mn) = O*(2n.log(m)),

I1 (P1,P3)

I2 (P2,P3)

I3 (P1,P3,P4)I5 (P1, P4)

I4 (P2,P3,P4)

I6 (P2,P3)

temps

I1 ,P1

I1 ,P3

I2, P2

I2, P2

I2, P3

I2, P3

…

n niveaux

au plus m nœuds fils par noeud


• 1ère approche : réduction au problème MAX-STABLE,

– Modélisation par un graphe ayant N=mn sommets au plus,– Le problème MAX-STABLE peut être résolu en O*(1.2132N),

=> Le problème d’ordonnancement est en O*(1.2132mn)– Meilleur que Enum dès lors que m ≤ 13,


Problème d’ordonnancement d’intervalles

I1 (P1,P3)

I2 (P2,P3)

I3 (P1,P3,P4)I5 (P1, P4)

I4 (P2,P3,P4)

I6 (P2,P3)

temps

(I4, P2)

(I4, P3)

(I3,P3)

(I1, P1)

(I1, P3)

(I3,P1) (I3,P4)

(I2, P3)(I2, P2)

(I4, P4)

(I5, P4)

(I5, P1)

(I6, P2)

(I6, P3)

P1

P1

P1

P3P2

P3


I2 (P2,P3)

• 2nde approche : réduction au problème LIST-COLORING,



I1 (P1,P3)

I2 (P2,P3)

I3 (P1,P3,P4)I5 (P1, P4)

I4 (P2,P3,P4)

I6 (P2,P3)

temps

I1 (P1 , P3)I3 (P1,P3,P4)

I4 (P2,P3,P4)I5 (P1, P4)

I6 (P2,P3)

Coloration de liste (LIST-COLORING)

Entrée : un graphe G=(V,E), une liste de couleurs autorisées par sommetQuestion : Existe-t-il une coloration des sommets de G ?


I2 (P2,P3)




I1 (P1,P3)

I2 (P2,P3)

I3 (P1,P3,P4)I5 (P1, P4)

I4 (P2,P3,P4)

I6 (P2,P3)

temps

I1 (P1 , P3)I3 (P1,P3,P4)

I4 (P2,P3,P4)I5 (P1, P4)

I6 (P2,P3)

– Par la méthode Inclusion-Exclusion le problème LIST-COLORING peut être résolu en temps O*(2n) et espace exponentiel,

Björklund, A., Husfeldt, T., M. Koivisto (2009). Set partitioning via Inclusion-Exclusion, SIAM Journal on

Computing, 39(2):546-563.


• 2nde approche : réduction au problème LIST-COLORING,– Résolution par la Programmation Dynamique,– On suppose que D1 ≤ D2 ≤ … ≤ Dn,– La fonction de récurrence Opt[i,l1,…,lm] est définie comme suit:

• i -> {1,..,i},• lj -> date de fin au plus tard des intervalles de couleur j (opérateur Pj),



I1 (P1,P3)

I2 (P2,P3)

I3 (P1,P3,P4)

temps

P1

P1

P3

l3

Opt[i,l1,…,lm]=vrai

Opt[i,l1,…,lm]=faux

Condition initiale : Opt[0, l1,…,lm]=vrai

S’il existe une coloration de liste sur l’ensemble {1,…,i} telle que j=1,…,m, il n’y a pas d’intervalle k{1,…i} de couleur j avec Dk>lj.

Sinon



– On pose Ri={1≤u≤m / Di lu et Ii peut être traité par Pu},– La fonction de récurrence Opt[i,l1,…,lm] peut être réécrite :



Opt[ i, l1 ,…, lm ]= uRi Opt[ i-1, l1 ,…, lu=ri ,…, lm] Faux i =1,…,n

Opt[0, l1,…,lm]=vrai l1,…,lm

I1 (P1,P3)

I2 (P2,P3)

I3 (P1,P3,P4)I5 (P1, P4)

I4 (P2,P3,P4)

I6 (P2,P3)

temps

i=3, u=4,Opt[3,l1,l2,l3,l4=r3]=vrai

l4

Pour chaque entrée de Opt[ ] on a n valeurs possibles :

=> complexité temporelle et spatiale en O*(n(m+1))

Le problème devient polynomial à m fixé.



– Fonctionnement de l’algorithme,(i) Calcul des m-uplets (l1,…,lm) pertinents en partant de i=m,

– …



(ii) Calcul des valeurs de Opt en partant de i=0,

n=4, m=3r=[0;2;1;4], D=[3;5;6;7], Dmax=7I1 (P1,P2)

I2 (P2,P3)

I3 (P1,P2,P3)

I4 (P1,P3)

temps

{1,2,3,4} => (7,7,7){1,2,3} => (4,7,7) et (7,7,4){1,2} => (4,1,7), (4,7,1), (1,7,4) et (7,1,4) {1} => (4,1,2), (4,2,1) et (1,2,4)=> (0,1,2), (0,2,1).

i (0,1,2)

(0,2,1)

0 Vrai Vrai

i (4,1,2)

(4,2,1)

(1,2,4)

1 Vrai Vrai Faux

…

Opt[ i, l1 ,…, lm ]= uRi Opt[ i-1, l1 ,…, lu=ri ,…, lm] Faux


• Comparaison des approches,



Enum MAX-STABLE

LIST-COLORING

LIST-COLORING (PD)

Complexité temporelle

O*(2n.log(m)

)O*(1.2132m.

n)O*(2n) O*(n(m+1))

LIST-COLORING (PD) domine LIST-COLORING si la relation suivante est vérifiée :

m n/log2(n) - 1

EnumMAX-STABLE

LIST-COLORING

m

temps

3 13



Problème d’ordonnancement flowshop

• Définition du problème,– 2 machines de traitement,– n travaux Ji à réaliser,– Chaque travail Ji est défini par :

• ai, sa durée sur la machine 1,• bi, sa durée sur la machine 2,• di, sa date de fin souhaitée.

– Flowshop : machine 1 -> machine 2,– Permutation : la séquence sur les 2 machines est la même,– Contrainte particulière : di=d, i=1,…,n, et d est à calculer.

temps

i

i

ai

bi

Ci,1 Ci,2 di

d

Machine 1

Machine 2

Une solution : une séquence s=( , , , , ), une date due commune d.




• Définition du problème,– Problème bicritère :

• Minimiser d,

• Minimiser U=i Ui avec Ui=1 si Ci,2>d (0 sinon).

– Approche -contrainte pour le calcul d’un optimum de Pareto, Minimiser d

sc U =

avec une valeur donnée

d=15 temps

U=2

F2UD est NP-difficile au sens faible.

Note : si on connait les travaux en avance, alors la valeur de d peut être obtenue en temps polynomial (ordre de Johnson)

F2UD

Jonhson, S.M. (1954). Optimal two and three stage production schedules with set-up time included, Naval Research Logistics Quarterly, 1:61-68.




• Complexité de l’énumération basique Enum,

– Arbre binaire (Ji en avance/en retard),

– Complexité en O*(2n),

J1 / A

J1 / R

J2 / A

J2 / R …

n niveaux

au plus 2 nœuds fils par noeud

J2 / A

J2 / R




• 1ère approche : Trier & Chercher (TriChe),

– Propriété préliminaire :

– On va créer deux tables T1 et T2 par division de l’instance,• Notations :• A(s) = is ai,• B(s) = is bi,• C(s) = Cmax(s).

• Propriété : Soient s1 et s2 deux sous-séquences telles que s=s1 // s2 est classée selon l’ordre de Johnson. On a Cmax(s)=max(A(s1)+C(s2);C(s1)+B(s2)).

A(s1)

C(s1)

C(s2)

B(s2)

Cmax(s)




• 1ère approche : Trier & Chercher (TriChe),• Notations :

• A(s) = is ai,• B(s) = is bi,• C(s) = Cmax(s),• Cmin(si) = min j≥i C(sj),• Bmin(si) = min j≥i B(sj).

• Table T1 : chaque colonne correspond à un ordonnancement sj de (n/2 - 1) travaux,

• Table T2 : chaque colonne correspond à un ordonnancement sk de (n/2 - 2) travaux,

avec = 1 +2.

=> Chaque table contient au plus 2n/2 colonnes.

Duplica

tion






• dmin=+• Pour 1=0../* max n +1 valeurs */

• Construire T1, T2, T2’ /* O*(2n/2) */• Pour s1 T1 /* O*(2n/2) */

• sj T2 / argmin(C(sj)-B(sj) ≥ C(s1)-A(s1))• dmin=min(dmin;A(s1)+Cmin(sj))

/*

O*(n/2) */

A(s1)Cmin(sj)

dmin ?

(n-1-2) travaux






• dmin=+• Pour 1=0../* max n +1 valeurs */

• Construire T1, T2, T2’ /* O*(2n/2) */• Pour s1 T1 /* O*(2n/2) */

• sj T2 / argmin(C(sj)-B(sj) ≥ C(s1)-A(s1))• dmin=min(dmin;A(s1)+Cmin(sj))

/*

O*(n/2) */

•sj T’2 / argmin(C(sj)-B(sj) ≤ C(s1)-A(s1))• dmin=min(dmin;C(s1)+Bmin(sj))

/* O*(n/2) */

dmin ?

(n-1-2) travaux

C(s1)

Bmin(sj)




• 1ère approche : Trier & Chercher (TriChe),

• L’algorithme TriChe est en O*(2n/2) O*(1.4142n) et espace exponentiel.




• 2nde approche : Brancher et Réduire (BraRed),– Etude en cours,– Basée sur l’hypothèse suivante :

Ji, on note niA (resp. ni

R) le nombre de travaux nécessairement en avance (resp. en retard) si Ji est ordonnancé en avance (resp. en retard).

• Comment calculer les niA et ni

R ? A l’aide de conditions de dominance.

Lemme : Soient deux travaux Ji et Jj tels que aiaj et bibj. Il existe un ordonnancement optimal dans lequel :

(i) Si Ji est ordonnancé en retard, Jj l’est également,

(ii) Si Jj est ordonnancé en avance, Ji l’est également.




• 2nde approche : Brancher et Réduire (BraRed),– Mesure du temps de calcul T(n,) :

T(n , ) = T(n-1-niA , ) + T(n-1-ni

R , -1-niR)

Posons u=n+. On a alors :

T(u) = T(u - 1 - niA) + T(u - 2 - 2ni

R).

– Cas le plus défavorable : i, max(niA,ni

R)=0.

Supposons que T(u)=cu. Par résolution numérique, on obtient :

T(u) 1.6180u = 1.6180(n+)

BraRed domine Enum dès que <n*100/227 0.44*n BraRed ne domine pas TriChe.

P0

P1 P2

Ji en avance

Ji en retard




• 2nde approche : Brancher et Réduire (BraRed),

– Cas « possible » : i, max(niA,ni

R)≥1.

Supposons que T(u)=cu. Par résolution numérique, on obtient :

T(u) 1.4142u = 1.4142(n+)

BraRed domine Enum BraRed ne domine pas TriChe.

– Extensions : autres mesures du temps T / définition de u.

P0

P1 P2

Ji en avance

Ji en retard


• Comparaison des approches,



Enum TriChe BraRed BraRed (2)

Complexité temporelle

O*(2n) O*(1.4142n) O*(1.6180n+) O*(1.4142n+)

Enum

BraRed

TriChe

n/

temps

0.4 1 0


• A priori intérêt purement théorique,

• Challenge : établir la complexité dans le pire des cas d’un algorithme exponentiel exact précis…

… et non pas mettre au point un algorithme exponentiel dont on peut calculer la complexité dans le pire des cas.


Conclusions

Documents

Complexité des algorithmes exponentiels : application à lordonnancement Christophe LENTE Emmanuel NERON Ameur SOUKHAL Vincent TKINDT Laboratoire dInformatique