Journées Franciliennes de Recherche Opérationnelle(24 Juin 2005)

Un algorithme de coupes pour le problème de l’affectation quadratique

Alain Faye , Frédéric Roupin

CEDRIC - IIE - CNAM

Plan

• Problèmes quadratiques en 0-1– Méthode polyédrique (PL)

– Programmation semi-définie (SDP)

• Affectation quadratique– Inégalités valides

– Résultats numériques en PL et SDP

min f (x) ciixii1n cijxixjj1, ji

ni1n

s.c. Ax b , x 0,1 n

Programme quadratique en 0-1

Localisation, placement de tâches sur des processeurs, affectation quadratique, partition de graphe, recherche de sous-graphes denses de cardinal fixé,...

3

Méthode polyédrique

Principe

• Linéariser f en posant xi xj = yi,j

5

Min f (x) s.c. xX {0,1}n

• LX = {(x,y): x X, yi,j = xi xj 1i<jn}

Lf = min

Direction du min de Lf

optimum

Pb: expliciter les facettes de P

• P = Conv(LX)

++

+

++

+

+ +

+

+

Programmation semi-définie

(Pb) min xtQx + ctxs.c. xtAix + di

t x = bi iIai

t x = bi i{1,…,p}

Problème en 0-1xi

2 - xi = 0 i{1,…,n}

7

=

min QY + ctx s.c. AiY + di

t x = bi iIai

t x = bi i{1,…,p}Y = x xt

y11 y12

y21 y22

x1x1 x1x2

x2x1 x2x2n=2

Relaxation semi-définie

Y ≽ x xt

(SDP)

≽

01

Yx

xt

0

1

22212

12111

21

yyx

yyx

xx

≽

≽

Problème en 0-1yii

- xi = 0 i{1,…,n}

Affectation quadratique

Blanchard , Elloumi , Faye , Wicker. Un algorithme de coupes pour l’affectation quadratique. INFOR 41 n°1 (2003).

Roupin. From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems. Journal of Combinatorial Optimization. Vol.8(4) (2004).

Faye, Roupin. A cutting planes algorithm based upon a semidefinite relaxation for the Quadratic Assignment Problem. Conférence ESA

2005. A paraître dans Lectures notes in computer science.

Affectation quadratique

min qijxijj1

n

i1

n

qij hk xijxhkk 1k j

n

h1hi

n

j1

n

i1

n

s.c.

xiji1

n 1 j N {1,... ,n}

xijj1

n

1 i N {1,..., n}

xij 0,1 i , j N {1,... ,n}

Polytope affectation quadratique Pn (Padberg, Rijal 96)

9

0 1 0 01 0 0 00 0 0 10 0 1 0

x =

n = 4

Enveloppe affine

Nix

Njx

n

jij

n

iij

1

1

1

1

Nkihixy

Njkhjxy

hk

n

jhkij

hk

n

ihkij

,,

,,

1

1

O(n3) contraintes

On peut « économiser » O(n2) contraintes (description minimale)Blanchard , Elloumi , Faye , Wicker. Une famille de facettes pour le polytope de l’affectation quadratique. Rapport de recherche 330 CNAM (2002)

10

Famille d’inégalités valides

Soit i, h, l 3 indices de lignes distincts et {j}, A, B une partition des indices de colonnes et C B

Exemple: n=5, i=2, h=4, l=3, j =1, A={2}, C={3,4}

y2133 y2134

y2142 y33 44 y33 45

y34 43 y34 45

1 2 3 4 5

12345

11

0 0

1 2 3 4 5

12345

11

0 0

11

Propriétés

• Inégalité induit une facette de Pn si C est un sous-ensemble propre de B

• Pb de séparation NP-difficile (Max-Cut se réduit à ce pb en temps polynomial)

• Résolution du pb de séparation par une heuristique

12

45**44**42**3321 yyyy 4221y

Recherche d’ inégalités violées

Soit i, h, l 3 indices de lignes et {j}, C={c} indices de colonnes,

trouver A, B,{j}, une partition des indices de colonnes et C B

Exemple: n=5, i=2, h=4, l=3, j =1, C={3}

13

453443343421 yyy

443543353521 yyy

422142**42334221 yyyy

