Extending the QCR method to general mixed-integer programs
成果类型：
Article
署名作者：
Billionnet, Alain; Elloumi, Sourour; Lambert, Amelie
署名单位：
heSam Universite; Conservatoire National Arts & Metiers (CNAM); Institut Polytechnique de Paris; ENSTA Paris; Ecole Nationale Superieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-010-0381-7
发表日期：
2012
页码：
381-401
关键词：
摘要：
Let (MQP) be a general mixed integer quadratic program that consists of minimizing a quadratic function subject to linear constraints. In this paper, we present a convex reformulation of (MQP), i.e. we reformulate (MQP) 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. We prove that our reformulation is the best one within a convex reformulation scheme, from the continuous relaxation point of view. This reformulation, that we call MIQCR (Mixed Integer Quadratic Convex Reformulation), is based on the solution of an SDP relaxation of (MQP). Computational experiences are carried out with instances of (MQP) including one equality constraint or one inequality constraint. The results show that most of the considered instances with up to 40 variables can be solved in 1 h of CPU time by a standard solver.