Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2204.05637 · Genetic and Evolutionary Computation Conference Companion (GECCO Companion)

Hybrid quantum-classical heuristic for the bin packing problem

Mikel Garcia de Andoin, Eneko Osaba, Izaskun Oregi, Esther Villar-Rodríguez, Mikel Sanz

Published Jul 9, 2022• 18 citations
arXivHTMLPDF

Abstract

Optimization problems is one of the most challenging applications of quantum computers, as well as one of the most relevants. As a consequence, it has attracted huge efforts to obtain a speedup over classical algorithms using quantum resources. Up to now, many problems of different nature have been addressed through the perspective of this revolutionary computation paradigm, but there are still many open questions. In this work, a hybrid classical-quantum approach is presented for dealing with the one-dimensional Bin Packing Problem (1dBPP). The algorithm comprises two modules, each one designed for being executed in different computational ecosystems. First, a quantum subroutine seeks a set of feasible bin configurations of the problem at hand. Secondly, a classical computation subroutine builds complete solutions to the problem from the subsets given by the quantum subroutine. Being a hybrid solver, we have called our method H-BPP. To test our algorithm, we have built 18 different 1dBPP instances as a benchmarking set, in which we analyse the fitness, the number of solutions and the performance of the QC subroutine. Based on these figures of merit we verify that H-BPP is a valid technique to address the 1dBPP.

DOI
10.1145/3520304.3533986

Related papers

Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem

Mikel Garcia de Andoin, Izaskun Oregi, Esther Villar-Rodríguez +2 more

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.

arXiv:2207.07460•IEEE Symposium Series on Computational Intelligence (SSCI)•Dec 4, 2022•12 citations

A Novel Quantum Inspired Cuckoo Search Algorithm for Bin Packing Problem

Abdesslem Layeb, Seriel Rayene Boussalia

The Bin Packing Problem (BPP) is one of the most known combinatorial optimization problems.This problem consists to pack a set of items into a minimum number of bins.There are several variants of this problem; the most basic problem is the onedimensional bin packing problem (1-BPP).In this paper, we present a new approach based on the quantum inspired cuckoo search algorithm to deal with the 1-BPP problem.The contribution consists in defining an appropriate quantum representation based on qubit representation to represent bin packing solutions.The second contribution is proposition of a new hybrid quantum measure operation which uses first fit heuristic to pack no filled objects by the standard measure operation.The obtained results are very encouraging and show the feasibility and effectiveness of the proposed approach.

International Journal of Information Technology and Computer Science•May 2, 2012•59 citations

Digitized counterdiabatic quantum optimization for bin packing problem

Ruoqian Xu, Sebastián V. Romero, Jialiang Tang +2 more

Abstract The bin packing problem (BPP), a classical NP-hard combinatorial optimization challenge, has emerged as a promising application for quantum computing. In this work, we tackle the one-dimensional BPP (1dBPP) using a digitized counterdiabatic quantum approximate optimization algorithm (DC-QAOA) that incorporates counterdiabatic (CD) driving to achieve a 40% higher feasibility ratio than standard QAOA, while reducing quantum resource requirements. We investigate three ansatz schemes -DC-QAOA, CD-inspired ansatz, and CD-mixer ansatz - each integrating CD terms with distinct combinations of cost and mixer Hamiltonians, resulting in different DC-QAOA variants. Numerical simulations demonstrate that these DC-QAOA variants maintain solution accuracy with less than 5% variance across varying iteration numbers, circuit depths, and Hamiltonian step sizes. Moreover, they require approximately 7 to 8 times fewer measurements to achieve comparable precision under the same parameter variations. Experimental validation on a 10-item 1dBPP instance using IBM quantum computers shows the CD-mixer ansatz achieves five times more feasibility solutions and greater robustness against NISQ noise. Collectively, these results establish DC-QAOA as a resource-efficient framework for combinatorial optimization on near-term quantum devices.

arXiv:2502.15375•EPJ Quantum Technology•Aug 11, 2025•1 citation

A novel greedy quantum inspired cuckoo search algorithm for variable sized bin packing problem

Abdesslem Layeb, Seriel Rayene Boussalia

