QAL-BP: An Augmented Lagrangian Quantum Approach for the Bin Packing Problem

Bin packing is one of the most studied NP-Hard problem in combinatorial optimization, but it still remains one of the hardest to solve. On the other hand, emerging quantum technologies have proven to have the potential to provide exponential speedup over classical computing, for certain classes of problems, including combinatorial optimization problems. In this work we present a novel heuristic QUBO formulation for the well known bin packing problem (BPP) based on the augmented Lagrangian method and an analytical estimation of penalty multipliers that makes the model more generalizable to different input instances. We tested our approach on a set of bin packing instances, by using a real quantum computer based on Quantum Annealing (QA). The experiments demonstrate that the proposed approach is capable of finding good quality solutions for small-sized instances of the BPP. The proposed approach is also compared with existing classical state-of-the-art algorithms for the BPP, and we show that it strongly outperforms them in terms of running time. This new approach paves the way to the research for a generalizable QUBO formulation for BPP and to the study of new QUBO formulations for other combinatorial problems with inequality constraints.