Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem

Abstract

The Bin Packing Problem (BPP) stands out as a paradigmatic combinatorial optimization problem in logistics. Quantum and hybrid quantum-classical algorithms are expected to show an advantage over their classical counterparts in obtaining approximate solutions for optimization problems. We have recently proposed a hybrid approach to the one dimensional BPP in which a quantum annealing subroutine is employed to sample feasible solutions for single containers. From this reduced search space, a classical optimization subroutine can find the solution to the problem. With the aim of going a step further in the evaluation of our subroutine, in this paper we compare the performance of our procedure with other classical approaches. Concretely we test a random sampling and a random-walk-based heuristic. Employing a benchmark comprising 18 instances, we show that the quantum approach lacks the stagnation behaviour that slows down the classical algorithms. Based on this, we conclude that the quantum strategy can be employed jointly with the random walk to obtain a full sample of feasible solutions in fewer iterations. This work improves our intuition about the benefits of employing the scarce quantum resources to improve the results of a diminishingly efficient classical strategy.

8 pages, 2 figures, submitted to the IEEE Symposium Series On Computational Intelligence 2022

References in corpus (6)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A Quantum Approximate Optimization Algorithm
• Random Walks: A Review of Algorithms and Applications
• Quantum Neuronal Sensing of Quantum Many-Body States on a 61-Qubit Programmable Superconducting Processor
• Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks
• Hybrid Quantum-Classical Heuristic for the Bin Packing Problem

Cited by in corpus (5)

• Hybrid Approach for Solving Real-World Bin Packing Problem Instances Using Quantum Annealers
• QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems
• Solving Logistic-Oriented Bin Packing Problems Through a Hybrid Quantum-Classical Approach
• Formulation of the Electric Vehicle Charging and Routing Problem for a Hybrid Quantum-Classical Search Space Reduction Heuristic
• Digitized Counter-Diabatic Quantum Optimization for Bin Packing Problem