Mai 2001FRANCOROIII - Challenge 20011 Recherche Locale Guidée Par Le Coût Des Contraintes...

mai 2001 FRANCOROIII - Challenge 2001 1

Recherche Locale Guidée Par Le Coût Des Contraintes

Gavranovic HarisUniverzitet U Sarajevu

IMAG, Grenoble

mai 2001 FRANCOROIII - Challenge 2001 2

Plan

Les remarques générales sur le problèmes, ses instances, la modélisation et la méthode de résolution

La description et les étapes de la méthode implémentée

i. Propagation des contraintes CEM et la détermination du niveau minimal réalisable

ii. Détermination d’une ‘bonne’ polarisationiii. Réduction de l’espace de recherche iv. Recherche locale

Les résultats numériques et les perspectives

mai 2001 FRANCOROIII - Challenge 2001 3

1

2

34

7

6

8

9

5

CEM contraintesContre. fortes sur fréq.Contre. sur polar.

mai 2001 FRANCOROIII - Challenge 2001 4

1

2

34

7

6

8

9

5

(4) (3)

(7) (2)

(7) (6)

La fôret de polarisations avec cinq arbres de polarisation

(1) = -1 et (4) = -1 signifie (1) (4)

mai 2001 FRANCOROIII - Challenge 2001 5

On peut remarquer qu’une affectation de polarisations est équivalent à un arbre de polarisation.

Nous allons d’abord construire un arbre de polarisations pour procéder à l’affectation de fréquences.

La construction de l’arbre de polarisation est déterminée par les valeurs et des contraintes CEM au niveau k* donné.

mai 2001 FRANCOROIII - Challenge 2001 6

1

2

3

7

6

8

9

5

|f2 – f3| = 36

4

f2 = f3

Le forêt de fréquences avec sept arbres de fréquences

mai 2001 FRANCOROIII - Challenge 2001 7

Propagation des contraintes CEM et la détermination du niveau minimal réalisable

mai 2001 FRANCOROIII - Challenge 2001 8

{1,2,…,100}

{1,2,…,100}{1,2,…,100}

{1,2,…,100}1 2

43

6060

55

3030

20

909080

6161

51

mai 2001 FRANCOROIII - Challenge 2001 9

{1,2,…,49}1 2

43

6060

55

909080

616151

{1,2,…,20}

{81,82,…,100}

mai 2001 FRANCOROIII - Challenge 2001 10

{97,98…,100}

1 2

43 4

707063

{1,2,3}{51,52,53}

565646

5353

50

2525

10

{11,12,…,100}

(1) (2)

(1) (3)(2) (4)

mai 2001 FRANCOROIII - Challenge 2001 11

Détermination d’une ‘bonne’ polarisation

Tant qu’il y a plusieurs arbres de polarisations

1. Ajouter la contrainte (i) (j) pour la CEM contraintes qui réduit le plus les domaines de fréquences sur ces extrémités

2. Réduire les domaines et déterminer les orientations avec de nouvelles valeurs sur CEM contraintes et retourner à 1.

mai 2001 FRANCOROIII - Challenge 2001 12

1

2

34

7

6

8

9

5

{55,…,65}

{55,…,65} {1,2,…,76}

{1,2,…,100}

{1,2,…,100}

{1,2,…,61}

{69,..,100}

{25,..,40}

{25,..,40}

0

35192020

2223235

99

303027

155

202323

394141

303535

36

141616

202222

404545

Exemple2: niveau 7

mai 2001 FRANCOROIII - Challenge 2001 13

1

2

34

7

6

8

9

5

{55,…,65}

{55,…,65} {1,2,…,76}

{1,2,…,100}

{1,2,…,100}

{1,2,…,61}

{69,..,100}

{25,..,40}

{25,..,40}

0

35192020

2223235

99

303027

155

202323

394141

35

36

141616

202222

404545

mai 2001 FRANCOROIII - Challenge 2001 14

1-

2-

3+4+

7-

6+

8+

9-

5-

Sommet de référence

(4) (3)

(7) (2)

(7) (6)

(1) (4)

(8) (9)

(6) (9)

(5) (6)

(4) (5)

mai 2001 FRANCOROIII - Challenge 2001 15

1

2

34

7

6

8

9

5

{55,…,65}

