"An Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programming"
Technical report by Christoph Buchheim, Alberto Caprara, Andrea Lodi, available as BibTeX Source.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2009-592
Keywords:	closest vector problem, convex quadratic minimization
MSC codes:	90C10, 90C20, 90C25
This technical report has 17 pages, was written in July 2009, it has not been published.
Abstract:	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 considering certain 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.