Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

7-2022

Abstract

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.

Discipline

Computer Sciences | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

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

First Page

2223

Last Page

2231

Identifier

10.1145/3520304.3533982

Publisher

ACM

City or Country

Boston, US

Additional URL

http://doi.org/10.1145/3520304.3533982

Download

Share

COinS