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

Decomposition of large-scale 0-1 programs

Peter John Ryan

Published Jan 1, 1973• 0 citations
Publisher
DOI
10.20381/ruor-1629

Related papers

Parallel splitting method for large-scale quadratic programs

Matteo Vandelli, Francesco Ferrari, Daniele Dragoni

arXiv:2503.16977•Journal of Heuristics•Sep 20, 2026•6 citations

A MAX-CUT formulation of 0/1 programs

Jean Bernard Lasserre

arXiv:1505.06840•Operations Research Letters•Dec 29, 2015•32 citations

Decomposition methods for large scale LP decoding

Siddharth Barman, Xishuo Liu, Stark Christiaan Draper +1 more

Feldman et al. (IEEE Trans. Inform. Theory, Mar. 2005) showed that linear programming (LP) can be used to decode linear error correcting codes. The bit-error-rate performance of LP decoding is comparable to state-of-the-art BP decoders, but has significantly stronger theoretical guarantees. However, LP decoding when implemented with standard LP solvers does not easily scale to the block lengths of modern error correcting codes. In this paper we draw on decomposition methods from optimization theory to develop efficient distributed algorithms for LP decoding. The key enabling technical result is a nearly linear time algorithm for two-norm projection onto the parity polytope. This allows us to use LP decoding, with all its theoretical guarantees, to decode large-scale error correcting codes efficiently.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2011•35 citations

Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

Hantao Nie, Dong Un An, Zaiwen Wen

Semidefinite programming (SDP) is a fundamental convex optimization problem with wide-ranging applications. However, solving large-scale instances remains computationally challenging due to the high cost of solving linear systems and performing eigenvalue decompositions. In this paper, we present a quantum alternating direction method of multipliers (QADMM) for SDPs, building on recent advances in quantum computing. An inexact ADMM framework is developed, which tolerates errors in the iterates arising from block-encoding approximation and quantum measurement. Within this robust scheme, we design a polynomial proximal operator to address the semidefinite conic constraints and apply the quantum singular value transformation to accelerate the most costly projection updates. We prove that the scheme converges to an ϵ -optimal solution of the SDP problem under the strong duality assumption. A detailed complexity analysis shows that the QADMM algorithm achieves favorable scaling with respect to dimension compared to the classical ADMM algorithm and quantum interior point methods, highlighting its potential for solving large-scale SDPs.

arXiv:2510.10056•Quantum•Jul 8, 2026•2 citations

Experiments in quadratic 0–1 programming

Francisco Barahona, Michael Jünger, Gerhard Reinelt

Mathematical Programming•May 1, 1989•208 citations

Hybrid Quantum-Classical Computing Model for Battery Scheduling

Ibrahim Saad Alsaidan, Amin Khodaei

This study utilizes quantum computing resources to address the optimization problem of battery scheduling. Traditionally, such problems are formulated as Mixed-Integer Linear Programming (MILP) models and solved using classical algorithms such as branch-and-cut and Cutting Plane algorithms. However, these classical algorithms exhibits limitations when handling large-scale problems. To mitigate these limitations, decomposition techniques are typically implemented to handle large-scale complex MILP problems. Although decomposition technique increases the cababilities of classical computing resources to deal with large-scale probelems, they are still constrained by the physical limitation of classical hardware. In this paper, the utilization of both quantum and classical computing resource to solve MILP optimization problem is explored through proposing a hybrid quantum-classical battery scheduling model. The proposed battery scheduling model is decomposed into two operational layers: a time slot optimization layer (layer-1) and a charging/discharging power optimization layer (layer-2). In the first layer, the computational power of quantum resources is utilized to determine the optimal time slots for battery charging, discharging, or remaining idle. Once these time slots are determined, the second layer focuses on optimizing the amount of power to be charged or discharged. Bender’s decomposition technique is employed to implement the proposed model, and the results are compared with those obtained using classical algorithms.

IEEE PowerTech Conference•Jun 29, 2025•0 citations
Feldman et al. (IEEE Trans. Inform. Theory, Mar. 2005) showed that linear programming (LP) can be used to decode linear error correcting codes. The bit-error-rate performance of LP decoding is comparable to state-of-the-art BP decoders, but has significantly stronger theoretical guarantees. However, LP decoding when implemented with standard LP solvers does not easily scale to the block lengths of modern error correcting codes. In this paper we draw on decomposition methods from optimization theory to develop efficient distributed algorithms for LP decoding. The key enabling technical result is a nearly linear time algorithm for two-norm projection onto the parity polytope. This allows us to use LP decoding, with all its theoretical guarantees, to decode large-scale error correcting codes efficiently.
Semidefinite programming (SDP) is a fundamental convex optimization problem with wide-ranging applications. However, solving large-scale instances remains computationally challenging due to the high cost of solving linear systems and performing eigenvalue decompositions. In this paper, we present a quantum alternating direction method of multipliers (QADMM) for SDPs, building on recent advances in quantum computing. An inexact ADMM framework is developed, which tolerates errors in the iterates arising from block-encoding approximation and quantum measurement. Within this robust scheme, we design a polynomial proximal operator to address the semidefinite conic constraints and apply the quantum singular value transformation to accelerate the most costly projection updates. We prove that the scheme converges to an ϵ -optimal solution of the SDP problem under the strong duality assumption. A detailed complexity analysis shows that the QADMM algorithm achieves favorable scaling with respect to dimension compared to the classical ADMM algorithm and quantum interior point methods, highlighting its potential for solving large-scale SDPs.
This study utilizes quantum computing resources to address the optimization problem of battery scheduling. Traditionally, such problems are formulated as Mixed-Integer Linear Programming (MILP) models and solved using classical algorithms such as branch-and-cut and Cutting Plane algorithms. However, these classical algorithms exhibits limitations when handling large-scale problems. To mitigate these limitations, decomposition techniques are typically implemented to handle large-scale complex MILP problems. Although decomposition technique increases the cababilities of classical computing resources to deal with large-scale probelems, they are still constrained by the physical limitation of classical hardware. In this paper, the utilization of both quantum and classical computing resource to solve MILP optimization problem is explored through proposing a hybrid quantum-classical battery scheduling model. The proposed battery scheduling model is decomposed into two operational layers: a time slot optimization layer (layer-1) and a charging/discharging power optimization layer (layer-2). In the first layer, the computational power of quantum resources is utilized to determine the optimal time slots for battery charging, discharging, or remaining idle. Once these time slots are determined, the second layer focuses on optimizing the amount of power to be charged or discharged. Bender’s decomposition technique is employed to implement the proposed model, and the results are compared with those obtained using classical algorithms.