|
 
|
[BEL10b] Solving a general mixed-integer quadratic problem through convex reformulation : a computational study
Atelier, Poster ou Démonstration dans une Conférence Internationale : European Workshop on Mixed Integer Nonlinear Programming, April 2010, pp.197-204, Marseille, France,Mots clés: mixed-integer quadratic programming, convex reformulation, semidefinite programming, experiments
Résumé:
Abstract. Let (QP) be a mixed integer quadratic program that consists of minimizing a quadratic function subject to linear constraints. In this paper, we present a convex reformulation of (QP), i.e. we reformulate (QP) into an equivalent program, with a convex objective function. Such a reformulation can be solved by a standard solver that uses a branch and bound algorithm. This reformulation, that we call MIQCR (Mixed Integer Quadratic Convex Reformulation), is the best one within a convex reformulation scheme, from the continuous relaxation point of view. It is based on the solution of an SDP relaxation of (QP). Computational experiences were carried out with instances of (QP) with one equality constraint. The results show that most of the considered instances, with up to 60 variables, can be solved within 1 hour of CPU time by a standard solver.
Equipe:
oc
BibTeX
| @inproceedings { | |||
| BEL10b, | |||
| title | = | "{Solving a general mixed-integer quadratic problem through convex reformulation : a computational study }", | |
| author | = | " A. Billionnet and S. Elloumi and A. Lambert ", | |
| booktitle | = | "{European Workshop on Mixed Integer Nonlinear Programming}", | |
| year | = | 2010, | |
| month | = | "April", | |
| pages | = | "197-204", | |
| address | = | " Marseille, France", | |
| } | |||
