Mixed-integer linear programming solver using Benders decomposition assisted by a neutral-atom quantum processor
Physical Review A · 12.07.2024 · 110 (1)
DOI: 10.1103/physreva.110.012434 ↗Kurz gefasst
Fachartikel in der Zeitschrift Physical Review A, online erschienen am 12.07.2024. Verfasst von M. Yassine Naghmouchi und 1 weiteren Autor:innen. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 36 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Naghmouchi, M. Y., & Coelho, W. D. S. (2024). Mixed-integer linear programming solver using Benders decomposition assisted by a neutral-atom quantum processor. Physical Review A, 110(1). https://doi.org/10.1103/physreva.110.012434
Vancouver
Naghmouchi MY, Coelho WDS. Mixed-integer linear programming solver using Benders decomposition assisted by a neutral-atom quantum processor. Physical Review A. 2024;110(1). doi:10.1103/physreva.110.012434
BibTeX
@article{Naghmouchi2024,
author = {Naghmouchi, M. Yassine and Coelho, Wesley da Silva},
title = {Mixed-integer linear programming solver using Benders decomposition assisted by a neutral-atom quantum processor},
journal = {Physical Review A},
year = {2024},
volume = {110},
number = {1},
doi = {10.1103/physreva.110.012434}
}
EUVIMED