Parallel splitting method for large-scale quadratic programs

• URL: http://arxiv.org/abs/2503.16977v1
• Date: Fri, 21 Mar 2025 09:45:47 GMT
• Title: Parallel splitting method for large-scale quadratic programs
• Authors: Matteo Vandelli, Francesco Ferrari, Daniele Dragoni,
• Abstract summary: SPLIT is a framework for decomposing large-scale quadratic programs into smaller subproblems, which are then solved in parallel.<n>We show that SPLIT is capable of providing drastic reductions in computational time, while delivering high-quality solutions.
• Score: 2.520799507359113
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 overcome these limitations, we introduce SPLIT, a general-purpose quantum-inspired framework for decomposing large-scale quadratic programs into smaller subproblems, which are then solved in parallel. SPLIT accounts for cross-interactions between subproblems, which are usually neglected in other decomposition techniques. The SPLIT framework can integrate generic subproblem solvers, ranging from standard branch-and-bound methods to quantum optimization algorithms. We demonstrate its effectiveness through comparisons with commercial solvers on the MaxCut and Antenna Placement Problems, with up to 20,000 decision 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 particularly suited for near real-time applications that require a solution within a strict time frame, or when the problem size exceeds the hardware limitations of dedicated devices, such as current quantum computers.

Related papers

• SCOOP: A Quantum-Computing Framework for Constrained Combinatorial Optimization [0.0]
  We present SCOOP, a novel framework for solving constrained optimization problems. SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins. We demonstrate the framework on three NP-hard problems, Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover.
  arXiv  Detail & Related papers  (2025-04-15T06:17:23Z)
• Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
  We show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario. We follow by submitting instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios.
  arXiv  Detail & Related papers  (2024-06-11T19:59:05Z)
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  We present Unified Spectral Bundling with Sketching (USBS), a provably correct, fast and scalable algorithm for solving massive SDPs. USBS provides a 500x speed-up over the state-of-the-art scalable SDP solver on an instance with over 2 billion decision variables.
  arXiv  Detail & Related papers  (2023-12-19T02:27:22Z)
• Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows [5.818566833386833]
  We introduce a novel temporal decomposition scheme for solving a class of offline PDPTWs. Our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty.
  arXiv  Detail & Related papers  (2023-03-06T20:07:05Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms [0.0]
  We apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach.
  arXiv  Detail & Related papers  (2021-01-19T19:00:40Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Optimizing the Optimizer: Decomposition Techniques for Quantum Annealing [0.0]
  Current generation quantum computers are too small to solve real-world problems. In this work, we explore multiple heterogeneous approaches to solving benchmark problems. Our results indicate that solver performance is highly dependent on the structure of the problem graph.
  arXiv  Detail & Related papers  (2020-01-16T21:35:16Z)

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.