Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

7-2022

Abstract

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.

Keywords

QUBO, optimization, vehicle routing, quantum-inspired

Discipline

Computer Sciences | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference Companion

First Page

2251

Last Page

2257

Identifier

10.1145/3520304.3533988

Publisher

ACM

City or Country

Boston, US

Additional URL

http://doi.org/10.1145/3520304.3533988

Download

Share

COinS