{55,…,65} {1,2,…,76}

{1,2,…,100}

{1,2,…,100}

{1,2,…,61}

{69,..,100}

{25,..,40}

{25,..,40}

0

35192020

2223235

99

303027

155

202323

394141

303535

36

141616

202222

404545

mai 2001 FRANCOROIII - Challenge 2001 16

1

2

34

7

6

8

9

5

0

3519

235

301

23

39

30

36

14

20

45

{55,…,65}

{55,…,65} {1,2,…,76}

{1,2,…,100}

{1,2,…,100}

{1,2,…,61}

{70,..,100}

{25,..,40}

{25,..,40}

mai 2001 FRANCOROIII - Challenge 2001 17

Réduction de l’espace de recherche

mai 2001 FRANCOROIII - Challenge 2001 18

1

2

3

35

{1,2,…,76}

{25,..,40}

{25,..,40}

Nombre total de combinaisons est à priori

76 * 16 * 16 = 19456 |f2 – f3| = 36

f2 = f3

mai 2001 FRANCOROIII - Challenge 2001 19

1

2

3

35

{1,2,…,76}

{25,..,40}

{25,..,40}

|f2 – f3| = 36

f2 = f3

f1 f2 f3

25 25 61

26 26 62

27 27 63

28 28 64

29 29 65

30 30 66

31 31 67

…….. ….. ….

36 36 72

37 37 1

37 37 73

38 38 2

38 38 74

……. ….. ….

40 40 76

Nombre total de combinaisons est 20.

mai 2001 FRANCOROIII - Challenge 2001 20

La structure de la forêt de fréquences dans les instances du problème

mai 2001 FRANCOROIII - Challenge 2001 21

A B

Nmb de combinaison = n * m

réduction

Nmb de combinaison min ( n , m) * 2

mai 2001 FRANCOROIII - Challenge 2001 22

Recherche locale