Bin packing is a well-known NP-hard optimisation problem which has several real applications. Classical bin packing (BPP) is a simple model where all bins are identical. However, the variable sized bin packing problem (VSBPP) is a generalisation of the bin packing problem where bins of different capacities are available for packing a set of items having different weights. The objective is to pack all the items in the bins minimising the sum of the remaining spaces of the used bins. In this paper, we present a new approach based on the quantum inspired cuckoo search algorithm to deal with the variable sized bin packing problem (VSBPP) problem. The contribution consists in defining an appropriate quantum representation based on qubit representation to represent bin packing solutions. The second contribution is a proposition of a new hybrid quantum measure operation which uses first fit heuristic to pack no filled objects by the standard measure operation. The third contribution is the use of a new hybrid randomised heuristic based on both first fit and best heuristics. The obtained results are very encouraging and show the feasibility and effectiveness of the proposed approach.

International Journal of Mathematics in Operational Research•Jan 1, 2014•3 citations

Quantum solution for solving the Bin Packing problem

Samuel Deleplanque, Amélia Durbec, Amina El Yaagoubi

Quantum optimization shows significant potential in tackling complex combinatorial challenges, prompting our research exploration into the domain of quantum computing to address the Bin Packing Problem (BPP) through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work-in-progress paper outlines our proposal for a thorough study that encompasses classical bin packing formulations, initiating with the Mixed Integer Linear Program, followed by a comparative analysis of the corresponding QUBO representations, and adopting a structured approach of Quantum Annealing on the D-Wave machine. While our work is still in progress, continuous comparative analyses are being conducted to evaluate various QUBO formulations, derived from diverse classical bin packing models, aiming to identify the most efficient QUBO for addressing the BPP. On another front, efforts are dedicated to refining the solution process further, with a focus on enhancing the precision of the selected QUBO formulation.

International Conference on Control, Decision and Information Technologies (CoDIT)•Jul 1, 2024•1 citation

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

Lorenzo Cellini, Antonio Macaluso, Michele Lombardi

The bin packing is a well-known NP-Hard problem in the domain of artificial intelligence, posing significant challenges in finding efficient solutions. Conversely, recent advancements in quantum technologies have shown promising potential for achieving substantial computational speedup, particularly in certain problem classes, such as combinatorial optimization. In this study, we introduce QAL-BP, a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation designed specifically for bin packing and suitable for quantum computation. QAL-BP utilizes the Augmented Lagrangian method to incorporate the bin packing constraints into the objective function while also facilitating an analytical estimation of heuristic, but empirically robust, penalty multipliers. This approach leads to a more versatile and generalizable model that eliminates the need for empirically calculating instance-dependent Lagrangian coefficients, a requirement commonly encountered in alternative QUBO formulations for similar problems. To assess the effectiveness of our proposed approach, we conduct experiments on a set of bin packing instances using a real Quantum Annealing device. Additionally, we compare the results with those obtained from two different classical solvers, namely simulated annealing and Gurobi. The experimental findings not only confirm the correctness of the proposed formulation, but also demonstrate the potential of quantum computation in effectively solving the bin packing problem, particularly as more reliable quantum technology becomes available.

