Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)

A Framework for Automatically Setting Multiple Penalty Weights in Quadratic Unconstrained Binary Optimization

Jiajie Liu, Alberto Moraglio

Published Jul 14, 2025• 3 citations
Publisher

Abstract

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.

DOI
10.1145/3712255.3726759

Related papers

Evaluation of Sensitivity Analysis of Penalty Weights in QUBO

Jiajie Liu, Alberto Moraglio

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.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2025•3 citations

Exact and sequential penalty weights in quadratic unconstrained binary optimisation with a digital annealer

MD Garcia (21941009), M Ayodele (21491936), A Moraglio (21844982)

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.

•Aug 1, 2025•0 citations

Exact and sequential penalty weights in quadratic unconstrained binary optimisation with a digital annealer

Marcos Diez García, Mayowa Ayodele, Alberto Moraglio

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.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•24 citations

Optimization of Penalty Weights in Quantum Annealing for Dynamic Spectrum Allocation

Yuhi Kurebayashi, Yui Yamashita, Yoshito Tobe

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.

Asia-Pacific Conference on Communications (APCC)•Nov 26, 2025•0 citations

Automaton-based methodology for implementing optimization constraints for quantum annealing

Hristo N. Djidjev

Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.

ACM International Conference on Computing Frontiers (CF)•May 11, 2020•1 citation

QuantumQUBO Agent: Automating Quadratic Unconstrained Binary Optimization (QUBO) Formulation Generation from Natural Language

Niloy Kumar Mondal, Md Rizwan Parvez

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.

arXiv:2609.10629•Sep 9, 2026•0 citations
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.
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.
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 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.
Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.
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.