QAL-BP: an augmented Lagrangian quantum approach for bin packing

Area of Science:

• Artificial Intelligence
• Quantum Computing
• Operations Research

Background:

• The bin packing problem is an NP-Hard combinatorial optimization challenge.
• Quantum computing offers potential for significant computational speedup in optimization tasks.

Purpose of the Study:

• To introduce QAL-BP, a novel QUBO formulation for bin packing suitable for quantum computation.
• To develop a versatile model that analytically estimates penalty multipliers, avoiding instance-dependent coefficients.

Main Methods:

• Developed QAL-BP, a Quadratic Unconstrained Binary Optimization (QUBO) formulation using the Augmented Lagrangian method.
• Incorporated bin packing constraints into the objective function.
• Estimated heuristic penalty multipliers analytically.
• Conducted experiments on a quantum annealing device and compared results with classical solvers (simulated annealing, Gurobi).

Main Results:

• The proposed QAL-BP formulation correctly models the bin packing problem.
• Quantum annealing demonstrated potential for effectively solving bin packing instances.
• The QAL-BP model proved versatile and generalizable, removing the need for empirical coefficient tuning.

Conclusions:

• The QAL-BP formulation is a viable quantum approach for the bin packing problem.
• Quantum computation holds promise for solving complex optimization problems as technology matures.
• The study validates the effectiveness of quantum annealing for combinatorial optimization tasks.