Scalable Determination of Penalization Weights for Constrained Optimizations on Approximate Solvers

• URL: http://arxiv.org/abs/2604.02416v1
• Date: Thu, 02 Apr 2026 18:00:02 GMT
• Title: Scalable Determination of Penalization Weights for Constrained Optimizations on Approximate Solvers
• Abstract summary: A common approach to constrained optimization problems is to enforce the constraints in the QUBO formulation by adding penalization terms.<n>We develop a pre-computation strategy for determining penalization weights with provable guarantees for Gibbs solvers and complexity for broad problem classes.<n>Experiments across diverse problems and solver architectures, including large-scale instances on Fujitsu's Digital Annealer, show robust performance and order-of-magnitude speed over existings.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quadratic unconstrained binary optimization (QUBO) provides problem formulations for various computational problems that can be solved with dedicated QUBO solvers, which can be based on classical or quantum computation. A common approach to constrained combinatorial optimization problems is to enforce the constraints in the QUBO formulation by adding penalization terms. Penalization introduces an additional hyperparameter that significantly affects the solver's efficacy: the relative weight between the objective terms and the penalization terms. We develop a pre-computation strategy for determining penalization weights with provable guarantees for Gibbs solvers and polynomial complexity for broad problem classes. Experiments across diverse problems and solver architectures, including large-scale instances on Fujitsu's Digital Annealer, show robust performance and order-of-magnitude speedups over existing heuristics.

Related papers

• CVaR-Assisted Custom Penalty Function for Constrained Optimization [3.652509571098291]
  Constrained optimization problems are frequently reformulated as quadratic unconstrained binary optimization (QUBO) models.<n>Standard QUBO formulations enforce inequality constraints through slack variables and quadratic penalties.<n>We propose a slack-free penalty formulation for constrained binary optimization that eliminates auxiliary slack variables.
  arXiv  Detail & Related papers  (2026-04-22T01:08:38Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems [4.266376725904727]
  We propose a hybrid classical--quantum framework based on graph shrinking to reduce the number of variables and constraints in QUBO formulations of optimization problems.<n>Our approach improves solution feasibility, reduces repair complexity, and enhances quantum optimization quality on hardware-limited instances.
  arXiv  Detail & Related papers  (2025-06-17T07:11:48Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  This paper proposes a novel combination of constraint encoding methods for the Quantum Approximate Optimization Ansatz.<n>One-hot constraints are enforced through $XY$-mixers that restrict the search space to the feasible sub-space naturally.<n>Since $XY$-mixers restrict the search space, specific state vector entries are always zero and can be omitted from the simulation, saving valuable memory and computing resources.
  arXiv  Detail & Related papers  (2025-06-03T17:46:53Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers [4.266376725904727]
  Variational Quantum Algorithms (VQAs) typically require constrained problems to be reformulated as unconstrained ones using penalty methods.<n>A common approach introduces slack variables and quadratic penalties in the QUBO formulation to handle inequality constraints.<n>We explore a slack-free formulation that directly encodes inequality constraints using custom penalty functions.<n>These step-like penalties suppress infeasible solutions without introducing additional qubits or requiring finely tuned weights.
  arXiv  Detail & Related papers  (2025-04-17T03:20:02Z)
• Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
  This paper presents a hybrid framework that combines the use of standard Ising Hamiltonians to solve a subset of the constraints. The resolution of these non-Ising constraints is achieved through either penalty dephasing or the quantum Zeno effect.
  arXiv  Detail & Related papers  (2023-05-14T03:49:10Z)
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management [45.82374977939355]
  We introduce a new method for solving optimization problems with challenging constraints using variational quantum algorithms. We test our proposal on a real-world problem with great relevance in finance: the Cash Management problem. Our empirical results show a significant improvement in terms of the cost of the achieved solutions, but especially in the avoidance of local minima.
  arXiv  Detail & Related papers  (2023-02-08T17:09:20Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.