Penalty Weights in QUBO Formulations: Permutation Problems

Abstract

Optimisation algorithms designed to work on quantum computers or other specialised hardware have been of research interest in recent years. Commercial solvers that use quantum or quantum-inspired methods, such as Fujitsu’s Digital Annealer (DA) and D-wave’s Quantum Annealer, can solve optimisation problems faster than algorithms implemented on general purpose computers. However, they can only optimise problems that are in binary and quadratic form. Quadratic Unconstrained Binary Optimisation (QUBO) is therefore a common formulation used by these solvers. There are many combinatorial optimisation problems that are naturally represented as permutations e.g. travelling salesman problem. Encoding permutation problems using binary variables however presents some challenges. Many QUBO solvers are single flip solvers, it is therefore possible to generate solutions that cannot be decoded to a valid permutation. To create bias towards generating feasible solutions, we use penalty weights. The process of setting static penalty weights for various types of problems is not trivial. This is because values that are too small will lead to infeasible solutions being returned by the solver while values that are too large may lead to slower convergence. In this study, we explore some methods of setting penalty weights within the context of QUBO formulations. We propose new static methods of calculating penalty weights which lead to more promising results than existing methods.