Enhancing a QUBO solver via data driven multi-start and its application to vehicle routing problem

• Main Authors: SUEN, Whei Yeap, PARIZY, Matthieu, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2022
• Subjects: QUBO; optimization; vehicle routing; quantum-inspired; Computer Sciences; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/7624; https://ink.library.smu.edu.sg/context/sis_research/article/8627/viewcontent/3520304.3533988.pdf
• Institution: Singapore Management University

Quadratic unconstrained binary optimization (QUBO) models have garnered growing interests as a strong alternative modelling framework for solving combinatorial optimization problems. A wide variety of optimization problems that are usually studied using conventional Operations Research approaches can be formulated as QUBO problems. However, QUBO solvers do not guarantee optimality when solving optimization problems. Instead, obtaining high quality solutions using QUBO solvers entails tuning of multiple parameters. Here in our work, we conjecture that the initial states adjustment method used in QUBO solvers can be improved, where careful tuning will yield overall better results. We propose a data-driven multi-start algorithm that complements the QUBO solver (namely Fujitsu Digital Annealer) in solving constrained optimization problems. We implemented our algorithm on a variety of capacitated vehicle routing problem instances, and empirical results show that different initial state adjustment methods do make a difference in the quality of solutions obtained by the QUBO solver.