Quantum-classical Hybrid Solver Accelerates Extended Benders Decomposition for Large-Scale Mixed-Integer Quadratic Problems

Complex mixed-integer quadratic problems, which arise in fields from finance to logistics, often challenge even the most powerful computers, but a new approach promises significant acceleration. Takuma Yoshihara and Masayuki Ohzeki, from the Graduate School of Information Sciences at Tohoku University, alongside their colleagues, demonstrate a hybrid quantum-classical method that tackles these difficult problems with increased efficiency. The team integrates a quantum solver directly into the established extended Benders decomposition framework, effectively bypassing a major computational bottleneck. Results show this innovative method delivers near-optimal solutions and, crucially, achieves exponential speedups over leading classical solvers for specific problem types, marking a substantial advance in tackling complex optimisation challenges.

Extended Benders decomposition proves effective for MIQP, but its master problem, frequently involving integer and quadratic variables, often becomes a computational bottleneck. To overcome this, the team integrates the D-Wave Constrained Quadratic Model (CQM) solver into the decomposition framework to directly solve the master problem. The results demonstrate that this hybrid approach efficiently yields near-optimal solutions and, for certain problem instances, achieves exponential speedups over a leading commercial classical solver, highlighting a promising computational strategy for tackling complex mixed-integer optimisation problems.

Ebertt-Dantzig Decomposition and Quantum Annealing

This research presents a novel hybrid approach combining Ebertt-Dantzig Decomposition (EBD) with the Constrained Quadratic Model (CQM) solver, implemented on D-Wave quantum annealers, for solving Mixed-Integer Quadratic Programming (MIQP) problems. The authors demonstrate that this combination offers a promising alternative to traditional methods, particularly for large-scale problems, and outperforms traditional solvers, achieving faster solutions as problem size increases. The method also exhibits better scalability compared to Simulated Annealing, which struggles with accuracy on larger problems, and achieves solutions comparable to those obtained with the Gurobi optimizer, validating its correctness and ability to find optimal solutions. This suggests the method holds potential for tackling MIQP instances difficult to address with conventional classical solvers.

The methodology involves leveraging EBD to decompose the MIQP into a master problem and subproblems, which are then solved using the CQM solver. The performance of EBD+CQM is compared against Gurobi and Simulated Annealing in terms of convergence speed and solution accuracy, varying the number of integer and continuous variables, as well as the number of constraints, to assess scalability. The research suggests that the EBD+CQM approach could be a valuable tool for solving real-world MIQP problems in areas such as power system optimisation and portfolio management. Future work will focus on expanding the framework to handle more complex continuous variables and a larger number of constraints, identifying suitable problem classes, and applying the method to solve practical MIQP problems in various domains.

Hybrid Optimisation Solves Complex Quadratic Problems

Scientists have developed a novel hybrid optimisation method for solving large-scale mixed-integer quadratic problems (MIQP), a challenging area with applications in power systems and portfolio optimisation. The research addresses a key bottleneck in existing methods, extended Benders decomposition, which struggles with the computational demands of its master problem. To overcome this, the team integrated the D-Wave Constrained Quadratic Model (CQM) solver directly into the decomposition framework. Experiments demonstrate that this hybrid approach efficiently yields near-optimal solutions, significantly improving performance on complex problems and achieving exponential speedups over a leading commercial classical solver for certain problem instances.

The core of the innovation lies in leveraging the CQM solver’s ability to handle quadratic objectives, a feature that classical solvers often find intractable as problem size increases. The team formulated the MIQP master problem with an objective function minimising a quadratic expression and subject to linear constraints. They then iteratively refined the solution using a dual decomposition technique, applying Lagrange relaxation to simplify the subproblem and identify extreme points. This process allows the hybrid method to effectively navigate the complex interplay between discrete and continuous variables, confirming the potential of combining quantum-inspired solvers with classical optimisation techniques to tackle previously intractable problems in mixed-integer programming.

Hybrid Quantum Solver Scales Optimisation Problems

This research presents a novel hybrid method for solving large-scale mixed-integer quadratic problems, a challenging area of optimisation. By integrating a specific quantum-inspired solver with an established decomposition framework, the team successfully addressed computational bottlenecks often encountered in these complex problems. Results demonstrate that this approach efficiently generates near-optimal solutions and, in certain instances, achieves substantial speedups compared to leading classical solvers, highlighting its potential to tackle previously intractable problems in areas requiring complex optimisation and its promising ability to scale without significant performance degradation. By combining the strengths of both decomposition techniques and the quantum-inspired solver, the researchers have created a powerful tool for addressing large-scale mixed-integer problems. The authors acknowledge that further investigation is needed to fully understand the scalability limits of the method and plan to evaluate its performance under more complex conditions, including an increasing number of variables and constraints. They will assess its effectiveness on representative real-world problems, such as power system optimisation and portfolio optimisation, with the goal of establishing this hybrid approach as a versatile and reliable method for a broad range of applications.