Separable Relaxations for Binary Quadratic Optimization

Christoph Buchheim* and Emiliano Traversi

We present a new approach to constrained quadratic binary programming. Dual bounds are computed by choosing appropriate global underestimators of the objective function that are separable but not necessarily convex. Using the binary constraint on the variables, the minimization of this separable underestimator can be reduced to a linear minimization problem over the same set of feasible vectors. For most combinatorial optimization problems, the linear version is considerably easier than the quadratic version. We explain how to embed this approach into a branch-and-bound algorithm and present experimental results. Finally, we discuss an algorithm for mixed-integer polynomial optimization based on similar ideas, which is joint work with Claudia D'Ambrosio.

Mathematics Subject Classification: 90C10 90C27 90C20 90C22

Keywords: binary quadratic programming; branch-and-bound algorithm

Minisymposion: Nonlinear Mixed Integer Programming and Conic Relaxations