Christoph Buchheim, 17 February 2010, 11:00, DIS
Wednesday, 17 February 2010, h. 11:00. Room A5 - DIS, via Ariosto 25, Roma
SPEAKER: Christoph Buchheim TU Dortmund [email protected]
A fast branch-and-bound algorithm for convex mixed-integer optimization (joint project with Alberto Caprara and Andrea Lodi)
ABSTRACT: We present a branch-and-bound algorithm for minimizing a convex (quadratic) objective function over integer and continuous variables. 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.