Mai 2001FRANCOROIII - Challenge 20011 Recherche Locale Guidée Par Le Coût Des Contraintes Gavranovic Haris Univerzitet U Sarajevu IMAG, Grenoble

mai 2001 FRANCOROIII - Challenge 2001 1

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

Gavranovic HarisUniverzitet U Sarajevu

IMAG, Grenoble


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


1

2

34

7

6

8

9

5

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


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)


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é.


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


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


{1,2,…,100}

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

{1,2,…,100}1 2

43

6060

55

3030

20

909080

6161

51


{1,2,…,49}1 2

43

6060

55

909080

616151

{1,2,…,20}

{81,82,…,100}


{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)


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.


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


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


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)


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


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}


Réduction de l’espace de recherche


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


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.


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


A B

Nmb de combinaison = n * m

réduction

Nmb de combinaison min ( n , m) * 2


Recherche locale


)()()(

22:),( k

ij

jikij

ji

jik

ppppffjiV

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

1

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

ik VVkMPFTc

La fonction à minimiser:


0,0,

22 1

sinon 0 jfif

kij

jpipkij

jpip

jfif

kijV

CEM scontrainte

)(

lestoutespout

kij

k VV


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


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


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.


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:


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:


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.


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.


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)


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)


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)


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


{64,65,…,100}

{1,2,…,37}1 2

43 4

707063

{1,2,…,100}

565646


{64,65,…,100}

{1,2,…,37}1 2

43 4

707063

{1,2,…,53}

565646

5353

50


{64,65,…,100}

1 2

43 4

707063

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

565646

5353

50

2525

10

{11,12,…,100}

Documents

Mai 2001FRANCOROIII - Challenge 20011 Recherche Locale Guidée Par Le Coût Des Contraintes Gavranovic Haris Univerzitet U Sarajevu IMAG, Grenoble