An Effective BranchandBound Algorithm for Convex Quadratic Integer Programming
Buchheim, Christoph and Caprara, Alberto and Lodi, Andrea
(2010)
An Effective BranchandBound Algorithm for Convex Quadratic Integer Programming.
Published In:
Integer programming and combinatorial optimization : 14th international conference, IPCO 2010, Lausanne, Switzerland, June 9  11, 2010 ; proceedings, Lecture notes in computer science. 6080 Springer 2010, pp. 285298.
Abstract
We present a branchandbound 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 latticefree 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.
Item Type:  Proceedings article 

Citations:  4 (Google Scholar)  0 (Web of Science) 
Uncontrolled Keywords:  convex quadratic minimization closest vector problem 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Related URLs: 
ZAIK Number:  zaik2009592 

Depositing User:  Christoph Buchheim 
Date Deposited:  09 Jul 2009 00:00 
Last Modified:  26 Oct 2011 11:58 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/592 