Reformulation Quadratique Convexe en Programmation Quadratique en Variables 0-1 Sourour Elloumi CEDRIC-Cnam (Paris) Avec Alain Billionnet, Marie-Christine Plateau 1 Programmes quadratiques en 0-1 2 Exemple 3 Problmes dOptimisation Combinatoire: max-cut investissement partitionnement de graphes affectation quadratique . Rsolution exacte : difficile 4 Absence des termes quadratiques (Q=0) : Programmation Linaire en Nombres Entiers (PLNE) Chaque nud : -Calcul de borne inf. rapide : relaxation continue -Profite des calculs du pre -ventuellement, calcul de solution admissible ou borne sup. -Division de lensemble des solutions Branch objective -80 14 MIP simplex iterations 2 branch-and-bound nodes Sortie Cplex 9 Linarisation produit- Exemple Inconvnient : plus de contraintes (et ventuellement de variables) Avantage : meilleure relaxation continue Amlioration Adams et Sherali, 1984 10 Linarisation produit- Exemple Root relaxation solution time = 0.00 sec. Times (seconds): Input = 0.004 Solve = 0.002 Output = 0.001 CPLEX 8.1.0: optimal integer solution; objective -80 7 MIP simplex iterations 0 branch-and-bound nodes Sortie Cplex Temps de calcul plus important en chaque noeud 11 Linarisation Dautres Linarisations existent avec O(n) variables et contraintes Glover, 1975 Billionnet et Soutif, 2004 Billionnet, Plateau et E., 2007 12 Approche de rsolution II- Relaxation SDP et B objective -80 13 MIP simplex iterations 11 branch-and-bound nodes 27 Exemple- une autre convexification = 100 f convexe Nodes Cuts/ Node Left Objective IInf Best Integer Best Node ItCnt Gap 0 0 -166.0612 5 -166.0612 0 * 0+ 0 0 -79.0000 -166.0612 0 110.20% 1 1 -140.1798 4 -79.0000 -140.1798 1 77.44% 2 2 -104.5025 1 -79.0000 -112.1618 3 41.98% * 3 2 0 -80.0000 -91.5254 4 14.41% 4 1 -91.5254 4 -80.0000 -91.5254 5 14.41% 5 0 -91.5238 3 -80.0000 -91.5238 6 14.40% Times (seconds): Input = 0.004 Solve = 0.006 Output = 0 CPLEX 8.1.0: optimal integer solution; objective -80 6 MIP simplex iterations 5 branch-and-bound nodes 28 Critre : Meilleure convexification possible = minimise lerreur la racine Erreur croissante en fonction de Plus petit tel que Q s.d.p. : * = - plus petite valeur propre (Q) 29 Exemple- suite * = 56.88 Nodes Cuts/ Node Left Objective IInf Best Integer Best Node ItCnt Gap 0 0 -125.9702 4 -125.9702 0 * 0+ 0 0 -79.0000 -125.9702 0 59.46% * 1 0 0 -80.0000 -80.0000 1 0.00% Times (seconds): Input = 0.004 Solve = 0.005 Output = 0.002 CPLEX 8.1.0: optimal integer solution; objective -80 1 MIP simplex iterations 1 branch-and-bound nodes 30 Mthode de la plus petite valeur propre dj dcrite dans la littrature (et utilise dans cplex ?) Comment faire mieux ? c-d diminuer lerreur la racine maximiser la borne par relaxation continue 31 Amlioration 1 On gnralise la perturbation de la diagonale 32 Amlioration 2- Utilisation des contraintes dgalit pour perturber toute la matrice 33 Maximisation de la borne : trouver le meilleur (u,) relaxation continue (P) : Preuve utilisant la dualit lagrangienne et la convexit 34 (P) dual au sens de la programmation SDP de (SP) : var. duales 35 (SP)=(Rsdp) La rsolution de la relaxation SDP nous permet de calculer un (,u) optimal (SP) et (P) : mme valeur optimale on rcupre la borne de la relaxation SDP dans la reformulation convexe 36 Mthode de rsolution (QCR) Phase 1 : rsoudre (SP) et rcuprer les valeurs des variables duales (solveur SDP) Phase 2 : Rsoudre par PQNE (cplex, xpress) borne par relaxation continue la racine = v(SP) Rsum 37 Exemple- suite Phase 1 : u* et * calculs par SDP. Valeur optimale -88.02 Phase 2 : Nodes Cuts/ Node Left Objective IInf Best Integer Best Node ItCnt Gap 0 0 -88.0253 5 -88.0253 0 * 0+ 0 0 -79.0000 -88.0253 0 11.42% 1 1 -88.0202 3 -79.0000 -88.0205 2 11.42% 2 2 -87.8536 2 -79.0000 -87.9905 3 11.38% 3 2 -83.8531 2 -79.0000 -87.9905 5 11.38% 4 1 cutoff -79.0000 -87.9905 6 11.38% 5 0 -80.8175 2 -79.0000 -87.7886 9 11.12% 6 0 -80.1081 2 -79.0000 -80.1797 11 1.49% * 7 0 0 -80.0000 -80.0000 12 0.00% Times (seconds): Input = 0.003 Solve = 0.007 Output = 0.001 CPLEX 8.1.0: optimal integer solution; objective -80 12 MIP simplex iterations 7 branch-and-bound nodes 38 Discussion- QCR Amlioration de mthodes bases sur la programmation quadratique convexe Utilise des outils standard et puissants Utilisation originale de la programmation semidfinie positive (prtraitement) La mthode est optimale dans un schma de reformulation 39 Exprimenta