mai 2001 FRANCOROIII - Challenge 2001 23

)()()(

22:),( k

ij

jikij

ji

jik

ppppffjiV

0:),( )0()0( ijijji

1

)()1(2 1010),,,(ki

ik VVkMPFTc

La fonction à minimiser:

mai 2001 FRANCOROIII - Challenge 2001 24

0,0,

22 1

sinon 0 jfif

kij

jpipkij

jpip

jfif

kijV

CEM scontrainte

)(

lestoutespout

kij

k VV

mai 2001 FRANCOROIII - Challenge 2001 25

A B

2

0

)1(2 10 k 10 j)i,M,F,T,c(C,k

l

lij

kij VV

0,0,

22 1

sinon 0 jfif

kij

jpipkij

jpip

jfif

kijV

arbreF dans ou

j)i,M,F,T,c(C, arbreF)M,F,T,c(C,ji

mai 2001 FRANCOROIII - Challenge 2001 26

Phase de l’initialisation:

1. Affecter à tous les trajets la fréquence ‘zéro’

2. Affecter à tous les arbre de fréquence la combinaison de fréquences qui minimise le coût C(C,T,F,M,arbreF)

3. Ordonner la liste d’arbres de fréquences suivant leur coûts et recommencer avec l’étape 1

mai 2001 FRANCOROIII - Challenge 2001 27

La recherche principale: recherche locale pilotée par le coût des contraintes

La partie principale de la recherche est constituée de deux types de procédures appliquées en alternance: la procédure légère et la procédure lourde.

mai 2001 FRANCOROIII - Challenge 2001 28

1. Ordonner les arbres de fréquences suivant leurs coûts associés

2. Pour chaque arbre de fréquences: Affecter la combinaison de fréquences qui minimise le coût associé

3. Ordonner les contraintes suivant leurs coûts

4. Pour chaque contrainte dont le coût dépasse la valeur 10*2*k (la contrainte est violée au niveau k) faire:

ou bien

• Construire un seul arbre avec les combinaisons de fréquences qui satisfont la contrainte au niveau k à partir de deux arbres liés par cette contrainte. Trouver la combinaison optimale.

ou bien:

• Trouver deux combinaisons de fréquences associées aux deux arbres qui satisfont la contrainte au niveau k et minimise la somme des coûts associés.

Les deux procédures ont la forme suivante:

mai 2001 FRANCOROIII - Challenge 2001 29

1. Ordonner les arbres de fréquences suivant leurs coûts associés

2. Pour chaque arbre de fréquences: Affecter la combinaison de fréquences qui minimise le coût associé

3. Ordonner les contraintes suivant leurs coûts associés

4. Pour chaque contrainte dont le coût dépasse la valeur 10*2*k (la contrainte est violée au niveau k) faire:

• Construire un seul arbre avec les combinaisons de fréquences qui satisfont la contrainte au niveau k à partir de deux arbres liés par cette contrainte. Trouver la combinaison optimale.

ou bien:

• Trouver deux combinaisons de fréquences associées aux deux arbres qui satisfont la contrainte au niveau k et minimise la somme des coûts associés.

Les deux procédures ont la forme suivante:

mai 2001 FRANCOROIII - Challenge 2001 30

4…Construire un seul arbre avec les combinaisons de fréquences qui satisfont la contrainte au niveau k à partir de deux arbres liés par

cette contrainte. Trouver la combinaison optimale.

La procédure légère ne construit que de relativement petits arbres de fréquences (moins de quatre trajets et ayant au plus 600 combinaisons).

La procédure lourde peut construire des arbres de fréquences avec huit trajets et ayant au plus 50000 combinaisons.

mai 2001 FRANCOROIII - Challenge 2001 31

Recherche locale pilotée par le coût des contraintes

1. Phase de l’initialisation; k = 10;

2. Tant qu’il y a du temps

3. Tant qu’il y a des contraintes violées au niveau k

• Applique la procédure légère 40 fois

• Appliquer la procédure lourde 3 fois

• Reconstruire les arbres de fréquences du départ

• k = k – 1; Retourner à l’étape 3.

mai 2001 FRANCOROIII - Challenge 2001 32

k* viols au niveau k* - 1 cumul des viols ( i < (k* - 1) contr. fortes violées fapp01 4 4* 12 184fapp02 2 2* 19 365fapp03 7 7* 19 989fapp04 3 3 9 457fapp05 11 1 2933fapp06 6 6 20 1470fapp07 10 10 16 4332fapp08 5 5* 37 1419fapp09 3 4 18 1018 1fapp10 6 6* 39 2331fapp11 9 9 47 6719 1fapp12 5 6 15 2901 1fapp13 8 9 51 11253fapp14 7 9 47 12325 2fapp15 9 10 106 19346

Instances du problème (phase1)

mai 2001 FRANCOROIII - Challenge 2001 33

k* viols au niveau k* - 1 cumul des viols ( i < (k* - 1) contr. fortes violées fapp16 11 59 1663fapp17 4 4 74fapp18 8 4 118fapp19 6 2 106fapp20 10 5 203fapp21 4 3 31fapp22 7 15 389fapp23 9 16 392fapp24 7 7 165fapp25 3 7 71 1fapp26 7 9 159fapp27 5 9 91fapp28 3 20 116fapp29 6 25 449fapp30 7 17 437

Instances du problème (phase2)

mai 2001 FRANCOROIII - Challenge 2001 34

k* viols au niveau k* - 1cumul des viols ( i < (k* - 1)contr. fortes violées test01 4 4* 5 273test02 7 7* 13 697test03 4 5 24 714 1test04 9 9 66 8442

Instances du problème (test)

mai 2001 FRANCOROIII - Challenge 2001 35

Conclusion

•La méthode est encore inefficace pour les instances de grande taille

•La recherche locale pilotée par le coût des contraintes a montre ses qualité sur le FAP sans polarisations

•La façon de déterminer les polarisation est une heuristique. Nous ne voyons pas d’améliorations importantes dans cette direction.

•La perspective prometteuse peut être la recherche locale qui affecte au même temps les polarisations et les fréquences

mai 2001 FRANCOROIII - Challenge 2001 36

{64,65,…,100}

{1,2,…,37}1 2

43 4

707063

{1,2,…,100}

565646

mai 2001 FRANCOROIII - Challenge 2001 37

{64,65,…,100}

{1,2,…,37}1 2

43 4

707063

{1,2,…,53}

565646

5353

50

mai 2001 FRANCOROIII - Challenge 2001 38

{64,65,…,100}

1 2

43 4

707063

{1,2,3}{51,52,53}

565646

5353

50

2525

10

{11,12,…,100}