Prof. Hans Mittelmann of Arizona State University has added Quadratic Unconstrained Binary Optimization (QUBO) problems to his widely recognized benchmarks. With the growing interest in quantum computing, QUBO has been put in the spotlight as a potential solution to complex optimization challenges; since quantum annealers can find approximate solutions to QUBOs
The QuBowl QUBO and MaxCut solver, developed by the SynLab of the Research Campus MODAL in collaboration with the Department of Applied Algorithmic Intelligence Methods at ZIB and i2damo GmbH, provides a highly effective solution to these problems. The QuBowl solver has outperformed its competitors in the Nonconvex QUBO-QPLIB Benchmark, solving 15 out of 23 QUBO problems to global optimality.
“We are thrilled to see that our solver is among the best available for computing proven optimal solutions to QUBO problems,” says Daniel Rehfeldt. “In contrast to heuristic solvers, Qubowl provides a guaranteed quality solution, and it is also the overall fastest solver in the benchmark.”
QuBowl provides advanced algorithmic components to solve unconstrained binary problems, such as reduction techniques and cutting-plane separation algorithms. These components are combined in an exact branch-and-cut solver with a parallel implementation, making QuBowl a highly efficient solution to QUBO problems. The results of this ongoing collaboration have been accepted for publication in Mathematical Programming Computation.
Links:
https://arxiv.org/abs/2202.02305
http://plato.asu.edu/ftp/qubo.html
http://qplib.zib.de/