[Technical report] Characterizing and benchmarking QUBO reformulations of the knapsack problem Rodolfo A. Quintero and Luis F. Zuluaga.
The motivation to work on this project came after we realized that most of the literature regarding QUBO reformulations for constrained optimization problems is centered around equality constrained problems.
Here, we focus on the “simplest” inequality constrained problem in this class: the knapsack problem (KP). Specifically, we derive different QUBO formulations for the KP, characterize the range of their associated penalty constants, as well as computationally
benchmark them through experiments using QAOA on IBMq.
Submitted
[arXiv] Lagrangian Reformulation for Nonconvex Optimization: Tailoring Problems to Specialized Solvers Rodolfo A. Quintero, Juan C. Vera, and Luis F. Zuluaga
ArXiv submission available soon. In this paper, we were able to show, using only first principles, the equivalence between a class of equality-constrained nonconvex optimization problems and their Lagrangian relaxation.
This enables the use of quantum and classical optimization solvers that take advantage of particular formulations of nonconvex problems to find approximate solutions. In addition to filling a crucial gap in the literature,
our results are readily applicable to many important situations in practice. For instance, it allows us to rewrite many integer and MINLP problems as continuous optimization programs!
Book Chapters
[Springer link] Qubo formulations of combinatorial optimization problems for quantum computing devices. In Encyclopedia of Optimization, pages 1-13. Springer, 2022. Rodolfo A. Quintero, and Luis F. Zuluaga
Journal Articles
[Springer link] Characterization of qubo reformulations for the maximum k-colorable subgraph problem. Quantum Information Processing, 21(3):1-36, 2022. Rodolfo A. Quintero, David Bernal, Tamás Terlaky, and Luis F Zuluaga
This was my first deep dive into Quantum Computing Optimization. The idea that motivated this work originated from a paper by James Abello, Sergiy Butenko, Panos Pardalos, and Mauricio Resende on finding
independent sets in a graph using a continuous reformulation of the integer version of the maximum independent set problem, by penalizing the linear constraints in the objective function with a quadratic function.
In our project, we generalize and prove similar results for the Maximum k-Colorable Subgraph (MkCS) problem, which encompasses the independent set problem. More specifically, we derive two QUBO reformulations for the MkCS problem and fully characterize the range of penalty parameters that can be used in these QUBO reformulations.
To illustrate the benefits of obtaining and characterizing these QUBO reformulations, we benchmarked different QUBO reformulations of the MkCS problem by performing numerical tests on D-Wave’s quantum annealing devices.