Stats, Optimization, and Machine Learning Seminar - Fred Glover and Gary Kochenberger

Modeling and Solving Combinatorial Optimization Problems Using the QUBO Model

A surprising development of the last few years has been the emergence of a model, called QUBO (for Quadratic Unconstrained Binary Optimization) that unifies a wide variety of optimization problems, especially in combinatorial optimization. The importance of the QUBO model is further underscored by its connection with quantum computing, where it is the foundation of "adiabatic" quantum computing, an area being explored by Google and D-Wave Systems and embodied in D-Wave quantum computers at Los Alamos National Laboratory and Oak Ridge National Laboratory. Computational experience coming from both the classical and the quantum computing communities highlights not only the potential of the QUBO model but also its effectiveness as an alternative to traditional modeling and solution methodologies. We survey, in a tutorial manner, a variety of applications of the QUBO model and highlight state of the art solution methods. In our discussion of applications, we make a connection with QUBO and machine learning.

Fred Glover is Chief Technology Officer of OptTek Systems, Inc., in charge of algorithmic design and strategic planning initiatives, and Distinguished University Professor, Emeritus, in the University of Colorado School of Engineering and Leeds School of Business. He has authored or co-authored more than 500 published articles and eight books in the fields of mathematical optimization, computer science and artificial intelligence, and is the originator of the “Tabu Search Algorithm,” an adaptive memory programming algorithm for mathematical optimization in complex search spaces, for which Google returns more than 900,000 results. He is an elected member of the U. S. National Academy of Engineering and is the recipient of the von Neumann Theory Prize, the highest honor of the INFORMS Society, as well as numerous other awards and honorary fellowships. 

Dr. Gary A. Kochenberger has a BS in electrical engineering and a PhD in Management Science from the University of Colorado. He is currently a professor of Business Analytics at the University of Colorado at Denver. His research interests include combinatorial optimization, resource allocation, pattern classification, data mining, and related areas.  He has published 4 books and more than 100 articles on operations research and optimization.