Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor

• URL: http://arxiv.org/abs/2402.05748v2
• Date: Mon, 17 Jun 2024 09:20:00 GMT
• Title: Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor
• Authors: M. Yassine Naghmouchi, Wesley da Silva Coelho,
• Abstract summary: This paper presents a new hybrid classical-quantum approach to solve Mixed Linear Programming (MILP) We apply Benders decomposition (BD) to segment MILPs into a master problem (MP) and a subproblem (SP) Our MILP to QUBO conversion tightens the upper bounds of the involved continuous variables, positively impacting the required qubit count, and the convergence of the algorithm.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents a new 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 (SP), 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 involved continuous variables, 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 (PoC) that outperforms existing solutions. We also conduct preliminary numerical results: in a series of small MILP instances our algorithm identifies over 95 percent of feasible solutions of high quality, outperforming classical BD approaches where the MP is solved using simulated annealing. To the best of our knowledge, this work is the first to utilize a neutral atom quantum processor in developing an automated, problem-agnostic framework for solving MILPs through BD.

Related papers

• Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
  We formulate a Quadratic Unconstrained Binary Optimization (QUBO) problem suitable for solving using quantum computationcolorblue. The formulation aims to find communities with maximal self-sufficiency and minimal power flowing between them. We benchmark the solution quality for multiple approaches: D-Wave's hybrid quantum-classical solvers, classicals, and a branch-and-bound solver.
  arXiv  Detail & Related papers  (2024-07-09T11:44:58Z)
• 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)
• Toward TransfORmers: Revolutionizing the Solution of Mixed Integer Programs with Transformers [3.107843027522116]
  We introduce an innovative deep learning framework that employs a transformer model to address the challenges of mixed-integer programs. Our approach is the first to utilize transformers to predict the binary variables of a mixed-integer programming (MIP) problem. We present an efficient algorithm in which CLSP solutions are learned through a transformer neural network.
  arXiv  Detail & Related papers  (2024-02-20T21:13:38Z)
• Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness [2.854196251981274]
  In this study, we examine two decomposition methods for Mixed-Integer Linear Programming (MILP) We concentrate on breaking down the original problem into smaller subproblems, which are then solved iteratively using a combined quantum-classical hardware approach. Our experimental results demonstrate that this approach can save up to 90% of qubits compared to existing methods on quantum annealing and gate-based quantum computers.
  arXiv  Detail & Related papers  (2023-04-30T13:10:56Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Hybrid Quantum-Classical Multi-cut Benders Approach with a Power System Application [0.0]
  A quantum-classical (HQC) solution to the Unit Commitment (UC) problem is presented. The validity and computational viability of the proposed approach are demonstrated using the D-Wave Advantage 4.1 quantum annealer.
  arXiv  Detail & Related papers  (2021-12-10T16:16:09Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization. We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance. The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
  arXiv  Detail & Related papers  (2021-06-24T16:39:31Z)
• Joint Deep Reinforcement Learning and Unfolding: Beam Selection and Precoding for mmWave Multiuser MIMO with Lens Arrays [54.43962058166702]
  millimeter wave (mmWave) multiuser multiple-input multiple-output (MU-MIMO) systems with discrete lens arrays have received great attention. In this work, we investigate the joint design of a beam precoding matrix for mmWave MU-MIMO systems with DLA.
  arXiv  Detail & Related papers  (2021-01-05T03:55:04Z)

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.