Penalty and partitioning techniques to improve performance of QUBO solvers

Mayowa Ayodele, Richard Allmendinger, Manuel López‐Ibáñez +1 more

Siong Thye Goh, Jianyuan Bo, Sabrish Gopalakrishnan +1 more

Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.

Fumiyo Takano, Motoi Suzuki, Y. Kobayashi +1 more

Tian Huang, Siong Thye Goh, Sabrish Gopalakrishnan +3 more

A popular method for solving a constrained combinatorial optimisation problem is to first convert it into a quadratic unconstrained binary optimisation (QUBO) problem, and solve it using a standard QUBO solver. However, this relaxation introduces hyper-parameters that balance the objective and penalty terms for the constraints, and their chosen values significantly impact performance. Hence, hyper-parameters tuning is important. Existing generic hyper-parameter tuning methods require multiple expensive calls to a QUBO solver, making them inefficient for performance critical applications when repeated solutions of similar combinatorial optimisation problems are required. In this paper, we propose the QROSS method, in which we build surrogate models of QUBO solvers via learning from solver data on a collection of instances of a problem. In this way, we are able capture the common structure of the instances and their interactions with the solver, and produce promising hyper-parameters with fewer calls to the QUBO solver. We take the Traveling Salesman Problem (TSP) as a case study, where we demonstrate QROSS finds better solutions with fewer calls to QUBO solver, compared with conventional hyper-parameter tuning techniques. Moreover, with simple adaptation methods, QROSS is shown to generalise well to out-of-distribution datasets and different types of QUBO solvers.

Renáta Rusnáková, Martin Chovanec, Maroš Harahus +1 more

This study focuses on reformulating the shortest path problem in undirected weighted graphs into a QUBO problem, leveraging the D-Wave quantum annealing hybrid solver for execution. While A * search with heuristics, a widely used algorithm for solving shortest path problem, serves as a baseline for comparison, our primary contribution lies in analyzing the accuracy and benefits of the proposed QUBO formulation. Our analysis reveals that the proposed QUBO formulation together with selected quantum annealing hybrid solver is loosing its efficiency with increasing number of nodes. This is caused by the size of the problem and related penalty calculation but also by the architecture of the D-Wave QPU and design of the hybrid solver. We are proposing techniques to improve the results, such as graph pruning during preprocessing or penalty parameter tuning to achieve better, more accurate, results. This study provides valuable insights into the limitations of current approaches and explores the future applications of quantum computing in solving real-world challenges.

Mayowa Ayodele