Aller au menu Aller au contenu
Recherche Opérationnelle et Systèmes de Production
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Recherche Opérationnelle et Systèmes de Production
Recherche Opérationnelle et Systèmes de Production
< >

> GSCOP_Recherche > GSCOP_RechercheOpérationnelle

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

Publié le 7 décembre 2015
A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo
Colloque / Séminaire 10 décembre 2015

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

Vignette ROSP

Vignette ROSP


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


A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo

mise à jour le 8 décembre 2015

  • Tutelle CNRS
  • Tutelle Grenoble INP
  • Université Joseph Fourier
  • Tutelle UMR
Univ. Grenoble Alpes