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.
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.
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.
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.
This paper presents a new inspired algorithm called quantum inspired cuckoo search algorithm (QICSA). This one is a new framework relying on quantum computing principles and cuckoo search algorithm. The contribution consists in defining an appropriate representation scheme in the cuckoo search algorithm that allows applying successfully on combinatorial optimisation problems some quantum computing principles like qubit representation, superposition of states, measurement, and interference. This hybridisation between quantum inspired computing and bioinspired computing has led to an efficient hybrid framework which achieves better balance between exploration and exploitation capabilities of the search process. Experiments on knapsack problems show the effectiveness of the proposed framework and its ability to achieve good quality solutions.
The graph colouring problem (GCP) is one of the most interesting, studied and difficult combinatorial optimisation problems. That is why, several approaches were developed for solving this problem, including exact approaches, heuristic approaches, metaheuristics and hybrid approaches. In this paper, we try to solve the graph colouring problem using a new approach based on the quantum inspired cuckoo search algorithm. The first contribution consists in defining an appropriate quantum representation based on qubit representation to represent the graph colouring solutions. The second contribution is the proposition of a novel measure operator based on the adjacency matrix. The third contribution involves the proposition of an adapted hybrid quantum mutation operation. To show the feasibility and the effectiveness of the algorithm, we have used the standard DIMACS benchmark, and the obtained results are very encouraging.
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 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.