Vignette ROSP

Séminaire ROSP jeudi 10 décembre 2015 à 14h - Sourour Elloumi (ENSIIE / CEDRIC)

Le prochain séminaire ROSP se déroulera le jeudi 10 décembre à 14h en salle C319 avec un exposé de Sourour Elloumi (ENSIIE / CEDRIC) ayant pour titre "Linéarisation et reformulation quadratique convexe pour l'optimisation quadratique".


Linéarisation et reformulation quadratique convexe pour l'optimisation quadratique




Nous considérons le problème (QP) de la minimisation d’une fonction quadratique sous des contraintes linéaires ou quadratiques. Les variables sont entières ou réelles, et bornées. Ce problème très général permet de modéliser de nombreux problèmes classiques en Optimisation Combinatoire et constitue une première généralisation de la programmation linéaire en nombres entiers.

Une différence majeure entre (QP) et les programmes linéaires en nombres entiers réside dans le fait que, en général, sa relaxation continue fournit un problème lui aussi NP-difficile. Pour contourner cette difficulté, la reformulation quadratique convexe transforme (QP) en un problème (QP') équivalent mais dont la relaxation continue est un problème convexe. Afin de calculer une solution optimale de (QP), on peut alors résoudre (QP') par un algorithme d'énumération implicite basé sur l'optimisation continue convexe.

Nous faisons un tour d'horizon de développements récents de cette approche. Nous montrons en particulier comment les relaxations semi-définies positives permettent de construire les problèmes équivalents (QP') les plus intéressants. Dans le cas des variables binaires, nous donnons une vision des linéarisations classiques comme un cas particulier de reformulation quadratique convexe.

Enfin, nous illustrons la généralité et l’efficacité expérimentale de la résolution exacte par reformulation quadratique convexe sur différents problèmes d’Optimisation Combinatoire.

Références :
 
  • A. Billionnet et S. Elloumi. Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem . Mathematical Programming, 109(1): 55-68, 2007.
  • A. Billionnet, S. Elloumi et M.-C. Plateau. Improving standard solvers convex reformulation for constrained quadratic 0-1 programs: the QCR method. Discrete Applied Math, vol. 157(6), 2009, pp. 1185-1197.
 
  • A. Billionnet, S. Elloumi et A. Lambert. Extending the QCR method to general mixed-integer programs. Mathematical Programming, vol. 131(1), 2012, pp.381-401