A Tutorial on Formulating QUBO Models

The field of Combinatorial Optimization (CO) is one of the most important areas in the general field of optimization, with important applications found in every industry, including both the private and public sectors. It is also one of the most active research areas pursued by the research communities of Operations Research, Computer Science, and Analytics as they work to design and test new methods for solving real world CO problems. Generally these problems are concerned with making wise choices in settings where there is a large number of yes/no decisions to be made and where each set of decisions yields a corresponding objective function value---like a cost or profit value. Finding good solutions in these settings is extremely difficult. The traditional approach is for the analyst to develop a solution algorithm that is tailored to the particular mathematical structure of the problem at hand. While this approach has produced good results in certain problem settings, it has the disadvantage that the diversity of applications arising in practice requires the creation of a diversity of solution techniques, each with limited application outside their original intended use. In recent years, we have discovered that a mathematical formulation known as QUBO, an acronym for a Quadratic Unconstrained Binary Optimization problem, can embrace a large variety of important CO problems found in industry and government. Through special reformulation techniques that are easy to apply, the power of QUBO solvers can be used to efficiently solve many important problems once they are put into the QUBO framework. This two-step process of first re-casting an original model into the form of a QUBO model and then solving it with appropriate software enables the QUBO model to become a unifying framework for combinatorial optimization. The alternative path that results for effectively modeling and solving many important problems is a new development in the field of combinatorial optimization. The materials provided in subsequent sections illustrate the process of reformulating important optimization problems as QUBO models through a series of explicit examples. Collectively these examples highlight the application breadth of the QUBO model. We do not focus here on modeling a given problem in the form classically adopted in the optimization community. Rather, our examples disclose the methods that can be used to recast a given problem, perhaps existing in a classical mathematical form, into an equivalent QUBO model.

Citation

University of Colorado, November 2018.

Article

Download

View A Tutorial on Formulating QUBO Models