An Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programming

Buchheim, Christoph and Caprara, Alberto and Lodi, Andrea (2010) An Effective Branch-and-Bound 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. 285-298.

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.


Actions:
Full text not available from this repository.
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2009-592
Depositing User: Christoph Buchheim
Date Deposited: 09 Jul 2009 00:00
Last Modified: 26 Oct 2011 11:58
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/592