|
 
|
[Ell12] A unified view of linear and quadratic convex reformulations for binary quadratic programming
Conférence Internationale avec comité de lecture : ISMP, August 2012, pp.1 page, Berlin, Allemagne,Mots clés: Binary quadratic programming, linearization, quadratic convex reformulation
Résumé:
We consider binary quadratic programs (QP) having a quadratic objective
function, linear constraints, and binary variables. Many classical solution methods of
these problems are based on exact reformulation of QP into an
equivalent mixed integer linear program. Several linearization methods were
studied in the literature. More recent solution methods also
build an exact reformulation but into a problem which objective function is
quadratic and convex. A common point of the two approaches is that the
continuous relaxation of the reformulated problem is a convex optimization
problem that can be solved in polynomial time. This makes it possible to use a general branch-and-bound framework to solve the reformulated problem and even to rely on the strongness of standard solvers.
In this paper, we show that several quadratic convex reformulation methods, as well as classical linearization, can be viewed within a unified framework. This shows the non-surprising result that linearization is a particular quadratic convex reformulation on the one hand. On the other hand, it allows to compare these methods from a theoretical point of view.
Equipe:
oc
BibTeX
| @inproceedings { | |||
| Ell12, | |||
| title | = | "{A unified view of linear and quadratic convex reformulations for binary quadratic programming}", | |
| author | = | " S. Elloumi ", | |
| booktitle | = | "{ISMP}", | |
| year | = | 2012, | |
| month | = | "August", | |
| pages | = | "1 page", | |
| address | = | "Berlin, Allemagne", | |
| } | |||
