Constrained Binary Quadratic Optimization - Separation and Exact Solution

Lena Hupp, Laura Klein, Frauke Liers^* and Bernhard Stöcker

Effective algorithms exist for the solution of many combinatorial optimization problems, such as optimum matchings, orderings, etc. In several practical applications, however, the task is to optimize a quadratic function instead of a linear one. \newline In order to apply exact branch-and-cut methods, the objective function has to be linearized. However, the standard linearization usually leads to very weak relaxations and long running times. In this talk, we will present polyhedral insights for some of these quadratic combinatorial optimization problems together with separation routines and implementations showing the effectiveness of the methods.

Mathematics Subject Classification: 90C57 90C27

Keywords: binary quadratic optimization; branch-and-cut

Minisymposion: Nonlinear Mixed Integer Programming and Conic Relaxations