Parallel splitting method for large-scale quadratic programs

Abstract:Current algorithms for large-scale industrial optimization problems typically face a trade-off: they either require exponential time to reach optimal solutions, or employ problem-specific heuristics. To address these limitations, we introduce SPLIT, a general-purpose quantum-inspired framework for decomposing large-scale quadratic programs into smaller subproblems, which are solved in parallel. SPLIT heuristically accounts for objective-function cross-interactions between subproblems, usually neglected in other decomposition techniques. The SPLIT framework can integrate generic subproblem solvers, from branch-and-bound to quantum optimization methods. We demonstrate its effectiveness through comparisons with commercial solvers and published results on MaxCut and Antenna Placement Problems, with up to 20,000 variables. Our results show that SPLIT is capable of providing drastic reductions in computational time, while delivering high-quality solutions. In these regards, the proposed method is well-suited for near real-time applications that require a solution within a strict time frame, or when the problem size exceeds hardware limitations of dedicated devices, such as current quantum computers.

Quantum Physics (quant-ph); Optimization and Control (math.OC)

arXiv:2503.16977 [quant-ph]

(or arXiv:2503.16977v3 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2503.16977 Focus to learn more arXiv-issued DOI via DataCite

https://doi.org/10.1007/s10732-026-09606-4 Focus to learn more DOI(s) linking to related resources

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.