|
 
|
[BEL09] Résolution de programmes quadratiques en nombres entiers par reformulation convexe
Conférence Nationale avec comité de lecture : JPOC 6 (Journées Polyèdres et Optimisation Combinatoire) , June 2009, pp.15-18, Bordeaux, France,Mots clés: Programmation quadratique discrète, reformulation convexe
Résumé:
Ce problème entre dans la classe des problèmes difficiles [1]. Les solveurs standards peuvent
résoudre efficacement des programmes quadratiques en variables mixtes (MIQP), mais seulement
dans le cas spécifique où f(x) est une fonction convexe. Ainsi, pour résoudre (QP) nous le
reformulons en un programme équivalent dont la fonction objectif est quadratique et convexe,
puis nous le soumettons à un solveur standard. Concrètement, cela consiste à perturber la matrice
Q de (QP) dans le but d’obtenir une matrice semi définie positive. Une méthode classique
de résolution de programmes quadratiques convexes en nombres entiers consiste à appliquer un
algorithme de Branch and Bound. Il est connu que le comportement de cet algorithme dépend
de la qualité de la borne à la racine de l’arbre de résolution. C’est pourquoi, afin que notre
reformulation soit pertinente, nous cherchons une reformulation qui minimise l’écart entre la
solution optimale en nombres réels et la solution optimale en nombres entiers.
Equipe:
oc
BibTeX
| @inproceedings { | |||
| BEL09, | |||
| title | = | "{Résolution de programmes quadratiques en nombres entiers par reformulation convexe}", | |
| author | = | " A. Billionnet and S. Elloumi and A. Lambert ", | |
| booktitle | = | "{JPOC 6 (Journées Polyèdres et Optimisation Combinatoire) }", | |
| year | = | 2009, | |
| month | = | "June", | |
| pages | = | "15-18", | |
| address | = | "Bordeaux, France", | |
| } | |||
