|
 
|
[Ell14a] Quadratic Convex Reformulation for discrete quadratic optimization : Basic results and recent extensions
Conférences invitées : PGMO-COPI'14, October 2014, pp.66,
motcle:
Résumé:
We consider problem (QP) of minimizing a quadratic function subject to linear or quadratic constraints. Variables are integer and bounded. This very general problem can model many classical problems in Combinatorial Optimization.
A major difference between (QP) and integer linear programs lies in the fact that, in general, its continuous relaxation is an NP-hard optimization problem. To overcome this difficulty, the Convex Quadratic Reformulation approach transforms (QP) into a problem (QP'), equivalent to (QP), but whose continuous relaxation is a convex problem. To compute a global optimal solution to (QP) it becomes possible to solve (QP') by an implicit enumeration algorithm based on continuous convex optimization.
We make an overview of recent developments in this approach. We show in particular how positive semidefinite relaxations can be used to build the most interesting equivalent problems (QP'). In the case of binary variables, we give a vision of classical linearization as a special case of Convex Quadratic Reformulation.
Finally, we illustrate the generality and the computational efficiency of the Quadratic Convex Reformulation approach for several combinatorial optimization problems.
Equipe:
oc
BibTeX
| @inproceedings { | |||
| Ell14a, | |||
| title | = | "{Quadratic Convex Reformulation for discrete quadratic optimization : Basic results and recent extensions}", | |
| author | = | " S. Elloumi ", | |
| booktitle | = | "{PGMO-COPI'14}", | |
| year | = | 2014, | |
| month | = | "October", | |
| pages | = | "66", | |
| } | |||
