Accelerating Extended Benders Decomposition with Quantum-Classical Hybrid Solver

1. Problem Statement

The paper addresses the computational challenges associated with Mixed-Integer Quadratic Programming (MIQP), a class of optimization problems where the objective function or constraints contain quadratic terms involving both discrete (integer) and continuous variables.

• Context: MIQPs are critical for real-world applications such as unit commitment in power systems and cardinality-constrained portfolio optimization.
• The Bottleneck: While Extended Benders Decomposition (EBD) is a standard technique for solving MIQPs by iteratively decomposing the problem into a "master problem" and a "subproblem," the master problem itself is often an NP-hard MIQP. Solving this master problem using classical solvers becomes a severe computational bottleneck, especially as problem size increases, due to the difficulty of optimizing quadratic forms over discrete variables ($x^T C x$).
• Limitations of Existing Methods: Previous attempts to accelerate EBD using machine learning or pure quantum annealing (QA) have been limited to linear or simplified structures, failing to handle the complex quadratic interactions inherent in general MIQPs.

2. Methodology

The authors propose a Quantum-Classical Hybrid Method that integrates the D-Wave Constrained Quadratic Model (CQM) solver into the EBD framework to solve the master problem directly.

A. Extended Benders Decomposition (EBD) Framework

The standard EBD process is utilized:

1. Decomposition: The original MIQP is split into a master problem (handling integer variables $x$) and a subproblem (handling continuous variables $y$).
2. Dual Subproblem: The subproblem is solved using Lagrange relaxation and the weak duality theorem to generate optimality cuts (constraints) based on dual variables ($\lambda$).
3. Master Problem Update: The master problem is updated with these cuts. The process iterates until the duality gap between the primal and dual solutions falls below a threshold ($\epsilon = 0.5$).

B. Hybrid Solver Integration

The core innovation lies in replacing the classical solver for the master problem with the D-Wave CQM solver.

• Challenge: The CQM solver (and Quantum Annealing) natively handles discrete binary variables but struggles with continuous variables and inequality constraints.
• Transformation Strategy:
  1. Discretization: The continuous auxiliary variable $t$ in the master problem is discretized using a binary representation (Eq. 9), converting it into a sum of binary variables.
  2. Constraint Handling: Inequality constraints are converted into equality constraints by introducing non-negative slack variables (represented as binary sums).
  3. Penalty Method: These equality constraints are squared and added to the objective function as penalty terms (Eq. 10), transforming the entire master problem into a Constrained Quadratic Model (CQM) or effectively a QUBO (Quadratic Unconstrained Binary Optimization) form suitable for the hybrid solver.

3. Key Contributions

• Novel Hybrid Architecture: First proposal to integrate the D-Wave CQM solver specifically for the master problem of EBD in MIQP contexts, moving beyond linear approximations.
• Mathematical Formulation: Developed a rigorous method to convert continuous variables and inequality constraints within the EBD master problem into a format compatible with quantum-classical hybrid solvers via discretization and penalty methods.
• Scalability Demonstration: Provided empirical evidence that this hybrid approach scales more favorably than state-of-the-art classical solvers for large-scale instances.

4. Experimental Results

The authors conducted comparative experiments against Simulated Annealing (SA), Gurobi Optimizer (a leading classical MIP solver), and the D-Wave CQM solver.

• Convergence Accuracy:

  • SA, Gurobi, and CQM all achieved convergence to near-optimal solutions for small-scale problems.
  • Pure Quantum Annealing (QA) failed to converge to the required accuracy, highlighting the necessity of the hybrid CQM approach for EBD.
  • Exactness: The solutions obtained via EBD+CQM matched those of direct Gurobi solutions, validating the method's correctness.

• Scalability and Performance:

  • Simulated Annealing: Showed poor scalability; success rates dropped significantly as problem size increased (convergence lost at size ~220).
  • Gurobi vs. CQM: As the number of integer variables increased (from 100 to 1000), Gurobi's computation time grew rapidly. In contrast, the CQM solver demonstrated significantly moderated growth, achieving faster solution times for large-scale instances.
  • Constraint Scaling: When the number of constraints was increased (with binary variables fixed at 400), CQM maintained a speed advantage over Gurobi.

• Speedup: The hybrid approach achieved exponential speedups over Gurobi for certain problem instances, particularly in the large-scale regime.

5. Significance and Future Outlook

• Strategic Impact: This work establishes a promising computational strategy for tackling complex mixed-integer optimization problems that are currently intractable for classical solvers at scale.
• Real-World Applicability: The method offers natural scalability without performance degradation, making it highly suitable for dynamic real-world applications like power grid management and financial portfolio optimization.
• Future Work: The authors plan to extend this framework to handle more complex continuous variables and a higher density of constraints. They aim to define the specific boundaries of scalability and validate the approach on representative industrial MIQP problems.

In conclusion, the paper demonstrates that combining the iterative strength of Extended Benders Decomposition with the quadratic optimization capabilities of the D-Wave CQM solver creates a powerful, scalable hybrid engine capable of solving large-scale MIQPs more efficiently than current leading classical methods.