Adaptive Sparsification for Linear Programming

• URL: http://arxiv.org/abs/2510.08348v1
• Date: Thu, 09 Oct 2025 15:36:00 GMT
• Title: Adaptive Sparsification for Linear Programming
• Authors: Étienne Objois, Adrian Vladu,
• Abstract summary: We introduce a generic framework for solving linear programs with many constraints $(n gg d)$ via adaptive sparsification.<n>We present a quantum version of Clarkson's algorithm that finds an exact solution to an LP using $tildeO(sqrtn d3)$ row-queries to the constraint matrix.<n>Second, our framework yields new state-of-the-art algorithms for mixed packing and covering problems when the packing constraints are simple''
• Score: 3.735586259382096
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a generic framework for solving linear programs (LPs) with many constraints $(n \gg d)$ via adaptive sparsification. Our approach provides a principled generalization of the techniques of [Assadi '23] from matching problems to general LPs and robustifies [Clarkson's '95] celebrated algorithm for the exact setting. The framework reduces LP solving to a sequence of calls to a ``low-violation oracle'' on small, adaptively sampled subproblems, which we analyze through the lens of the multiplicative weight update method. Our main results demonstrate the versatility of this paradigm. First, we present a quantum version of Clarkson's algorithm that finds an exact solution to an LP using $\tilde{O}(\sqrt{n} d^3)$ row-queries to the constraint matrix. This is achieved by accelerating the classical bottleneck (the search for violated constraints) with a generalization of Grover search, decoupling the quantum component from the classical solver. Second, our framework yields new state-of-the-art algorithms for mixed packing and covering problems when the packing constraints are ``simple''. By retaining all packing constraints while sampling only from the covering constraints, we achieve a significant width reduction, leading to faster solvers in both the classical and quantum query models. Our work provides a modular and powerful approach for accelerating LP solvers.

Related papers

• Efficient Penalty-Based Bilevel Methods: Improved Analysis, Novel Updates, and Flatness Condition [51.22672287601796]
  Penalty-based methods have become popular for solving bilevel optimization (BLO) problems.<n>They often require inner-loop iteration to solve the lower-level (LL) problem and small outer-loop step sizes to handle the increased smoothness induced by large penalty terms.<n>This work considers the general BLO problems with coupled constraints (CCs) and leverages a novel penalty reformulation that decouples the upper- and lower-level variables.
  arXiv  Detail & Related papers  (2025-11-20T20:48:14Z)
• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
  State-of-the-art Large Language Model (LLM) pruning methods operate layer-wise, minimizing the per-layer pruning error on a small dataset to avoid full retraining.<n>Existing methods hence rely on greedy convexs that ignore the weight interactions in the pruning objective.<n>Our method drastically reduces the per-layer pruning error, outperforms strong baselines on state-of-the-art GPT architectures, and remains memory-efficient.
  arXiv  Detail & Related papers  (2025-10-15T16:13:44Z)
• A competitive NISQ and qubit-efficient solver for the LABS problem [0.0]
  Pauli Correlation.<n>(PCE) has recently been introduced as a qubit-efficient approach to optimization problems within variational quantum algorithms.<n>We extend the PCE-based framework to solve the Low Autocorrelation Binary Sequences (LABS) problem.
  arXiv  Detail & Related papers  (2025-06-20T18:00:02Z)
• 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)
• A Quantum Constraint Generation Framework for Binary Linear Programs [0.0]
  We propose a new approach to utilize quantum computers for binary linear programming (BLP)<n>Quantum optimization algorithms, hybrid or quantum-only, are currently general purpose, standalone solvers for ILP.<n>In this study we wrap any suitable quantum optimization algorithm into a quantum informed classical constraint generation framework.
  arXiv  Detail & Related papers  (2025-03-27T07:24:33Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression [65.8785736964253]
  We consider contextual bandits with linear constraints (CBwLC), a variant of contextual bandits in which the algorithm consumes multiple resources subject to linear constraints on total consumption. This problem generalizes contextual bandits with knapsacks (CBwK), allowing for packing and covering constraints, as well as positive and negative resource consumption. We provide the first algorithm for CBwLC (or CBwK) that is based on regression oracles. The algorithm is simple, computationally efficient, and statistically optimal under mild assumptions.
  arXiv  Detail & Related papers  (2022-11-14T16:08:44Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Quantum constraint learning for quantum approximate optimization algorithm [0.0]
  This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
  arXiv  Detail & Related papers  (2021-05-14T11:31:14Z)
• A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization [5.460573052311485]
  We propose a hybrid framework to solve large-scale permutation-based problems using a high-performance quadratic unconstrained binary optimization solver. We propose techniques to overcome the challenges in using a QUBO solver that typically comes with limited numbers of bits.
  arXiv  Detail & Related papers  (2020-09-27T07:15:25Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  This paper proposes near-optimal algorithms for the pure-exploration linear bandit problem in the fixed confidence and fixed budget settings. We provide an algorithm whose sample complexity scales with the geometry of the instance and avoids an explicit union bound over the number of arms. We also propose the first algorithm for linear bandits in the the fixed budget setting.
  arXiv  Detail & Related papers  (2020-06-21T00:56:33Z)

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.