Evaluation of Sensitivity Analysis of Penalty Weights in QUBO
Jiajie Liu, Alberto Moraglio · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2025
This paper evaluates a framework which automatically sets penalty weights in QUBO (Quadratic Unconstrained Binary Optimization) through constraint sensitivity analysis. Combinatorial optimization problems need to be converted to QUBO form before being solved on quantum computers. Traditional QUBO models often use uniform penalty weights across constraints. The challenge of setting multiple penalty weights is that the weight combinations grow exponentially with the number of constraints. The proposed method first applies an exact and sequential method to obtain an initial weight, then adjusts individual weights based on their sensitivity, measured by the effect on the objective function. The constraint sensitivity analysis method was introduced very recently, and only preliminarily tested [10]. In this paper, we extend it to work on multiple (more than 2) constraints and test it on a wider problem benchmark. Experimental evaluations on the Quadratic Assignment Problem, Traveling Salesman Problem, and p-Median Facility Location Problem instances are presented. Results demonstrate that compared with Optuna and existing exact and sequential frameworks, the constraint sensitivity analysis method achieves superior solution quality and lower deviation from the optimal while maintaining acceptable feasibility rates.