A Mixing Method based Branch-and-Bound Solver for QUBO Problems

Quadratic unconstrained binary optimization (QUBO) has an exceptional role in combinatorial optimization. Many optimization problems like the well-known maximum-cut problem, the graph bisection problem, or the maximum independent set problem can be formulated as a QUBO instance. Moreover, any linearly constrained binary quadratic problem can be reduced to solving a QUBO problem. It is also well-known that linear programming-based approaches perform poorly on dense QUBO instances. In this talk, we present a branch-and-bound solver for QUBO problems based on semidefinite programming. In contrast to other approaches in the literature, we use weaker but much faster solvable semidefinite relaxations. This is achieved by using the so-called mixing method, a low-rank coordinate descent method. We provide numerical results showing that our approach outperforms the other existing semidefinite approaches in the literature.