Faster exact solution of sparse MaxCut and QUBO problems

Understand

The maximum-cut problem is one of the fundamental problems in combinatorial optimization.

• With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years.
• This article aims to advance the state of the art in the exact solution of both problems -- by using mathematical programming techniques on digital computers.
• The main focus lies on sparse problem instances, although also dense ones can be solved.