|
 
|
[BEL09c] Convex reformulations for binary quadratic programs
Conférence Internationale avec comité de lecture : EURO 2009, 23rd European Conference on Operational Research, July 2009, pp.47, Bonn, Germany,Mots clés: -Binary programming, Quadratic programming, Convex reformulation, Semi-definite programming, Experiments
Résumé:
-Let (QP) be a binary quadratic program that consists in minimizing a quadratic function subject to linear constraints. To solve (QP) we reformulate it into an equivalent program with a convex objective function. Our reformulation, that we call EQCR (Extended Quadratic Convex Reformulation), is optimal from the continuous relaxation bound point of view. We show that this best reformulation can be deduced from the solution of a semidefinite relaxation of (QP) and that EQCR outperforms QCR. We carry out computational experiments on Max-Cut and on the k-cluster problem.
Equipe:
oc
BibTeX
| @inproceedings { | |||
| BEL09c, | |||
| title | = | "{Convex reformulations for binary quadratic programs}", | |
| author | = | " A. Billionnet and S. Elloumi and A. Lambert ", | |
| booktitle | = | "{EURO 2009, 23rd European Conference on Operational Research}", | |
| year | = | 2009, | |
| month | = | "July", | |
| pages | = | "47", | |
| address | = | " Bonn, Germany", | |
| } | |||
