Quantum Speedups for Group Relaxations of Integer Linear Programs

• URL: http://arxiv.org/abs/2602.13494v1
• Date: Fri, 13 Feb 2026 21:58:59 GMT
• Title: Quantum Speedups for Group Relaxations of Integer Linear Programs
• Abstract summary: Super-quadratic quantum speedups for ILPs have been difficult to obtain because classical algorithms for many-constraint ILPs are global and exhaustive.<n>We present a competitive feasibility-preserving classical local-search algorithm for the group relaxation, and a corresponding quantum algorithm that, under reasonable technical conditions, achieves a super-quadratic speedup.
• Score: 3.4310967861393418
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} yet of great practical importance. Super-quadratic quantum speedups for ILPs have been difficult to obtain because classical algorithms for many-constraint ILPs are global and exhaustive, whereas quantum frameworks that offer super-quadratic speedup exploit local structure of the objective and feasible set. We address this via quantum algorithms for Gomory's group relaxation. The group relaxation of an ILP is obtained by dropping nonnegativity on variables that are positive in the optimal solution of the linear programming (LP) relaxation, while retaining integrality of the decision variables. We present a competitive feasibility-preserving classical local-search algorithm for the group relaxation, and a corresponding quantum algorithm that, under reasonable technical conditions, achieves a super-quadratic speedup. When the group relaxation satisfies a nondegeneracy condition analogous to, but stronger than, LP non-degeneracy, our approach yields the optimal solution to the original ILP. Otherwise, the group relaxation tightens bounds on the optimal objective value of the ILP, and can improve downstream branch-and-cut by reducing the integrality gap; we numerically observe this on several practically relevant ILPs. To achieve these results, we derive efficiently constructible constraint-preserving mixers for the group relaxation with favorable spectral properties, which are of independent interest.

Related papers

• Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization [57.66069228055418]
  This paper is about algorithms for computationally constrained multi-level compositional optimization.<n>The objective function is a composition of several smooth nested functions, and the decision is convex and closed.<n>By using a stage-wise design, we derive a parameter-free variant that preserves the same complexities for the Frank-Wolf gap.
  arXiv  Detail & Related papers  (2026-09-14T14:53:18Z)
• Polynomial Time Quantum Approximation Schemes for Constrained Optimisation [0.2578242050187029]
  We build on finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA.<n>We introduce Heavy-Hitter QAOA, which preserves these conditional guarantees while reducing the retained candidate set and classical-processing cost by one power of the problem size.<n> Hardware experiments on IBM Eagle r3 processors cover instances with up to one hundred logical variables or improve every tested QOptlib reference tour.
  arXiv  Detail & Related papers  (2026-08-02T09:35:42Z)
• A Hybrid Classical-Quantum Approach for Multi-Constrained Location Optimization Problem [0.19573380763700712]
  The Maximal Covering Location Problem (MCLP) aims to determine the optimal facility placements that maximize total coverage.<n>It is characterized by both equality and inequality constraints, which ensure correct coverage but significantly increase the complexity of exploring the solution space as instance size grows.<n>In this work, the MCLP is formulated as a Quadratic Unconstrained Binary Optimization model, where constraint embedding plays a critical role in solution quality.
  arXiv  Detail & Related papers  (2026-07-08T19:44:55Z)
• Pure and mixed Dicke state ansatz for equality and inequality constraints in variational quantum eigensolver [0.0]
  Combinatorial optimization can be addressed with quantum computing through variational quantum algorithms.<n>A central challenge is to design an ansatz expressive enough to explore the feasible subspace of the Hilbert space where the optimal solution lies.<n>We propose the first feasibility-preserving mixed Dicke state ansatz for Hamming weight constrained optimization.
  arXiv  Detail & Related papers  (2026-06-07T08:10:09Z)
• 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)
• BandPO: Bridging Trust Regions and Ratio Clipping via Probability-Aware Bounds for LLM Reinforcement Learning [49.25750348525603]
  BandPO replaces canonical clipping with Band, a unified theoretical operator that projects trust regions into dynamic, probability-aware clipping intervals.<n>We show that BandPO consistently outperforms canonical clipping and Clip-Higher, while robustly mitigating entropy collapse.
  arXiv  Detail & Related papers  (2026-03-05T08:03:05Z)
• Hot-Starting Quantum Portfolio Optimization [39.916647837440316]
  Combinatorial optimization with a smooth and convex objective function arises naturally in applications such as discrete mean-variance portfolio optimization.<n>We introduce a novel approach that restricts the search space to discrete solutions in the vicinity of the continuous optimum by constructing a compact Hilbert space.<n> Experiments on software solvers and a D-Wave Advantage quantum annealer demonstrate that our method outperforms state-of-the-art techniques.
  arXiv  Detail & Related papers  (2025-10-13T08:47:43Z)
• 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)
• Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
  We propose a first-order proximal gradient algorithm to solve the perspective relaxation of the problem within a BnB framework.<n>We show that our approach significantly accelerates dual bound computations and is highly effective in providing optimality certificates for large-scale problems.
  arXiv  Detail & Related papers  (2025-02-13T17:14:18Z)
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation [1.4691887238367354]
  We introduce means of efficiently approximating the QAOA optimisation landscape from solution space structures.<n>We derive a new algorithmic of unit-depth QAOA for two-level Hamiltonians.<n>Our approach is based on proving a long-standing conjecture regarding quantum-independent structures in QAOA.
  arXiv  Detail & Related papers  (2024-08-12T21:02:58Z)
• Efficient Internal Strategies in Quantum Relaxation based Branch-and-Bound [1.3499500088995464]
  We develop Quantum Relaxation based Branch-and-Bound ( QR-BnB) QR-BnB is a method incorporating quantum relaxation into the Branch-and-Bound framework. We show that our variable selection strategy via the expectation value of the Pauli operators gives better convergence than the naive random choice.
  arXiv  Detail & Related papers  (2024-05-02T01:28:52Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms.<n>An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• 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)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.