Optimisation algorithms designed to work on quantum computers or other
specialised hardware have been of research interest in recent years. Many of
these solver 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.

本文研究了使用量子计算机或其他专用硬件的优化算法，介绍了 QUBO 形式的优化问题，并探索了在 QUBO 公式下设置罚项权重的新静态方法，以解决旅行商问题等排列问题的优化难题。