Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor
8 February 2024
M. Yassine Naghmouchi,
Wesley da Silva Coelho
Applies Benders decomposition, splitting MILP into master problem and subproblem
Solves master problem on neutral atom quantum computer after reformulating into QUBO
Implements register embedding heuristic and QAOA algorithm for pulse shaping
Proof of concept outperforms existing hybrid Benders decomposition solutions
Preliminary results show 95%+ feasible solutions of high quality on small MILP test cases
Neutral atom quantum computing for mixed integer linear programming
This paper presents a hybrid classical-quantum approach using neutral atom quantum computing to solve mixed integer linear programming (MILP) problems. It applies Benders decomposition to break the MILP into a master problem solved on the quantum device and a subproblem solved classically. A proof of concept shows it can outperform existing solutions. Preliminary results on small MILP test cases demonstrate the approach finds over 95% high quality feasible solutions, beating classical Benders decomposition with simulated annealing.
No comments yet, be the first to start the conversation...
Sign up to comment on this paper