arXiv:2204.04574 · Chinese Control Conference (CCC)

Quantum-Inspired Solvers on Mixed-Integer Linear Programming Problem

Hao Wang, Yu Pan, Wei Cui

Published Jul 25, 2022• 2 citations

Abstract

Mixed-integer linear programming (MILP) plays a crucial role in artificial intelligence, biochemistry, finance, cryp-tography, etc. Notwithstanding popular for decades, the researches of MILP solvers are still limited by the resource consumption caused by complexity and failure of Moore's Law. Quantum-inspired Ising machines, as a new computing paradigm, can be used to solve integer programming problems by reducing them into Ising models. Therefore, it is necessary to understand the technical evolution of quantum inspired solvers to break the bottleneck. In this paper, the concept and traditional algorithms for MILP are introduced. Then, focused on Ising model, the principle and implementations of annealers and coherent Ising machines are summarized. Finally, the paper discusses the challenges and opportunities of miniaturized solvers in the future.

DOI: 10.23919/ccc55666.2022.9902772

Related papers

Hybrid Quantum Benders’ Decomposition For Mixed-integer Linear Programming

Zhongqi Zhao, Lei Fan, Zhu Han

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.

arXiv:2112.07109IEEE Wireless Communications and Networking ConferenceApr 10, 202251 citations

Mixed-integer linear programming solver using Benders decomposition assisted by a neutral-atom quantum processor

M. Yassine Naghmouchi, Wesley da Silva Coelho

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.

arXiv:2402.05748Physical Review AJul 12, 202412 citations

Solving the resource constrained project scheduling problem with quantum annealing

Luis Fernando Pérez Armas, Stefan Creemers, Samuel Deleplanque

Quantum annealing emerges as a promising approach for tackling complex scheduling problems such as the resource-constrained project scheduling problem (RCPSP). This study represents the first application of quantum annealing to solve the RCPSP, analyzing 12 well-known mixed integer linear programming (MILP) formulations and converting the most qubit-efficient one into a quadratic unconstrained binary optimization (QUBO) model. We then solve this model using the D-wave advantage 6.3 quantum annealer, comparing its performance against classical computer solvers. Our results indicate significant potential, particularly for small to medium-sized instances. Further, we introduce time-to-target and Atos Q-score metrics to evaluate the effectiveness of quantum annealing and reverse quantum annealing. The paper also explores advanced quantum optimization techniques, such as customized anneal schedules, enhancing our understanding and application of quantum computing in operations research.

Scientific ReportsJul 22, 202430 citations

Performance enhancing of hybrid quantum-classical Benders approach for MILP optimization

Sergio López-Baños, Elisabeth Lobe, Ontje Lünsdorf +1 more

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.

quant-pharXiv:2601.14024Jan 21, 20260 citations

Quantum annealing applications, challenges and limitations for optimisation problems compared to classical solvers

Finley Alexander Quinton, Per Arne Sevle Myhr, Mostafa Barani +2 more

Quantum computing is rapidly advancing, harnessing the power of qubits' superposition and entanglement for computational advantages over classical systems. However, scalability poses a primary challenge for these machines. By implementing a hybrid workflow between classical and quantum computing instances, D-Wave has succeeded in pushing this boundary to the realm of industrial use. Furthermore, they have recently opened up to mixed integer linear programming (MILP) problems, expanding their applicability to many relevant problems in the field of optimisation. However, the extent of their suitability for diverse problem categories and their computational advantages remains unclear. This study conducts a comprehensive examination by applying a selection of diverse case studies to benchmark the performance of D-Wave's hybrid solver against that of industry-leading solvers such as CPLEX, Gurobi, and IPOPT. The findings indicate that D-Wave's hybrid solver is currently most advantageous for integer quadratic objective functions and shows potential for quadratic constraints. To illustrate this, we applied it to a real-world energy problem, specifically the MILP unit commitment problem. While D-Wave can solve such problems, its performance has not yet matched that of its classical counterparts.

arXiv:2409.05542Scientific ReportsApr 13, 202546 citations

A hybrid Quantum-Classical Algorithm for Mixed-Integer Optimization in Power Systems

Petros Ellinas, Samuel C. Chevalier, Spyros Chatzivasileiadis

Mixed Integer Linear Programming (MILP) can be considered the backbone of the modern power system optimization process, with a large application spectrum, from Unit Commitment and Optimal Transmission Switching to verifying Neural Networks for power system applications. The main issue of these formulations is the computational complexity of the solution algorithms, as they are considered NP-Hard problems. Quantum computing has been tested as a potential solution towards reducing the computational burden imposed by these problems, providing promising results, motivating the can be used to speedup the solution of MILPs. In this work, we present a general framework for solving power system optimization problems with a Quantum Computer (QC), which leverages mathematical tools and QCs' sampling ability to provide accelerated solutions. Our guiding applications are the optimal transmission switching and the verification of neural networks trained to solve a DC Optimal Power Flow. Specifically, using an accelerated version of Benders Decomposition , we split a given MILP into an Integer Master Problem and a linear Subproblem and solve it through a hybrid ``quantum-classical'' approach, getting the best of both worlds. We provide 2 use cases, and benchmark the developed framework against other classical and hybrid methodologies, to demonstrate the opportunities and challenges of hybrid quantum-classical algorithms for power system mixed integer optimization problems.

arXiv:2404.10693Apr 16, 20240 citations