QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver Surrogates
arXiv:2103.10695
Abstract
An increasingly 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, tuning these parameters is an important problem. Existing generic hyper-parameter tuning methods require multiple expensive calls to a QUBO solver, making them impractical 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 good choices of penalty parameters with fewer number of calls to the QUBO solver. We take the Traveling Salesman Problem (TSP) as a case study, where we demonstrate that our method can find 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.
arXiv comment17 pages
References in corpus (10)
- Practical Bayesian Optimization of Machine Learning Algorithms
- MCMC using Hamiltonian dynamics
- Ising formulations of many NP problems
- Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
- Learning Combinatorial Optimization Algorithms over Graphs
- SATzilla: Portfolio-based Algorithm Selection for SAT
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
- A Tutorial on Formulating and Using QUBO Models
- Learning Improvement Heuristics for Solving Routing Problems