# Penalty Weights in QUBO Formulations: Permutation Problems

arXiv: https://arxiv.org/abs/2206.11040 · HTML: https://mlsanity.com/paper/2206.11040/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 20 Jun 2022.

## Builds on (most cited first, 6 of 6)

- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Quantum Permutation Synchronization](https://mlsanity.com/paper/2101.07755/) (2021)
- [Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer](https://mlsanity.com/paper/1508.06182/) (2015)
- [Digital Annealer for quadratic unconstrained binary optimization: a comparative performance analysis](https://mlsanity.com/paper/2012.12264/) (2020)
- [A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization](https://mlsanity.com/paper/2009.12767/) (2020)
- [Kernels of Mallows Models under the Hamming Distance for solving the Quadratic Assignment Problem](https://mlsanity.com/paper/1910.08800/) (2019)

## Built on by (most cited first, 9 of 9)

- [Q-Seg: Quantum Annealing-Based Unsupervised Image Segmentation](https://mlsanity.com/paper/2311.12912/) (2023)
- [A Study of Scalarisation Techniques for Multi-Objective QUBO Solving](https://mlsanity.com/paper/2210.11321/) (2022)
- [LLM-QUBO: An End-to-End Framework for Automated QUBO Transformation from Natural Language Problem Descriptions](https://mlsanity.com/paper/2509.00099/) (2025)
- [Fast Hyperparameter Tuning for Ising Machines](https://mlsanity.com/paper/2211.15869/) (2022)
- [Local Binary and Multiclass SVMs Trained on a Quantum Annealer](https://mlsanity.com/paper/2403.08584/) (2024)
- [GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer](https://mlsanity.com/paper/2609.04593/) (2026)
- [A QUBO Framework for Team Formation](https://mlsanity.com/paper/2503.23209/) (2025)
- [Minimum Bisection Problem: Machine Learning-Based Penalty Parameter Tuning for Optimization on Quantum Annealers](https://mlsanity.com/paper/2509.19005/) (2025)
- [Quantum Approaches to Urban Logistics: From Core QAOA to Clustered Scalability](https://mlsanity.com/paper/2512.10813/) (2025)

## Abstract (arXiv)

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.