Accelerating Extended Benders Decomposition with Quantum-Classical Hybrid Solver

• URL: http://arxiv.org/abs/2510.03647v2
• Date: Tue, 07 Oct 2025 07:59:06 GMT
• Title: Accelerating Extended Benders Decomposition with Quantum-Classical Hybrid Solver
• Authors: Takuma Yoshihara, Masayuki Ohzeki,
• Abstract summary: We propose a quantum-classical hybrid method for solving large-scale mixed-integer quadratic problems.<n>Our results show that this hybrid approach efficiently yields near-optimal solutions.
• Score: 0.7734726150561088
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a quantum-classical hybrid method for solving large-scale mixed-integer quadratic problems (MIQP). Although extended Benders decomposition is effective for MIQP, its master problem which handles the integer and quadratic variables often becomes a computational bottleneck. To address this challenge, we integrate the D-Wave CQM solver into the decomposition framework to solve the master problem directly. Our results show that this hybrid approach efficiently yields near-optimal solutions and, for certain problem instances, achieves exponential speedups over the leading commercial classical solver. These findings highlight a promising computational strategy for tackling complex mixed-integer optimization problems.

Related papers

• 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)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  Branch-and-bound algorithms effectively solve convex optimization problems, relying on the relaxation the objective function to obtain tight lower bounds.<n>We propose a branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO) algorithm that addresses the relaxation difficulties.
  arXiv  Detail & Related papers  (2025-04-21T18:19:19Z)
• Quantum annealing applications, challenges and limitations for optimisation problems compared to classical solvers [7.784135533096431]
  We benchmark D-Wave's hybrid solver against that of industry-leading solvers.<n>The findings indicate that D-Wave's solver is most advantageous for integer quadratic objective functions.<n>While D-Wave can solve such problems, its performance has not yet matched that of its classical counterparts.
  arXiv  Detail & Related papers  (2024-09-09T12:07:52Z)
• DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems [37.205311971072405]
  DISCO is an efficient DIffusion solver for large-scale Combinatorial Optimization problems.<n>It constrains the sampling space to a more meaningful domain guided by solution residues, while preserving the multi-modal properties of the output distributions.<n>It delivers strong performance on large-scale Traveling Salesman Problems and challenging Maximal Independent Set benchmarks, with inference time up to 5.28 times faster than other diffusion alternatives.
  arXiv  Detail & Related papers  (2024-06-28T07:36:31Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• A hybrid Quantum-Classical Algorithm for Mixed-Integer Optimization in Power Systems [0.0]
  We present a framework for solving power system optimization problems with a Quantum Computer (QC) Our guiding applications are the optimal transmission switching and the verification of neural networks trained to solve a DC Optimal Power Flow.
  arXiv  Detail & Related papers  (2024-04-16T16:11:56Z)
• A Hybrid Quantum-Classical Approach to the Electric Mobility Problem [0.8796261172196743]
  We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem. We benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics. The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints.
  arXiv  Detail & Related papers  (2023-10-04T12:14:56Z)
• A Deep Unrolling Model with Hybrid Optimization Structure for Hyperspectral Image Deconvolution [50.13564338607482]
  We propose a novel optimization framework for the hyperspectral deconvolution problem, called DeepMix.<n>It consists of three distinct modules, namely, a data consistency module, a module that enforces the effect of the handcrafted regularizers, and a denoising module.<n>This work proposes a context aware denoising module designed to sustain the advancements achieved by the cooperative efforts of the other modules.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms [18.075115172621096]
  We present a formal analysis of hybrid algorithms in the context of solving mixed-binary quadratic programs via Ising solvers. We propose to solve this reformulation with a hybrid quantum-classical cutting-plane algorithm.
  arXiv  Detail & Related papers  (2022-07-27T16:47:32Z)
• 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)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  We experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We find the problem hardness is controlled by the solution degeneracy and number of local minima. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions.
  arXiv  Detail & Related papers  (2022-02-18T19:00:01Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.