Exact and sequential penalty weights in quadratic unconstrained binary optimisation with a digital annealer
Garcia, MD; Ayodele, M; Moraglio, A
Date: 19 July 2022
Conference paper
Publisher
Association for Computing Machinery (ACM)
Publisher DOI
Abstract
Quadratic unconstrained binary optimisation (QUBO) problems
is a general class of combinatorial optimisation problems, which
regained popularity after recent advances in quantum computing.
Quantum-inspired technologies like Fujitsu’s Digital Annealer (DA),
based on simulated annealing, can solve QUBO problems much
faster than ...
Quadratic unconstrained binary optimisation (QUBO) problems
is a general class of combinatorial optimisation problems, which
regained popularity after recent advances in quantum computing.
Quantum-inspired technologies like Fujitsu’s Digital Annealer (DA),
based on simulated annealing, can solve QUBO problems much
faster than traditional computers. Penalty methods can convert
constrained optimisation problems into QUBO problems. However, existing exact methods of determining penalty weights are
limited to specific QUBO problems and require manual analysis
by experts in QUBO. Empirical methods are general but become
computationally prohibitive for large problem sizes and do not
guarantee that penalty weights preserve the feasibility of global
optima. We present a simple, efficient, general method applicable
to any QUBO to determine exact penalty weights. Such weights are
simple upper-bounds of the smallest penalty weight guaranteeing
that unconstrained global optima are the same as the feasible global
optima. These bounds can be iteratively improved by sequential
penalty methods which we also present. Experimental results with
the DA on minimum cut, travelling salesman and multi-dimensional
knapsack problems show the viability of the novel methodology
hybridising exact and sequential methods. This work contributes
towards general, automatic and scalable penalty methods in QUBO.
Computer Science
Faculty of Environment, Science and Economy
Item views 0
Full item downloads 0