arXiv:2309.12678•Scientific Reports•Mar 1, 2024•17 citations
Optimization problems is one of the most challenging applications of quantum computers, as well as one of the most relevants. As a consequence, it has attracted huge efforts to obtain a speedup over classical algorithms using quantum resources. Up to now, many problems of different nature have been addressed through the perspective of this revolutionary computation paradigm, but there are still many open questions. In this work, a hybrid classical-quantum approach is presented for dealing with the one-dimensional Bin Packing Problem (1dBPP). The algorithm comprises two modules, each one designed for being executed in different computational ecosystems. First, a quantum subroutine seeks a set of feasible bin configurations of the problem at hand. Secondly, a classical computation subroutine builds complete solutions to the problem from the subsets given by the quantum subroutine. Being a hybrid solver, we have called our method H-BPP. To test our algorithm, we have built 18 different 1dBPP instances as a benchmarking set, in which we analyse the fitness, the number of solutions and the performance of the QC subroutine. Based on these figures of merit we verify that H-BPP is a valid technique to address the 1dBPP.
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.
The Bin Packing Problem (BPP) is one of the most known combinatorial optimization problems.This problem consists to pack a set of items into a minimum number of bins.There are several variants of this problem; the most basic problem is the onedimensional bin packing problem (1-BPP).In this paper, we present a new approach based on the quantum inspired cuckoo search algorithm to deal with the 1-BPP problem.The contribution consists in defining an appropriate quantum representation based on qubit representation to represent bin packing solutions.The second contribution is proposition of a new hybrid quantum measure operation which uses first fit heuristic to pack no filled objects by the standard measure operation.The obtained results are very encouraging and show the feasibility and effectiveness of the proposed approach.
Abstract The bin packing problem (BPP), a classical NP-hard combinatorial optimization challenge, has emerged as a promising application for quantum computing. In this work, we tackle the one-dimensional BPP (1dBPP) using a digitized counterdiabatic quantum approximate optimization algorithm (DC-QAOA) that incorporates counterdiabatic (CD) driving to achieve a 40% higher feasibility ratio than standard QAOA, while reducing quantum resource requirements. We investigate three ansatz schemes -DC-QAOA, CD-inspired ansatz, and CD-mixer ansatz - each integrating CD terms with distinct combinations of cost and mixer Hamiltonians, resulting in different DC-QAOA variants. Numerical simulations demonstrate that these DC-QAOA variants maintain solution accuracy with less than 5% variance across varying iteration numbers, circuit depths, and Hamiltonian step sizes. Moreover, they require approximately 7 to 8 times fewer measurements to achieve comparable precision under the same parameter variations. Experimental validation on a 10-item 1dBPP instance using IBM quantum computers shows the CD-mixer ansatz achieves five times more feasibility solutions and greater robustness against NISQ noise. Collectively, these results establish DC-QAOA as a resource-efficient framework for combinatorial optimization on near-term quantum devices.
Bin packing is a well-known NP-hard optimisation problem which has several real applications. Classical bin packing (BPP) is a simple model where all bins are identical. However, the variable sized bin packing problem (VSBPP) is a generalisation of the bin packing problem where bins of different capacities are available for packing a set of items having different weights. The objective is to pack all the items in the bins minimising the sum of the remaining spaces of the used bins. In this paper, we present a new approach based on the quantum inspired cuckoo search algorithm to deal with the variable sized bin packing problem (VSBPP) problem. The contribution consists in defining an appropriate quantum representation based on qubit representation to represent bin packing solutions. The second contribution is a proposition of a new hybrid quantum measure operation which uses first fit heuristic to pack no filled objects by the standard measure operation. The third contribution is the use of a new hybrid randomised heuristic based on both first fit and best heuristics. The obtained results are very encouraging and show the feasibility and effectiveness of the proposed approach.
Quantum optimization shows significant potential in tackling complex combinatorial challenges, prompting our research exploration into the domain of quantum computing to address the Bin Packing Problem (BPP) through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work-in-progress paper outlines our proposal for a thorough study that encompasses classical bin packing formulations, initiating with the Mixed Integer Linear Program, followed by a comparative analysis of the corresponding QUBO representations, and adopting a structured approach of Quantum Annealing on the D-Wave machine. While our work is still in progress, continuous comparative analyses are being conducted to evaluate various QUBO formulations, derived from diverse classical bin packing models, aiming to identify the most efficient QUBO for addressing the BPP. On another front, efforts are dedicated to refining the solution process further, with a focus on enhancing the precision of the selected QUBO formulation.
The bin packing is a well-known NP-Hard problem in the domain of artificial intelligence, posing significant challenges in finding efficient solutions. Conversely, recent advancements in quantum technologies have shown promising potential for achieving substantial computational speedup, particularly in certain problem classes, such as combinatorial optimization. In this study, we introduce QAL-BP, a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation designed specifically for bin packing and suitable for quantum computation. QAL-BP utilizes the Augmented Lagrangian method to incorporate the bin packing constraints into the objective function while also facilitating an analytical estimation of heuristic, but empirically robust, penalty multipliers. This approach leads to a more versatile and generalizable model that eliminates the need for empirically calculating instance-dependent Lagrangian coefficients, a requirement commonly encountered in alternative QUBO formulations for similar problems. To assess the effectiveness of our proposed approach, we conduct experiments on a set of bin packing instances using a real Quantum Annealing device. Additionally, we compare the results with those obtained from two different classical solvers, namely simulated annealing and Gurobi. The experimental findings not only confirm the correctness of the proposed formulation, but also demonstrate the potential of quantum computation in effectively solving the bin packing problem, particularly as more reliable quantum technology becomes available.