443344**44334421 yyyy

453345**45334521 yyyy

On a A={2}, on va compléter C ={3}

4433y4533y

453443343421 yyy

C={3,4}

Njkihjiy

Nkihixy

Njkhjxy

Nix

Njx

yqxq

hkij

hk

n

jhkij

hk

n

ihkij

n

jij

n

iij

n

i

n

i

n

j

n

ihh

n

jkk

hkijhkij

n

jijij

,,,0

,,

,,

1

1

s.c.

min

1

1

1

1

1 1 1 1 11

PL initial

PL de Resende, Ramakrishnan, Drezner 9514

01

,

,,,0

1

1

,,

,,

1

1

s.c.

min

1 1

1 1

1

1

1

1

1 1 1 1 11

Yx

x

Njixy

Nkhjiy

Niy

Njy

Nkhixy

Nkhjxy

Nix

Njx

yqxq

t

ijijij

hkij

n

j

n

kikij

n

i

n

hhjij

hk

n

jhkij

hk

n

ihkij

n

jij

n

iij

n

i

n

i

n

j

n

h

n

khkijhkij

n

jijij

≽

SDP initial

15

Propriété de SDP initial

SB atteint solution quasi-optimale en assez peu d ’itérations

Spectral Bundle method (Helmberg)

Ex: Nug20. valeur optimale de SDP initial = 2503 (~15h)

en 1h30 valeur atteinte = 2492 > borne de Rendl-Sotirov

16

17

Quelques résultats numériques

PL

SDP

Comparaison des approches au niveau temps de calcul

18

19

Synthèse des résultats numériques

CPLEX9.0 pour PLsur Pentium IV

PL initial (Resende, Ramakrishnan, Drezner 95) SDP initial

SB method pour SDP

L ’ajout des coupes accélère la résolution du SDPmeilleure convergence de SB

20

Conclusion

• Ajout des coupes – améliore les relaxations classiques PL et SDP

au niveau de la borne– améliore la relaxation classique SDP au niveau

du temps de calcul

• Travaux futurs– attaquer problèmes plus gros n>30– améliorer le démarrage à « chaud » en SDP

21

FIN

Linéarisation produit (Adams, Sherali 86)

• remplacer produit xixj par une variable wi,j

(1) w i,j 0 (1i<jn)

(2) xi - wi,j 0 (1i<jn)

(3) xj - wi,j 0 (1i<jn)

(4) 1 - xi - xj + wi,j 0 (1i<jn)

• multiplication des contraintes par xi (1in)1j<in Aj wj,i + 1i<jn Ajwi,j (b- Ai) xi

• multiplication des contraintes par 1 - xi (1in)1j<in Aj (xj - wj,i ) + 1i<jn Aj(xj - wi,j ) b (1 - xi)

24

(Pb) min xtQx + ctxs.c. xtAix + di

t x = bi iIai

t x = bi i{1,…,p}

Problème en 0-1xi

2 - xi = 0 i{1,…,n}

25

Relaxation lagrangienne de (Pb) = dual de (SDP)(Lemaréchal, Oustry 99)

Relaxation semi-définie

(SDP) min QX + ctx s.c. AiX + di

t x = bi iIai

t x = bi i{1,…,p}X ≽ x xt

Recherche d’ inégalités valides violées

Soit i, h, l 3 indices de lignes et {j}, C={c} indices de colonnes,

trouver A, B,{j}, une partition des indices de colonnes et C B

Exemple: n=5, i=2, h=4, l=3, j =1, C={3}

26

45**44**42**3321 yyyy

453443343421 yyy

443543353521 yyy

45**44**42213321 yyyy

45**443342213321 yyyy

4533443342213321 yyyy

422142**42334221 yyyy

443344**44334421 yyyy

453345**45334521 yyyy

45344334

453344334221

3421

3321

yy

yyy

y

y

On a A={2} maintenant on va compléter C ={3}

Finalement C={3,4}

1 2 3 4 5

12345

11

0 0

1 2 3 4 5

12345

11

0 0

01

Yx

xt

0

1

22212

12111

21

yyx

yyx

xx

≽

≽

L ’ajout des coupes accélère la résolution du SDPmeilleure convergence de SB

had14

31