A recommendation system approach to tune a QUBO solver

• Main Authors: GOH, Siong Thye, BO, Jianyuan, PARIZY, Matthieu, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2022
• Subjects: Artificial Intelligence and Robotics; Systems Architecture
• Online Access: https://ink.library.smu.edu.sg/sis_research/7756; https://ink.library.smu.edu.sg/context/sis_research/article/8759/viewcontent/IJCAI_NASO_2022_A_Recommendation_System_Approach_to_Tune_a_QUBO_Solver.pdf
• Institution: Singapore Management University

There are two major challenges to solving constrained optimization problems using a QuadraticUnconstrained Binary Optimization or QUBO solver (QS). First, we need to tune both the underlyingproblem parameters and the algorithm parameters. Second, the solution returned from a QSmight not be feasible. While it is common to use automated tuners such as SMAC and Hyperopt totune the algorithm parameters, the initial search ranges input for the auto tuner affect the performanceof the QS. In this paper, we propose a framework that resembles the Algorithm Selection(AS) framework to tune algorithm parameters for an annealing-based QS. To cope with constraints,we focus on permutation-based combinatorial optimization problems, since computing the projectionto the feasible space for this class of problems can be done efficiently; and for simplicity, the numberof problem parameters can be reduced to one and we fix it. Methodologically, we train a recommendationsystem to to learn good annealing problem parameter ranges. During testing, we search forgood hyperparameter values using a recommendation system approach. To illustrate our approach experimentally, we use the Fujitsu Digital Annealer as our QUBO solver and Optuna as the auto tuner tosolve the Traveling Salesman Problem.