Lemaréchal, Claude
- Oustry, François
Rapport de recherche de l'INRIA -
Rhone-Alpes ,
Equipe :
NUMOPT 40 pages - Juin 1999 - Document en anglais
Titre français : Relaxations semi-définies et dualité lagrangienne avec applications en
optimisation combinatoire
Abstract : We show that it is fruitful to dualize the integrality constraints in a combinatorial optimization problem. First, this reproduces the known SDP relaxations of the max-cut and max-stable problems. Then we apply the approach to general combinatorial problems. We show that the resulting duality gap is smaller than with the classical Lagrangian relaxation; we also show that linear constraints need a special treatment.
Résumé : Nous montrons qu'il est fructueux de dualiser les contraintes d'intégralité d'un problème d'optimisation combinatoire. Tout d'abord, ceci reproduit la relaxation SDP classique pour les problèmes de la coupe maximum et du stable maximum. Nous appliquons ensuite cette approche à des problèmes combinatoires généraux. Nous montrons que le saut de dualité résultant est meilleur que celui de la relaxation lagrangienne classique. Nous montrons également que les contraintes linéaires nécessitent un traitement particulier.
Key-Words : COMBINATORIAL OPTIMIZATION / LAGRANGIAN RELAXATION / SDP RELAXATION / DUALITY /
QUADRATIC CONSTRAINTS / LINEAR MATRIX INEQUALITIES
Mots-clés : OPTIMISATION COMBINATOIRE / RELAXATION LAGRANGIENNE / RELAXATION SDP / DUALITÉ
/ CONTRAINTES QUADRATIQUES / INÉGALITÉS MATRICIELLES LINÉAIRES
