Semidefinite relaxations for non-convex quadratic mixed-integer programming

• 成果类型: Article
• 署名作者: Buchheim, Christoph; Wiegele, Angelika
• 署名单位: Dortmund University of Technology; University of Klagenfurt
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0534-y
• 发表日期: 2013
• 页码: 435-452
• 关键词: Optimization; cut

摘要

We present semidefinite relaxations for unconstrained non-convex quadratic mixed-integer optimization problems. These relaxations yield tight bounds and are computationally easy to solve for medium-sized instances, even if some of the variables are integer and unbounded. In this case, the problem contains an infinite number of linear constraints; these constraints are separated dynamically. We use this approach as a bounding routine in an SDP-based branch-and-bound framework. In case of a convex objective function, the new SDP bound improves the bound given by the continuous relaxation of the problem. Numerical experiments show that our algorithm performs well on various types of non-convex instances.