We demonstrate an end-to-end hybrid quantum-classical optimisation framework based on Benders decomposition, capable of solving mixed-integer linear programming (MILP) problems. The framework builds on a previously presented hybrid quantum-classical end-to-end pipeline based on Multiple Cuts via Multiple Solutions (MCMS) Benders decomposition where the cut selection step was performed on quantum annealing hardware. We extend this with gate-based QAOA implementations for both tensor network emulators and superconducting quantum hardware. The Vehicle Routing Problem (VRP) is used as a representative case study and we run the pipeline end-to-end on 10 permutations of a standardised benchmarking instance (20 customers and 4 vehicles from QOptLib) with a classical solver performing the cut selection step. We find that for our instances, only a small fraction of the compute in classical MCMS Benders decomposition is spent on the cut selection step. For a full hybrid end-to-end assessment, we run the pipeline for a toy problem with MPS-JuliQAOA, a powerful tensor network emulator, to execute QAOA. Here, the majority of the time is spent on the cut selection step, deeming quantum advantage of this framework unlikely at problems of this size. This highlights the need for more large-scale benchmarking research when more powerful (QPU) QUBO solvers are available.
We demonstrate an end-to-end hybrid quantum-classical optimisation framework based on Benders decomposition, capable of solving mixed-integer linear programming (MILP) problems. The framework builds on a previously presented hybrid quantum-classical end-to-end pipeline based on Multiple Cuts via Multiple Solutions (MCMS) Benders decomposition where the cut selection step was performed on quantum annealing hardware. We extend this with gate-based QAOA implementations for both tensor network emulators and superconducting quantum hardware. The Vehicle Routing Problem (VRP) is used as a representative case study and we run the pipeline end-to-end on 10 permutations of a standardised benchmarking instance (20 customers and 4 vehicles from QOptLib) with a classical solver performing the cut selection step. We find that for our instances, only a small fraction of the compute in classical MCMS Benders decomposition is spent on the cut selection step. For a full hybrid end-to-end assessment, we run the pipeline for a toy problem with MPS-JuliQAOA, a powerful tensor network emulator, to execute QAOA. Here, the majority of the time is spent on the cut selection step, deeming quantum advantage of this framework unlikely at problems of this size. This highlights the need for more large-scale benchmarking research when more powerful (QPU) QUBO solvers are available.
Mixed-integer linear programming problems are extensively used in industry for a wide range of optimization tasks. However, as they get larger, they present computational challenges for classical solvers within practical time limits. Quantum annealers can, in principle, accelerate the solution of problems formulated as quadratic unconstrained binary optimization instances, but their limited scale currently prevents achieving practical speedups. Quantum-classical algorithms have been proposed to take advantage of both paradigms and to allow current quantum computers to be used in larger problems. In this work, a hardware-agnostic Benders' decomposition algorithm and a series of enhancements with the goal of taking the most advantage of quantum computing are presented. The decomposition consists of a master problem with integer variables, which is reformulated as a quadratic unconstrained binary optimization problem and solved with a quantum annealer, and a linear subproblem solved by a classical computer. The enhancements consist, among others, of different embedding processes that substantially reduce the pre-processing time of the embedding computation without compromising solution quality, a conservative handling of cut constraints, and a stopping criterion that accounts for the limited size of current quantum computers and their heuristic nature. The proposed algorithm is benchmarked against classical approaches using a D-Wave quantum annealer for a scalable family of transmission network expansion planning problems.
Leveraging the current generation of quantum devices to solve optimization problems of practical interest necessitates the development of hybrid quantum-classical (HQC) solution approaches. In this paper, a multi-cut Benders decomposition (BD) approach that exploits multiple feasible solutions of the master problem (MP) to generate multiple valid cuts is adapted, so as to be used as an HQC solver for general mixed-integer linear programming (MILP) problems. The use of different cut selection criteria and strategies to manage the size of the MP by eliciting a subset of cuts to be added in each iteration of the BD scheme using quantum computing is discussed. The HQC optimization algorithm is applied to the Unit Commitment (UC) problem. UC is a prototypical use case of optimization applied to electrical power systems, a critical sector that may benefit from advances in quantum computing. The proposed approach is demonstrated using the D-Wave Advantage 4.1 quantum annealer.
The Benders’ decomposition algorithm is a technique in mathematical programming for complex mixed-integer linear programming (MILP) problems with a particular block structure. The strategy of Benders’ decomposition can be described as a strategy of divide and conquer. The Benders’ decomposition algorithm has been employed in a variety of applications such as communication, networking, and machine learning. However, the master problem in Benders’ decomposition is still NP-hard, which motivates us to employ quantum computing. In the paper, we propose a hybrid quantum-classical Benders’ decomposition algorithm. We transfer the Benders’ decomposition’s master problem into the quadratic unconstrained binary optimization (QUBO) model and solve it by the state-of-the-art quantum annealer. Then, we analyze the computational results and discuss the feasibility of the proposed algorithm. Due to our reformulation in the master problem in Benders’ decomposition, our hybrid algorithm, which takes advantage of both classical and quantum computers, can guarantee the solution quality for solving MILP problems.
The optimization of front-end crude oil scheduling is a critical determinant of refinery profitability and operational stability. However, the coupling of discrete logistics events (e.g., vessel berthing) with continuous material flows (e.g., pipeline transfers) renders this problem an NP-hard Mixed-Integer Linear Programming (MILP) challenge, often intractable for classical solvers at industrial scales. This study proposes a novel hybrid quantum-classical framework to address these computational bottlenecks. We employ Benders Decomposition to decouple the monolithic model into a discrete Master Problem (MP) and a continuous Subproblem (SP). To exploit the search capabilities of quantum computing, the MP is reformulated as a Quadratic Unconstrained Binary Optimization (QUBO) model and solved via a hybrid quantum solver, while the SP enforces mass balance and quality constraints through iterative optimality and feasibility cuts. Extensive experiments on 15 multi-scale instances demonstrate that the proposed framework significantly outperforms traditional metaheuristics (e.g., Genetic Algorithms, Tabu Search), reducing total operating costs by approximately 73--80% and achieving computational speeds comparable to state-of-the-art commercial solvers (Gurobi). By effectively leveraging global optimality cuts, the method overcomes the tendency of heuristic approaches to trap in local optima, providing a robust and scalable solution for complex refinery logistics.
This paper presents a hybrid classical-quantum approach to solve mixed-integer linear programming (MILP) using neutral-atom quantum computations. We apply Benders decomposition (BD) to segment MILPs into a master problem (MP) and a subproblem, where the MP is addressed using a neutral-atom device, after being transformed into a quadratic unconstrained binary optimization (QUBO) model, with an automatized procedure. Our MILP to QUBO conversion tightens the upper bounds of the continuous variables involved, positively impacting the required qubit count, and the convergence of the algorithm. To solve the QUBO, we develop a heuristic for atom register embedding and apply a variational algorithm for pulse shaping. In addition, we implement a proof of concept that outperforms existing solutions. We also conduct preliminary numerical results: In a series of small MILP instances our algorithm identifies over 95% of feasible solutions of high quality, outperforming classical BD approaches where the MP is solved using simulated annealing.
Abstract: Global logistics networks, intercontinental air-freight consolidators, and maritime energy fleets continuously solve large-scale Mixed-Integer Linear Programs (MILPs) such as the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and multi-vessel Maritime Inventory Routing Problems (MIRP). When weather disruptions, port congestion, or geopolitical airspace closures invalidate baseline schedules, classical branch-and-cut solvers (Gurobi, CPLEX) experience exponential worst-case tree growth on subproblems exceeding 2,000 binary decision variables, often failing to converge within strict 5-to-15-minute operational re-dispatch windows. Conversely, current Noisy Intermediate-Scale Quantum (NISQ) processors remain limited to 100-to-1,000 physical qubits with finite two-qubit gate fidelity (99.2%−99.8%), preventing direct encoding of full enterprise logistics instances. This paper presents a production-grade Quantum-Classical Hybrid Cloud Architecture that bridges enterprise Kubernetes clusters with co-located quantum processing units (QPUs) via AWS Braket Hybrid Jobs and IBM Quantum Qiskit Runtime primitives. Our framework applies Benders and Dantzig-Wolfe column generation on classical cloud HPC nodes to decompose a 25,000-variable global fleet MILP into a continuous master problem and hard combinatorial pricing/routing subproblems of 60 to 140 binary variables. These subproblems are transformed into Quadratic Unconstrained Binary Optimization (QUBO) and Ising Hamiltonians, warm-started from classical linear programming (LP) relaxations (WS-QAOA), compiled with dynamical decoupling and Zero-Noise Extrapolation (ZNE), and executed inside co-located QPU-CPU sessions while a GPU-accelerated Simulated Bifurcation (SB) digital annealer runs in parallel as a deterministic SLA fallback. Evaluated on disruption recovery workloads modeled on ExxonMobil maritime LNG routing and DHL Global Forwarding air-cargo container loading, our hybrid WS-QAOA + Column Generation workflow improves optimality gap closure at a 10-minute SLA cutoff from 6.84% (classical branch-and-bound alone) to 1.42%, reduces emergency re-routing compute wall-clock time by 61.5%, and cuts fleet fuel and charter penalty costs by 4.7%. Research Domain & Specialization Track Master of Science in Information Technology (MSIT) — Quantum Cloud Computing, Hybrid Orchestration, and Operations Research. Core Technical Highlights Empirical Production Case Studies: Rigorous architectural blueprints and telemetry evaluation across enterprise cloud deployments. Four-Tier Reference Architecture: Formal specification from edge ingress to distributed hardware execution pools. Mathematical Formulation: Formally derived algorithmic and optimization models with closed-loop verification. Multi-Modal Benchmarking: Comparative empirical baselines under fault-injection and synthetic workload scaling. Author Information Author: Sonu Kumar SinghRole: Senior Consultant Affiliation: Independent Researcher Publication Status: Preprint / Working Paper (MSIT AI & Cloud Systems Research Series) Reproducibility & Open Science All included architecture diagrams, telemetry schemas, and benchmark curves are open-access under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.