An Exact Solver for QUBO Problems using the Mixing Method
Abstract
Efficient solution approaches for quadratic unconstrained binary optimization (QUBO) problems are of great interest for several reasons. Firstly, the well-known maximum-cut problem admits a natural formulation as a QUBO problem. Secondly, other optimization problems like the graph bisection problem, the maximum independent set problem, linearly constrained binary quadratic problems, and many more can be reformulated as an instance of QUBO. Since linear programming based approaches perform poorly on dense problem instances, all state-of-the-art approaches involve semidefinite relaxations in this case. In this talk, we present an exact solver for QUBO problems based on semidefinite programming. It uses the so-called mixing method, a low-rank coordinate descent method, as its main tool to tackle the occurring semidefinite programs. We discuss some new ideas implemented in the solver and provide numerical results showing that it outperforms the other existing semidefinite approaches for medium-sized instances. Moreover, it was a paradigm in recent years to tighten semidefinite relaxations by considering more and more valid inequalities. In contrast to this, we demonstrate that weaker relaxations can still be competitive when used in a branch-and-bound approach.