  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.
