Applications and Computational Advances for Solving the QUBO Model

QUBO models have proven to be remarkable for their ability to function as an alternative modeling framework for a wide variety of combinatorial optimization problems. Many studies have underscored the usefulness of the QUBO model to serve as an effective approach for modeling and solving important combinatorial problems. The significance of this unifying nature of the QUBO model is enhanced by the fact that the model can be shown to be equivalent to the Ising model that plays a prominent role in physics and is a major focus of the quantum computing community. Consequently, the broad range of optimization problems approached as QUBO models from the traditional Operations Research community are joined by an important domain of problems with connection to the physics community. Across the board, the QUBO model is used today as an alternative modeling and solution approach for a growing number of important problems found in industry and government. We describe important new applications of this model and sketch fundamental ways to create effective QUBO formulations. We also report computational experience showing the power of recent algorithmic advances. (The introduction section draws on material from Glover et al., 4OR 17:335–371, 2019.)