Many combinatorial optimization problems on graphs can be reformulated as a quadratic unconstrained binary optimization problem or are equivalent to an instance of the well-known Max-Cut problem. This is also true for the class of linearly constrained binary quadratic problems. In this talk, we present a branch-and-cut solver for the Max-Cut problem and address some algorithmic advances and ideas. Our main tool for solving the occurring semidefinite programs is one of the recently proposed low-rank methods using the Burer-Monteiro factorization. We test our approach on many instances from the literature and compare it to other approaches.

https://www.math.aau.at/talks/147/pdf