Christoph Buchheim

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

  • Christoph Buchheim
  • Alberto Caprara
  • Andrea Lodi
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Quadratic Programming Tags ,

    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 … Read more

    Exact Algorithms for the Quadratic Linear Ordering Problem

  • Christoph Buchheim
  • Angelika Wiegele
  • Lanbo Zheng
    • Categories Combinatorial Optimization Tags , ,

    The quadratic linear ordering problem naturally generalizes various optimization problems, such as bipartite crossing minimization or the betweenness problem, which includes linear arrangement. These problems have important applications in, e.g., automatic graph drawing and computational biology. We present a new polyhedral approach to the quadratic linear ordering problem that is based on a linearization of … Read more