An effective branch-and-bound algorithm for convex quadratic integer programming
成果类型：
Article
署名作者：
Buchheim, Christoph; Caprara, Alberto; Lodi, Andrea
署名单位：
University of Bologna; Dortmund University of Technology
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-011-0475-x
发表日期：
2012
页码：
369-395
关键词：
摘要：
We present a branch-and-bound algorithm for minimizing a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing of a subset of the variables, a lower bound is given by the continuous minimum of the restricted objective function. We improve this bound by exploiting the integrality of the variables using suitably-defined lattice-free ellipsoids. Experiments show that our approach is very fast on both unconstrained problems and problems with box constraints. The main reason is that all expensive calculations can be done in a preprocessing phase, while a single node in the enumeration tree can be processed in linear time in the problem dimension.