EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

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

Invited abstract in session MA-42: Hybrid Classical-Quantum Algorithms, stream Quantum Computing Optimization.

Monday, 8:30-10:00
Room: 98 (building: 306)

Authors (first author is the speaker)

1. Anna Joliot
Pasqal
2. Wesley Coelho
PASQAL
3. M. Yassine NAGHMOUCHI
PASQAL

Abstract

This work 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, where the MP is addressed using a neutral-atom device, after being transformed into a Quadratic Unconstrained Binary Optimization (QUBO) model. To solve the QUBO, we develop a heuristic for atom register embedding and apply Quantum Approximate Optimization Algorithm for pulse shaping. In addition, we implement a Proof of Concept that outperforms existing solutions. We also conduct preliminary numerical results, 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.
Looking to the future, our objective is to scale and diversify our instances. This presents difficulties related to the limits on the number of qubits and the convergence of the algorithm. To overcome resource limitations, one can set a maximum number of qubits and implement an iterative process that guarantees the quality of the solution. When facing issues with convergence, we can consider multi-cuts, which involves generating multiple solutions for the MP and selecting a specific subset of Benders cuts to not surcharge the MP.

Keywords

Status: accepted

Back to the list of papers