(165f) Solving Mixed-Integer Linear and Quadratic Programs Using Quantum Computing

Quantum optimization techniques utilize quantum mechanical phenomena [1], such as superposition, entanglement, and tunneling that allow them to rapidly explore vast solution space [2] as well as escape local optima during the quantum annealing process [3], thereby providing good solutions to combinatorially complex problems within computationally tractable time. Due to the impressive technological advancements [4] and industrial efforts to build commercial cloud-based Quantum computing (QC) systems [5], the current generation of quantum computers can efficiently solve discrete optimization problems, for example, graph coloring [6], traffic flow optimization [7], scheduling problems [8], and vehicle routing problem [9].

However, not all optimization problems can directly be solved using QC in their original form. The current generation of quantum hardware requires that the problem of interest be transformed into equivalent forms that are suitable for Quantum annealing, such as the Ising model or quadratic unconstrained binary optimization (QUBO) model [10]. Also, due to the physical nature of QC, as well as the current limitation in quantum hardware, it is not possible to embed constraints, nor efficiently optimize over the continuous domain. This is problematic since most process systems engineering problems of real importance, such as sustainable process synthesis and intensification often involve solving mixed-integer quadratic or mixed-integer nonlinear programs (MINLP) [11] containing both continuous and discrete decisions with many constraints. Current approaches to solving such mixed-integer problems involve hybrid classical-quantum optimization techniques [12]. Such techniques involve decomposing the original problem into a master subproblem involving integer decisions and a nonlinear subproblem involving only continuous decisions. While these hybrid approaches can solve mixed-integer problems, they do not utilize the full potential of QC. To address this issue, we have devised a framework for directly solving mixed-integer linear and quadratic programs using QC platforms. This involves representing continuous variables as a set of binary variables and using this reformulation to transform the problem into a single QUBO-type problem, which can be directly solved using quantum annealing. By eliminating the need for hybrid schemes that require solving continuous subproblems using classical solvers, this approach fully utilizes the potential of QC. We have tested this approach on a variety of problems, including material design and pooling problems, with good agreement with solutions obtained using deterministic solvers. We have also extended this approach to solve mixed-integer quadratically constrained quadratic programs (MIQCQP) using QC alone, with several encoding methods explored and compared for efficacy in improving solution quality and computation time.

Keywords: Quantum optimization, Quantum computing, Quantum annealing, QUBO, Mixed-integer, MIQP, MIQCQP, Material design, Pooling problems.

References:

[1] Albash, T., and Lidar, D. A. Adiabatic quantum computation. Reviews of Modern Physics, 90, 015002 (2018).

[2] Baldassi, C, and Zecchina, R. Efficiency of quantum vs. classical annealing in nonconvex learning problems. Proceedings of the National Academy of Sciences, 115, 1457–1462 (2018).

[3] Lanting, T., Przybysz, A. J., Smirnov, A. Y., Spedalieri, F. M., Amin, M. H., Berkley, A. J., Harris, R., Altomare, F., Boixo, S., Bunyk, P., et al. Entanglement in a quantum annealing processor. Physical Review X, 4, 021041 (2014).

[4] Friis, N., Marty, O., Maier, C., Hempel, C., Holz¨apfel, M., Jurcevic, P., Plenio, M. B., Huber, M., Roos, C., Blatt, R., et al. Observation of entangled states of a fully controlled 20-qubit system. Physical Review X, 8, 021012 (2018).

[5] Mooney, G. J. White, G. A. Hill, C. D. and Hollenberg, L. C. Whole-Device Entanglement in a 65-Qubit Superconducting Quantum Computer. Advanced Quantum Technologies, 4, 2100061 (2021).

[6] Titiloye, O., and Crispin, A. Quantum annealing of the graph coloring problem. Discrete Optimization, 8, 376–384 (2011).

[7] Neukart, F., Compostella, G., Seidel, C., Von Dollen, D., Yarkoni, S., and Parney, B. Traffic flow optimization using a quantum annealer. Frontiers in ICT, 4, 29 (2017).

[8] Rieffel, E. G., Venturelli, D., O’Gorman, B., Do, M. B., Prystay, E. M., and Smelyanskiy, V. N. A case study in programming a quantum annealer for hard operational planning problems. Quantum Information Processing, 14, 1–36 (2015).

[9] Feld, S., Roch, C., Gabor, T., Seidel, C., Neukart, F., Galter, I., Mauerer, W., Linnhoff-Popien, C. A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. Frontiers in ICT, 6, 13 (2019).

[10] Lucas, A. Ising formulations of many NP problems. Frontiers in physics, 5 (2014).

[11] Demirel, S. E., Li, J., Hasan, M. M. F. (2017). Systematic process intensification using building blocks. Computers & Chemical Engineering, 105, 2–38.

[12] Zhao, Z., Fan, L., Han, Z. (2022). Hybrid Quantum Benders’ Decomposition for Mixed-integer Linear Programming. IEEE Wireless Communications and Networking Conference (WCNC), 2536-2540.