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.
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.
This paper proposes a novel framework for automatically setting penalty weights in the Quadratic Unconstrained Binary Optimization (QUBO) to handle problems with multiple constraints. Quantum computing and quantum-inspired methods have gained prominence, with QUBO models widely used for their unified representation of optimization problems. However, QUBO performance is highly sensitive to penalty weight settings, especially in multiple constraints scenarios, where setting different penalty weights to different constraints may further affect performance. Existing methods for setting common penalty weights for all constraints in QUBO can be generally categorized into manual methods based on expert experience, exact methods based on the objective function values, and sequential methods based on searching within an upper bound. This study introduces a novel framework for multiple constraints optimization that utilizes exact and sequential binary search methods to determine common penalty weight while integrating constraint sensitivity analysis to adjust each penalty weight dynamically. This approach enhances the efficiency and quality of QUBO solutions. Experimental results on the Travelling Salesman Problem show that the proposed framework achieves superior solution quality and feasibility on both the D-Wave quantum annealer and classical simulated annealing solvers, outperforming traditional methods and demonstrating strong adaptability.
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.
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.
Quantum computing has emerged as a promising alternative for solving combinatorial optimization problems. The standard approach for encoding optimization problems on quantum processing units (QPUs) involves transforming them into their Quadratic Unconstrained Binary Optimization (QUBO) representation. However, encoding constraints of optimization problems, particularly inequality constraints, into QUBO requires additional variables, which results in more qubits. Considering the limited availability of qubits in NISQ machines, existing encoding methods fail to scale due to their reliance on large numbers of qubits. We propose a generalized exponential penalty framework for QUBO inequality constraints inspired by a class of exponential functions, which we call exponential penalization. This paper presents an encoding strategy for inequality constraints in combinatorial optimization problems, inspired by a class of exponential functions, which we call exponential penalization. The initial idea of using exponential penalties for QUBO formulation was introduced by Montanez-Barrera et al. by applying a specific exponential function to reduce qubit requirements. In this work, we extend that approach by conducting a comprehensive study on a broader class of exponential functions, analyzing their theoretical properties and empirical performance. Our experimental results demonstrate that an exponential penalization achieves 57%, 83% qubit number reduction for Bin Packing Problem (BPP) and Traveling Salesman Problem (TSP), respectively. And we demonstrate comparable solution quality to classical with a probability of 6% and 21% accuracy for BPP with 8 and TSP with 12 qubits, respectively.
Quantum annealing offers a powerful means to solve combinatorial optimization problems formulated as Quadratic Unconstrained Binary Optimization (QUBO). In constrained problems, appropriate penalty weights are critical: too small yields infeasibility, too large harms solution quality. This paper proposes a rigorous method to determine lower bounds for penalty weights, ensuring constraint satisfaction without degrading optimization. Applied to the Dynamic Spectrum Allocation (DSA) problem with priority-aware extensions, the method leverages iterative quantum annealing to reduce tuning overhead. Experiments show improved efficiency and feasibility over conventional approaches.
Quadratic Unconstrained Binary Optimization (QUBO) is a central formulation for combinatorial optimization and has gained increasing attention due to its compatibility with quantum, hybrid quantum-classical, and quantum-inspired solvers. However, translating natural-language problem descriptions into correct QUBO formulations remains difficult, requiring the identification of binary variables, constraints, objective functions, penalty terms, and suitable penalty weights. This process is time-consuming and often demands substantial domain expertise. To address this challenge, we propose an end-to-end multi-agent framework that automatically generates QUBO formulations from natural-language problem descriptions, supported by structured or unstructured test cases. To evaluate its performance, We also introduce QUBOBench, a benchmark containing 100 combinatorial optimization problems across 12 application domains, curated from peer-reviewed literature, competitions, and canonical NP-hard problems. Experimental results show that our framework achieves 68% accuracy on QUBOBench, outperforming a direct single-call baseline by 22%. Further analysis identifies iterative self-repair as the most important component contributing to improved performance. The data and code are open-sourced at https://quitttcat.github.io/QuantumQUBOAgent.