Constraint Programming to Discover One-Flip Local Optima of Quadratic Unconstrained Binary Optimization Problems
This provides a method to improve solution quality for combinatorial optimization in quantum and classical computing, but it is incremental as it builds on existing constraint programming techniques.
The paper tackled the problem of generating diverse one-flip local optima for Quadratic Unconstrained Binary Optimization (QUBO) problems, using constraint programming to produce solution sets that aid optimization processes like annealing.
The broad applicability of Quadratic Unconstrained Binary Optimization (QUBO) constitutes a general-purpose modeling framework for combinatorial optimization problems and are a required format for gate array and quantum annealing computers. QUBO annealers as well as other solution approaches benefit from starting with a diverse set of solutions with local optimality an additional benefit. This paper presents a new method for generating a set of one-flip local optima leveraging constraint programming. Further, as demonstrated in experimental testing, analysis of the solution set allows the generation of soft constraints to help guide the optimization process.