# Hybrid Approach for Solving Real-World Bin Packing Problem Instances Using
Quantum Annealers

Sebastián V. Romero  TECNALIA, Basque Research and Technology Alliance (BRTA),
48160 Derio, Spain  0000-0002-4675-4452 Eneko Osaba  TECNALIA, Basque Research
and Technology Alliance (BRTA), 48160 Derio, Spain<EMAIL_ADDRESS>0000-0001-7863-9910 Esther Villar-Rodriguez  TECNALIA, Basque Research and
Technology Alliance (BRTA), 48160 Derio, Spain  0000-0003-3343-3737 Izaskun
Oregi  TECNALIA, Basque Research and Technology Alliance (BRTA), 48160 Derio,
Spain  EUNEIZ, 01013 Vitoria-Gasteiz, Spain  0000-0002-3950-1668 Yue Ban
TECNALIA, Basque Research and Technology Alliance (BRTA), 48160 Derio, Spain
0000-0003-1764-4470

###### Abstract

Efficient packing of items into bins is a common daily task. Known as Bin
Packing Problem, it has been intensively studied in the field of artificial
intelligence, thanks to the wide interest from industry and logistics. Since
decades, many variants have been proposed, with the three-dimensional Bin
Packing Problem as the closest one to real-world use cases. We introduce a
hybrid quantum-classical framework for solving real-world three-dimensional
Bin Packing Problems (Q4RealBPP), considering different realistic
characteristics, such as: i) package and bin dimensions, ii) overweight
restrictions, iii) affinities among item categories and iv) preferences for
item ordering. Q4RealBPP permits the solving of real-world oriented instances
of 3dBPP, contemplating restrictions well appreciated by industrial and
logistics sectors.

###### keywords:

3dBPP, Bin Packing Problem, Logistics, Optimization, Quantum Computing,
Quantum Annealer, D-Wave

## Introduction

Introduction

The optimization on the packaging of products into a finite number of
containers is a crucial daily task in the field of production and
distribution. Depending on the characteristics of both packages and
containers, multiple packaging problems can be formulated, generally known as
Bin Packing Problems (BPP) [1]. Within this category, the one-dimensional BPP
(1dBPP) is considered as the simplest one [2], whose goal is to pack all items
into as few containers as possible. Many variants with a variable number of
constraints have been proposed to deal with real situations in logistics and
industry [3]. The three-dimensional BPP (3dBPP)[4], in which each package has
three dimensions: height, width and depth, is the best-known and the most
challenging variant. Highlighted in several studies[5, 6, 7], 3dBPP has a
practical interest in many industrial settings. In recent years, it has been
formulated to possess diverse and practical applications such as pallet
loading [8], road transportation [9], air cargo [10], etc. Due to its
complexity, 3dBPP is also recurrently employed as a benchmark for testing
newly developed methods and mechanisms [11, 12].

On another front, quantum computing is still at its early stage but has
gathered a lot of attention from the scientific community as it offers
researchers and practitioners a revolutionary paradigm for tackling different
kinds of practical optimization problems [13, 14, 15, 16]. In particular,
quantum annealers have been recently applied to a wide variety of optimization
problems inspired by the fields from industry [17], logistics [18] and
economics [19]. However, the research on BPP carried out in the quantum
community is still scarce, even though BPP has been widely studied classically
as an optimization problem.

The pioneering work on BPP in the field of quantum computing presents a hybrid
quantum-classical method for solving the 1dBPP [20], whose solver is composed
of two modules: i) a quantum subroutine with which to search a set of feasible
configurations to fill one single bin and ii) a classical computational
heuristic which builds complete solutions employing the subsets given by the
quantum subroutine. To deepen the performance of the quantum subroutine
developed, further tests were conducted against a random sampling and a random
walk-based heuristic[21]. Besides those two papers, an additional study
formulates an atomic energy industry related problem as a 1dBPP, solving it
using the D-Wave quantum annealer[22]. Another works show quantum-inspired
evolutionary computation techniques as an alternative to tackle BPP related
problems [23, 24, 25]. Quantum-inspired techniques are a specific class of
evolutionary algorithms which make use of quantum physics to define their
operations and are designed to be executed on a classical computer[26]. Thus,
they can not be executed on any quantum machine.

In contrast to 1dBPP, tackling 3dBPP in the quantum domain is much more
challenging due to two related grounds: i) its complexity, which increases as
constraints from the real-world are taken into account and ii) the incipient
state of development of the current commercial quantum computers with
capacities still limited by decoherence and errors, which could be an obstacle
to solve highly-constrained problems. In this paper, we present a hybrid
quantum-classical computing framework for the real-world oriented 3dBPP, which
is coined as Quantum for Real Bin Packing Problem (Q4RealBPP). The proposed
framework resorts to the the Leap Constrained Quadratic Model (CQM) Hybrid
Solver (LeapCQMHybrid[27]) of D-Wave. At the same time, Q4RealBPP is built on
an existing code[28]. This reference code is an excellent starting point,
which paved the way for these two main contributions developed in this this
work.

  * •

Efficiency of the code: in the reference code, the problem is formulated such
that lots of variables (thus qubits) are needed. This issue meets the problem
of feasibility in the context of quantum hardware in the noisy intermediate-
scale quantum (NISQ) era[29]. Therefore, the optimization of the code is
crucial for dealing with complex problems. Q4RealBPP provides a step forward
on this aspect by exploring how the constraints coined as Intrinsic
restrictions can be polished. These restrictions are the ones needed for the
BPP definition (e.g. do not place cases outside a bin), and they were
previously introduced in the reference code. Thus, the novel work performed on
this specific facet has involved, among others, the redefinition of some
mathematical formulas that define these intrinsic restrictions, and the
elimination of a redundant optimization objective. Thanks to this procedure,
problems can be formulated by using fewer variables, which directly impacts
the capacity of the framework to address larger instances.

  * •

Applicability of the tool: the reference code is oriented toward solving the
most basic variant of the 3dBPP by only considering the dimension of both
packages and bins. This setting falls far from real client demands, where
other features such as weights, load balancing or incompatibilities,among
others, are likely to take part. We have elaborated on this direction by
implementing a set of constraints named Real-World BPP Restrictions. All these
constraints represent an added value for Q4RealBPP, having required a
significant extension of the mathematical formulation of the problem. We
deepen in this aspect in following sections.

Taking these factors into account, Q4RealBPP is oriented to industrial and
logistics related fields, contemplating problems such as the organization of
port containers, the introduction of packages in delivery vans and trucks or
the placement of foodstuffs on distribution pallets, among others. With the
aid of a hybrid quantum-classical method, Q4RealBPP represents a solid step
forward to solve 3dBPP with the clear purpose of facing real-world focused
problems well appreciated by final users and companies. Features contemplated
by Q4RealBPP involve i) dimensions of packages and bins, ii) maximum weight
allowed per bin, iii) positive and negative affinities among item categories
and iv) preferences for package ordering (in terms of load bearing and load
balancing). To demonstrate its application, we have conducted an
experimentation composed of 12 different instances serving as illustrative
examples. Additionally, Q4RealBPP allows users to easily build flexible and
well-defined instances to adapt a plethora of real-world situations to be
solved in the quantum computer.

The rest of the article is organized as follows: in Mathematical formulation
the 3dBPP formulation and its corresponding notation are presented. Moreover,
a detailed study of the computational resources needed for arbitrary instances
is carried out. In Experimental results, the applicability of this tool is
tested using a set of realistic instances as input. Finally, the conclusions
led by the presented results and our future plans are given in Conclusions and
future work.

## Mathematical formulation

Mathematical formulation

In this section, we describe in detail the mathematical formulation of the
3dBPP variant tackled in this research. First, input parameters and variables
that compose the problem are shown in Table 1.

Parameters |
---|---
$I,J,K_{i},Q$ |  sets of items, bins, orientations of $i$-th item (see Figure 1) and relative positions between items (see Figure 2).
$m,n$ |  number of items and bins.
$l_{i},w_{i},h_{i},\mu_{i}$ |  length, width, height and weight of item $i\in I$.
$L,W,H,M$ |  length, width, height and maximum capacity (optional) of bins.
$A^{\text{pos}},A^{\text{neg}}$ |  sets of positive and negative affinities (incompatibilities) between items of type $\alpha$ and $\beta$ (optional).
$\eta$ |  maximum mass ratio between two items where one is placed at the top of the other with $\eta>1$ (optional).
$(\tilde{L},\tilde{W})$ |  target center of mass of the resultant packings (optional).
Variables |
$v_{j}$ |  binary variable that represents if bin $j\in J$ is used.
$u_{i,j}$ |  binary variable that represents if item $i$ is added to bin $j$.
$r_{i,k}$ |  binary variable that represents if the orientation $k\in K_{i}$ is applied to the item $i$. They are used to compute the effective length, width and height $(x^{\prime}_{i},y^{\prime}_{i},z^{\prime}_{i})$ of the $i$-th item (see (6)-(8)).
$x_{i},y_{i},z_{i}$ |  continuous variables that return the location of the back lower left corner of item $i$ along $x$, $y$ and $z$ axes.
$\tilde{x}_{i},\tilde{y}_{i}$ |  continuous variables that account the relative distance between item $i$ and $(\tilde{L},\tilde{W})$ along $x$ and $y$ axes. Both are used if $(\tilde{L},\tilde{W})$ is defined previously.
$b_{i,k,q}$ |  binary variable that returns the relative position $q\in Q$ between items $i,k\in I$. See Figure 2.
Table 1: Parameters and variables used in our formulation.

### Objectives

Objectives

The 3dBPP can be solved as an optimization problem where a suitable cost
function to minimize must be defined. In our case, this cost function is
represented as the sum of three objectives. The strength given to each
objective, i.e. the relevance accounted for each one, is up to the user
preferences just by multiplying each objective with a suitable weight. Thus,
the problem can be stated as $\min\text{ }\sum_{i=1}^{3}\omega_{i}o_{i}$ with
$\omega_{i}$ the weights of each objective $o_{i}$. In our study we will not
consider this bias, i.e. $\omega_{i}=1\text{ }\forall i$.

The first and main objective minimizes the total amount of bins used to locate
the packages. This can be achieved by minimizing

$o_{1}=\sum_{j=1}^{n}v_{j}.$ (1)

Additionally, for ensuring that items are packed from the floor to the top of
the bin, avoiding solutions with floating packages, a second objective is
defined by minimizing the average height of the items for all bins

$o_{2}=\frac{1}{mH}\sum_{i=1}^{m}\left(z_{i}+z^{\prime}_{i}\right).$ (2)

Besides these two objectives reformulated from the reference code[28], we
further add a third optional objective $o_{3}$ to take into account the load
balancing feature. This concern is particularly important when air cargo
planes and sailings are the chosen conveyance[30, 31], for example. In those
situations, packages should be uniformly distributed around a given
$xy$-coordinate inside the bin. We can tackle this by computing the so-called
taxicab or Manhattan distance between items and the desired center of mass for
each bin. As a result, the gaps between items are also reduced. Concerning
this, the third objective to be minimized is

$o_{3}=\frac{1}{m}\left(\frac{1}{L}\sum_{i=1}^{m}\tilde{x}_{i}+\frac{1}{W}\sum_{i=1}^{m}\tilde{y}_{i}\right),$
(3)

with

$\tilde{x}_{i}\coloneqq\left|\left(x_{i}+\frac{x_{i}^{\prime}}{2}\right)\\!\text{
mod
}L-\tilde{L}\right|\quad\text{and}\quad\tilde{y}_{i}\coloneqq\left|y_{i}+\frac{y_{i}^{\prime}}{2}-\tilde{W}\right|\quad\forall
i\in I,$ (4)

where $0\leq x_{i}<nL$ (bins stacked horizontally) and $0\leq y_{i}<W$
$\forall i\in I$. This objective term minimizes for each item the distance
between the center of mass projection in the $xy$-plane and the
$(\tilde{L},\tilde{W})$ coordinate of each bin.

The objectives above defined are subject to certain restrictions, which are
essential to derive realistic solutions. The whole pool of constraints is
separated into two categories: the ones intrinsic to the BPP definition
(Intrinsic restrictions), and the ones relevant from a real-world perspective
(Real-world BPP restrictions).

### Intrinsic restrictions

Intrinsic restrictions

Item orientations: the fact that inside a bin each item must have only one
orientation can be implemented by using

$\sum_{k\in K_{i}}r_{i,k}=1\quad\forall i\in I.$ (5)

Figure 1: Set of possible orientations $k\in K_{i}$ for a given item $i$ of
dimensions $(l_{i},w_{i},h_{i})$. (a) $k=1$, (b) $k=2$, (c) $k=3$, (d) $k=4$,
(e) $k=5$, (f) $k=6$. See Table 2.

Orientations give rise to the effective length, width, and height of the items
along $x$, $y$ and $z$ axes

$\displaystyle
x^{\prime}_{i}=l_{i}r_{i,1}+l_{i}r_{i,2}+w_{i}r_{i,3}+w_{i}r_{i,4}+h_{i}r_{i,5}+h_{i}r_{i,6}\quad\forall
i\in I,$ (6) $\displaystyle
y^{\prime}_{i}=w_{i}r_{i,1}+h_{i}r_{i,2}+l_{i}r_{i,3}+h_{i}r_{i,4}+l_{i}r_{i,5}+w_{i}r_{i,6}\quad\forall
i\in I,$ (7) $\displaystyle
z^{\prime}_{i}=h_{i}r_{i,1}+w_{i}r_{i,2}+h_{i}r_{i,3}+l_{i}r_{i,4}+w_{i}r_{i,5}+l_{i}r_{i,6}\quad\forall
i\in I,$ (8)

and because of (5), only one term $r_{i,k}$ is nonzero in each equation.

It should be deemed that there could be items with geometrical symmetries, as
with cubic ones where rotations do not apply. Redundant and non-redundant
orientations are considered in the reference code[28]. In our formulation, we
previously check if these symmetries exist to define $K_{i}$ for each item.
Thanks to this, (6)-(8) are simplified filtering out redundant orientations
and leading to a formulation which uses less variables (thus qubits) to
represent the same problem, where $\kappa=\sum_{i=1}^{m}|K_{i}|\leq 6m$
variables $r_{i,k}$ are needed. For $i\in I_{\text{c}}$ with
$I_{\text{c}}\coloneqq\\{i\in I\,|\,l_{i}=w_{i}=h_{i}\\}$ (cubic items), we
can set $r_{i,1}=1$ and $0$ otherwise, thus satisfying (5) in advance. In
Table 2, we can see the non-redundant orientation sets for an item $i$
depending on its dimensions. This simple mechanism reduces the complexity of
the problem, being favourable for the quantum hardware to implement.

Condition | $l_{i}=w_{i}=h_{i}$ | $w_{i}=h_{i}\neq l_{i}$ | $l_{i}=h_{i}\neq w_{i}$ | $l_{i}=w_{i}\neq h_{i}$ | $l_{i}\neq w_{i}\neq h_{i}$
---|---|---|---|---|---
$K_{i}$ | $\varnothing$ | $\\{1,3,4\\}$ | $\\{1,2,3\\}$ | $\\{1,2,5\\}$ | $\\{1,2,3,4,5,6\\}$
Table 2: Subsets of non-redundant orientations for item $i$ for a satisfied
condition following (6)-(8).

Non-overlapping restrictions: since we are considering rigid packages, i.e.
they can not overlap, a set of restrictions need to be defined to overcome
these configurations. For this purpose, at least one of these situations must
occur (see Figure 2)

Item $i$ is at the left of item $k$ ($q=1$):
$\displaystyle-(2-u_{i,j}u_{k,j}-b_{i,k,1})nL+x_{i}+x^{\prime}_{i}-x_{k}\leq
0$ $\displaystyle\forall i,k\in I,\text{ }\forall j\in J,$ (9) Item $i$ is
behind item $k$ ($q=2$):
$\displaystyle-(2-u_{i,j}u_{k,j}-b_{i,k,2})W+y_{i}+y^{\prime}_{i}-y_{k}\leq 0$
$\displaystyle\forall i,k\in I,\text{ }\forall j\in J,$ (10) Item $i$ is below
item $k$ ($q=3$):
$\displaystyle-(2-u_{i,j}u_{k,j}-b_{i,k,3})H+z_{i}+z^{\prime}_{i}-z_{k}\leq 0$
$\displaystyle\forall i,k\in I,\text{ }\forall j\in J,$ (11) Item $i$ is at
the right of item $k$ ($q=4$):
$\displaystyle-(2-u_{i,j}u_{k,j}-b_{i,k,4})nL+x_{k}+x^{\prime}_{k}-x_{i}\leq
0$ $\displaystyle\forall i,k\in I,\text{ }\forall j\in J,$ (12) Item $i$ is in
front of item $k$ ($q=5$):
$\displaystyle-(2-u_{i,j}u_{k,j}-b_{i,k,5})W+y_{k}+y^{\prime}_{k}-y_{i}\leq 0$
$\displaystyle\forall i,k\in I,\text{ }\forall j\in J,$ (13) Item $i$ is above
item $k$ ($q=6$):
$\displaystyle-(2-u_{i,j}u_{k,j}-b_{i,k,6})H+z_{k}+z^{\prime}_{k}-z_{i}\leq 0$
$\displaystyle\forall i,k\in I,\text{ }\forall j\in J.$ (14)

As discussed with the orientation variable $r_{i,k}$ in (5), the relative
position between items $i$ and $k$ must be unique, so

$\sum_{q\in Q}b_{i,k,q}=1\quad\forall i,k\in I.$ (15)

Figure 2: Representation of $b_{i,k,q}$ activated for all relative positions
$q\in Q$ between items $i$ and $k$. See (9)-(14). Both are in contact but it
is not mandatory. (a) $b_{{i},{k},1}=1$, (b) $b_{{i},{k},2}=1$, (c)
$b_{{i},{k},3}=1$, (d) $b_{{i},{k},4}=1$, (e) $b_{{i},{k},5}=1$, (f)
$b_{{i},{k},6}=1$.

Item and container allocation restrictions: the following set of restrictions
guarantees an appropriate behaviour during item and bin assignment. In order
to avoid packing duplicates of the same item, each item must go to exactly one
bin, where

$\sum_{j=1}^{n}u_{i,j}=1\quad\forall i\in I.$ (16)

The following formula verifies if items are being packed inside bins that are
already in use

$\sum_{i=1}^{m}(1-v_{j})u_{i,j}\leq 0\quad\forall j\in J,$ (17)

so it activates $v_{j}$ if needed during packaging. Bins can be activated
sequentially to avoid duplicated solutions ensuring that

$v_{j}\geq v_{j+1}\quad\forall j\in J\text{ }|\text{ }j\neq n.$ (18)

Bin boundary constraints: in order to contemplate bin boundaries, the
following set of restrictions must be met

$x_{i}+x^{\prime}_{i}-jL\leq(1-u_{i,j})nL\quad\hfill\forall i\in I,\text{
}\forall j\in J,$ (19) $x_{i}-(j-1)Lu_{i,j}\geq 0\quad\hfill\forall i\in
I,\text{ }\forall j\in J\text{ }|\text{ }j>1,$ (20)
$y_{i}+y^{\prime}_{i}-W\leq(1-u_{i,j})W\quad\hfill\forall i\in I,\text{
}\forall j\in J,$ (21)
$z_{i}+z^{\prime}_{i}-H\leq(1-u_{i,j})H\quad\hfill\forall i\in I,\text{
}\forall j\in J,$ (22)

where (19) guarantees that items $i$ placed inside the bin $j$ are not outside
of the last bin ($n$-th bin) along the $x$ axis, (20) ensures that item $i$ is
located inside of its corresponding bin $j$ along the $x$ axis (activated if
$n>1$), (21) confirms that item $i$ placed inside the bin $j$ is not outside
along the $y$ axis, while (22) ensures that item $i$ allocated inside the bin
$j$ is not outside along the $z$ axis.

### Real-world BPP restrictions

Real-world BPP restrictions

In this subsection we introduce those restrictions related with the operative
perspective of the problem, i.e. the ones that consider real-world industrial
situations. All of the following constraints are optional in our formulation.

Overweight restriction: the weight of each package and the maximum capacity of
containers are common contextual data to avoid exceeding the maximum weight
capacity of bins, so avoid overloaded containers. We can introduce this
restriction as

$\sum_{i=1}^{m}\mu_{i}u_{i,j}\leq M\quad\forall j\in J.$ (23)

This restriction is activated if the maximum capacity $M$ is given.

Affinities among package categories: there are commonly preferences for
separating some packages into different bins (negative affinities or
incompatibilities) or, on the contrary, gathering them into the same container
(positive affinities). Let us consider $I_{\alpha}\coloneqq\\{i\in I\text{
}|\text{ }\texttt{id}\text{ of }i\text{ is equal to }\alpha\\}$, i.e.
$I_{\alpha}\subset I$ is a subset of all items labelled with id equal to
$\alpha$. Given a set of $p$ negative affinities
$A^{\text{neg}}\coloneqq\\{(\alpha_{1},\beta_{1}),\dots,(\alpha_{p},\beta_{p})\\}$,
then the restriction will be

$\sum_{(\alpha,\beta)\in A^{\text{neg}}}\,\sum_{(i_{\alpha},i_{\beta})\in
I_{\alpha}\times I_{\beta}}\,\sum_{j=1}^{n}u_{i_{\alpha},j}u_{i_{\beta},j}=0,$
(24)

To activate this restriction, a set of incompatibilities must be given.
Moreover, we can satisfy in advance $\nu\coloneqq 6n\sum_{(\alpha,\beta)\in
A^{\text{neg}}}|I_{\alpha}||I_{\beta}|$ non-overlapping constraints (see
(9)-(14)), leading to a simpler formulation. Conversely, given a set of
positive affinities $A^{-}$ $A^{\text{pos}}$ as stated with $A^{\text{neg}}$,
then the restriction will be posed such that

$\sum_{(\alpha,\beta)\in A^{\text{pos}}}\,\sum_{(i_{\alpha},i_{\beta})\in
I_{\alpha}\times
I_{\beta}}\,\sum_{j=1}^{n}\left(1-u_{i_{\alpha},j}u_{i_{\beta},j}\right)=0,$
(25)

This restriction is activated if a set of positive affinities is given. If
$A^{\text{pos}}$ and $A^{\text{neg}}$ are given, then both restrictions can be
introduced using just one formula adding (24) and (25).

Preferences in relative positioning: relative positioning of items demands
that some of them must be placed in a specific position with respect other
existing items. This preference allows introducing the ordering of a set of
packages according to their positions with respect to the axes. Thus, this
preference assists in ordering for many real cases such as: parcel delivery
(an item $i$ that has to be delivered before item $k$ will be preferably
placed closer to the trunk door) or load bearing (no heavy package should rest
over flimsy packages), among others.

Regarding this preference, we can define two different perspectives to treat
relative positioning:

  * •

Positioning to avoid ($P_{q}^{-}$): list of items $(i,k)$ should not be in the
relative position $q\in Q$ specified. So, $b_{i,k,q}=0$ is expected, favouring
configurations where the solver selects $q^{\prime}\in Q$ with $q^{\prime}\neq
q$ for the relative positioning of items $(i,k)$.

  * •

Positioning to favour ($P_{q}^{+}$): list of items $(i,k)$ should be in a
certain relative position $q$. Activated this preference, $b_{i,k,q}=1$ ought
to hold and consequently, $b_{i,k,q^{\prime}}=0\ \forall q^{\prime}\neq q$.

Formally, these preferences are written as

$P_{q}^{-}\coloneqq\\{(i,k)\in I^{2}\text{ }|\text{ }i<k\text{ and
}b_{i,k,q}=0\\}\quad\text{and}\quad P_{q}^{+}\coloneqq\\{(i,k)\in I^{2}\text{
}|\text{ }i<k\text{ and }b_{i,k,q}=1\\}.$ (26)

These preferences could be also treated as compulsory pre-selections. In such
case, the number of variables needed would be reduced, so would the search
space. If we let $\smash[t]{p^{-}=\sum_{q\in Q}|P_{q}^{-}|}$ and
$\smash[t]{p^{+}=\sum_{q\in Q}|P_{q}^{+}|}$ with $\smash[t]{P^{-}_{q}\cap
P^{+}_{q^{\prime}}=\varnothing}$, based on (15), the amount of variables
reduced would be given by $\smash[t]{p^{-}+6p^{+}}$. Moreover,
$\smash[t]{n(p^{-}+5p^{+})}$ non-overlapping constraints (see (9)-(14)) are
satisfied directly and can be ignored, thus simplifying the problem. In this
paper, for the sake of clarity, these preferences have been applied for load
bearing purposes as hard constraints (HC), as explained in the upcoming
Experimental results.

Load balancing: to activate this restriction, a target center of mass must be
given. Global positions with respect to the bin as a whole (as described in
objective $o_{3}$ in (3)), are fixed using the following constraints

$\pm\frac{1}{n}\sum_{j=1}^{n}\left[x_{i}+\frac{x_{i}^{\prime}}{2}-n(j-1)u_{i,j}L-\tilde{L}\right]\leq\tilde{x}_{i}\quad\text{and}\quad\pm\left(y_{i}+\frac{y_{i}^{\prime}}{2}-\tilde{W}\right)\leq\tilde{y}_{i}\quad\forall
i\in I.$ (27)

This feature is represented in Figure 3 for $(\tilde{L},\tilde{W})=(L/2,W/2)$,
whose red line shows the available $\tilde{x}_{i}$ and $\tilde{y}_{i}$ values
(see (4)).

Figure 3: Representation of available $\tilde{x}_{i}$ and $\tilde{y}_{i}$
values ensured by the constraints given in (27) for
$(\tilde{L},\tilde{W})=(L/2,W/2)$.

### Complexity of the problem

Complexity of the problem

Regarding the complexity of the 3dBPP proposed in this research, the total
amount of variables needed to tackle an arbitrary instance is given in Table
3, where our formulation scales as $\mathcal{O}[m^{2}+nm]$ in terms of
variables. Additionally, the total amount of constraints required is provided
in Table 4, whose quantity grows quadratically as $\mathcal{O}[m^{2}+nm]$.

Mandatory | $n$ | $x_{i},y_{i},z_{i}$ | $u_{i,j}$ | $v_{j}$ | $r_{i,k}$ | $b_{i,k,q}$ | Binary | Continuous
---|---|---|---|---|---|---|---|---
$1$ | $3m$ | - | - | $\kappa$ | $6\binom{m}{2}$ | $6\binom{m}{2}+\kappa$ | $3m$
$\geq 2$ | $3m$ | $nm$ | $n$ | $\kappa$ | $6\binom{m}{2}$ | $6\binom{m}{2}+n(m+1)+\kappa$ | $3m$

Optional | $n$ | $\tilde{x}_{i},\tilde{y}_{i}$ | (26) as HC | Binary | Continuous
---|---|---|---|---|---
$1$ | $2m$ | $-p^{-}-6p^{+}$ | $-p^{-}-6p^{+}$ | $2m$
$\geq 2$ | $2m$ | $-p^{-}-6p^{+}$ | $-p^{-}-6p^{+}$ | $2m$

Table 3: Amount of mandatory (related to Intrinsic restrictions) and optional
(related to Real-world BPP restrictions) used variables depending on the
number of items and bins. See Table 1.

Mandatory | $n$ | (5) | (9)-(15) | (16)-(18) | (19)-(22) | Quadratic | Linear
---|---|---|---|---|---|---|---
$1$ | $m-|I_{\text{c}}|$ | $7\binom{m}{2}$ | - | $3m$ | - | $7\binom{m}{2}+4m-|I_{\text{c}}|$
$\geq 2$ | $m-|I_{\text{c}}|$ | $(6n+1)\binom{m}{2}$ | $2n+m-1$ | $(4n-1)m$ | $6n\binom{m}{2}+n$ | $\binom{m}{2}+n(4m+1)+m-1-|I_{\text{c}}|$

Optional | $n$ | (23) | (24)/(25) | (26) as HC | (27) | Quadratic | Linear
---|---|---|---|---|---|---|---
$1$ | - | - | $-p^{-}-5p^{+}$ | $4m$ | - | $-p^{-}-5p^{+}+4m$
$\geq 2$ | $n$ | $1$ | $-n(p^{-}+5p^{+})-\nu$ | $4m$ | $1-n(p^{-}+5p^{+})-\nu$ | $n+4m$

Table 4: Amount of mandatory (related to Intrinsic restrictions) and optional
(related to Real-world BPP restrictions) considered constraints depending on
the number of items and bins.

## Experimental results

Experimental results

In this section, we conduct an experimentation to demonstrate the
applicability of Q4RealBPP, where the problem has been modelled as a CQM and
then solved by the LeapCQMHybrid provided by D-Wave[27]. Initially, it should
be made clear that CQM refers to the mathematical model that uses quadratic
objective functions and quadratic constraints on binary and integer variables.
As this concept was introduced by D-Wave Systems, this company developed the
hybrid solver LeapCQMHybrid, which also supports the definition of equality
and inequality requirements. This feature brings an advantage compared to
Quadratic Unconstrained Binary Optimization (QUBO), which is the native
formulation for the QPUs. The CQM model and the LeapCQMHybrid introduce some
interesting shortcuts for a more friendly use, allowing the user to provide a
problem in a more intuitive and descriptive way, avoiding the translation into
a mathematical formulation in the shape of a QUBO matrix.

More specifically, the LeapCQMHybrid workflow is as follows: first, a
classical front end receives the CQM formulation of the problem as input.
Then, it runs a number of parallel computation threads, where each of them are
composed of two parts: a heuristic module (HM) and a quantum module (QM). On
the one hand, HM tries to solve the problem by using a state of the art
heuristic solver. On the other hand, QM aids this resolution by formulating
different quantum queries aiming to guide the HM toward promising regions of
the search space, or finding improvements to already existing solutions. This
QM performs its operations by acceding the latest available quantum computer
of D-Wave. At the time of writing this paper, the most updated architecture is
the Advantage_system, composed of 5616 qubits organized in a Pegasus topology.
For more information, we refer interested readers to the related report
provided by D-Wave [32].

Having said that, for demonstrating the applicability of Q4RealBPP, we have
built an ad-hoc benchmark composed of 12 different instances of the 3dBPP. In
order to analyze the impact of every restriction deeply, each instance is
devoted to evaluate a specific feature of the problem. Also, we have generated
two specific instances that bring together all the restrictions of our
modelled 3dBPP. We describe in Table 5 the main characteristics of the 12 used
instances.

Instance | OW | PA | INC | LB | CM | Variables | Constraints
---|---|---|---|---|---|---|---
3dBPP_1 (51) | Fig. 4(b) |  |  |  |  |  | 8085 | 9129
3dBPP_2 (51) | Fig. 4(c) | ✓ |  |  |  |  | 8189 | 17039
3dBPP_3 (52) | Fig. 4(d) |  |  |  |  |  | 8406 | 9490
3dBPP_4 (52) | Fig. 4(e) |  |  |  | ✓ |  | 7925 | 9009
3dBPP_5 (53) | Fig. 4(f) |  |  |  |  |  | 8745 | 9858
3dBPP_6 (53) | Fig. 4(g) |  |  | ✓ |  |  | 8853 | 17555
3dBPP_7 (46) | Fig. 4(h) |  |  |  |  |  | 6624 | 7429
3dBPP_8 (46) | Fig. 4(i) |  | ✓ | ✓ |  |  | 6718 | 13585
3dBPP_9 (47) | Fig. 4(j) |  |  |  |  | ✓ | 7003 | 7943
3dBPP_10 (51) | Fig. 4(k) |  |  |  |  | ✓ | 8211 | 9333
3dBPP_11 (38) | Fig. 4(l) | ✓ | ✓ | ✓ | ✓ | ✓ | 4417 | 8805
3dBPP_12 (38) | Fig. 4(m) | ✓ | ✓ | ✓ | ✓ | ✓ | 4453 | 8973
Table 5: Brief description of the real-world oriented restrictions activated
and the amount of variables and constraints used for each instance (see Tables
3 and 4). In brackets, number of items considered. Here, OW: overweight, PA:
positive affinities, INC: incompatibilities, LB: load bearing, CM: center of
mass.

The whole dataset has been generated employing an own-developed Python script
(coined as Q4RealBPP-DataGen). In order this paper to be as self-contained as
possible, we briefly explain how Q4RealBPP-DataGen works. This script performs
two steps to generate Q4RealBPP-compliant instances: firstly Q4RealBPP-DataGen
randomly generates a defined number of items, following the package
distribution and dimensions established in Ref.[8]. Then, the attributes
regarding overweight restriction, affinities among item categories, load
bearing and load balancing are completed by means of Q4RealBPP-DataGen. These
constraints are randomly configured by the generator, except for the last two
(load bearing and load balancing). These last features, as well as the bin
dimensions, have been empirically set, in the search of a realistic scenario.
It should be clarified that Q4RealBPP is a flexible framework, letting users
to build their own setting not only configuring the instance of the problem
but also by activating or deactivating the real-world oriented restrictions.
For more information, the complete benchmark of instances and Q4RealBPP-
DataGen are openly available in [33]. Furthermore, a deep explanation about
how the dataset has been generated as well as the format of each instances is
provided in [34].

In our specific use case, the preferences in relative positioning (see Real-
world BPP restrictions) are tested as HC for load bearing. Accounting
fragility issues, one could apply the rule of choosing pairs of packages to
decide on what height to place each of them based on a mass ratio $\eta$
(assuming that weight is related to fragility). Thus, defining
$P_{3}^{-}=\\{(i,k)\in I^{2}\text{ }|\text{ }i<k\text{ and
}\mu_{k}/\mu_{i}>\eta\\}$ (so $b_{i,k,3}=0\text{ }\forall(i,k)\in P_{3}^{-}$)
and $P^{-}_{6}=\\{(i,k)\in I^{2}\text{ }|\text{ }i<k,\text{ and
}\mu_{i}/\mu_{k}>\eta\\}$ (so $b_{i,k,6}=0\text{ }\forall(i,k)\in P_{6}^{-}$),
this instantiation avoid configurations where items whose mass are more than
$\eta$ times the mass of other ones are placed above of them.

Figure 4 represents the results provided by Q4RealBPP for each of the
instances described in Table 5. Regarding the running time, we have
empirically determined the time it takes for the LeapCQMHybrid to resolve
these instances to be $30\text{\,}\mathrm{s}$, presenting a maximum Quantum
Processing Unit (QPU) access time of $0.032\text{\,}\mathrm{s}$ per execution.
Lastly, for interested readers, all obtained results are freely available
[33].

(a) Colour palette scheme used to relate id (item categories) with colours in
the illustrative examples.

(b) 3dBPP_1: 51 items without restrictions and $\sum_{i\in I}\mu_{i}=1776$.

(c) 3dBPP_2: inst. 3dBPP_1 with $M=1000$.

(d) 3dBPP_3: 52 items without restrictions.

(e) 3dBPP_4: inst. 3dBPP_3 with $\eta=2$.
$\\{\text{0:}{{\color[rgb]{0.58984375,0,0.3515625}\rule{4.26773pt}{5.69046pt}}},\text{1:}{{\color[rgb]{0.06640625,0,0.73828125}\rule{4.26773pt}{5.69046pt}}},\text{9:}{{\color[rgb]{1,0,0}\rule{4.26773pt}{5.69046pt}}}\\}$
weight more than twice of
$\\{\text{3:}{{\color[rgb]{0,0.4296875,1}\rule{4.26773pt}{5.69046pt}}},\dots,\text{8:}{{\color[rgb]{1,0.38671875,0}\rule{4.26773pt}{5.69046pt}}}\\}$.

(f) 3dBPP_5: 54 items without restrictions.

(g) 3dBPP_6: inst. 3dBPP_5 with
$\\{(\text{4:}{{\color[rgb]{0.09375,0.8203125,0.7734375}\rule{4.26773pt}{5.69046pt}}},\text{7:}{{\color[rgb]{1,0.8125,0}\rule{4.26773pt}{5.69046pt}}}),(\text{7:}{{\color[rgb]{1,0.8125,0}\rule{4.26773pt}{5.69046pt}}},\text{9:}{{\color[rgb]{1,0,0}\rule{4.26773pt}{5.69046pt}}})\\}$
incompatible.

(h) 3dBPP_7: 46 items without restrictions.

(i) 3dBPP_8: inst. 3dBPP_7 with
$(\text{4:}{{\color[rgb]{0.09375,0.8203125,0.7734375}\rule{4.26773pt}{5.69046pt}}},\text{8:}{{\color[rgb]{1,0.38671875,0}\rule{4.26773pt}{5.69046pt}}})$
incompatible and
$\\{(\text{0:}{{\color[rgb]{0.58984375,0,0.3515625}\rule{4.26773pt}{5.69046pt}}},\text{3:}{{\color[rgb]{0,0.4296875,1}\rule{4.26773pt}{5.69046pt}}}),(\text{0:}{{\color[rgb]{0.58984375,0,0.3515625}\rule{4.26773pt}{5.69046pt}}},\text{8:}{{\color[rgb]{1,0.38671875,0}\rule{4.26773pt}{5.69046pt}}})\\}$
together.

(j) 3dBPP_9: center of mass at $(\tilde{L},\tilde{W})=(750,750)$, the middle
of the bin.

(k) 3dBPP_10: center of mass at $(\tilde{L},\tilde{W})=(900,500)$.

(l) 3dBPP_11: $M=800$; $\eta=2$ and
$\\{\text{0:}{{\color[rgb]{0.58984375,0,0.3515625}\rule{4.26773pt}{5.69046pt}}},\text{7:}{{\color[rgb]{1,0.8125,0}\rule{4.26773pt}{5.69046pt}}}\\}$
weight more than twice of the rest;
$(\text{7:}{{\color[rgb]{1,0.8125,0}\rule{4.26773pt}{5.69046pt}}},\text{9:}{{\color[rgb]{1,0,0}\rule{4.26773pt}{5.69046pt}}})$
incompatible;
$\\{(\text{0:}{{\color[rgb]{0.58984375,0,0.3515625}\rule{4.26773pt}{5.69046pt}}},\text{3:}{{\color[rgb]{0,0.4296875,1}\rule{4.26773pt}{5.69046pt}}}),(\text{0:}{{\color[rgb]{0.58984375,0,0.3515625}\rule{4.26773pt}{5.69046pt}}},\text{8:}{{\color[rgb]{1,0.38671875,0}\rule{4.26773pt}{5.69046pt}}})\\}$
together; $(\tilde{L},\tilde{W})=(750,750)$.

(m) 3dBPP_12: $M=900$; $\eta=2$ and
$\\{\text{3:}{{\color[rgb]{0,0.4296875,1}\rule{4.26773pt}{5.69046pt}}},\text{4:}{{\color[rgb]{0.09375,0.8203125,0.7734375}\rule{4.26773pt}{5.69046pt}}}\\}$
weight more than twice of the rest;
$(\text{4:}{{\color[rgb]{0.09375,0.8203125,0.7734375}\rule{4.26773pt}{5.69046pt}}},\text{8:}{{\color[rgb]{1,0.38671875,0}\rule{4.26773pt}{5.69046pt}}})$
incompatible;
$(\text{2:}{{\color[rgb]{0,0.07421875,0.953125}\rule{4.26773pt}{5.69046pt}}},\text{4:}{{\color[rgb]{0.09375,0.8203125,0.7734375}\rule{4.26773pt}{5.69046pt}}})$
packed together; $(\tilde{L},\tilde{W})=(500,500)$ (the middle).

Figure 4: (a) Colour palette used in the solved instances. (b)-(m) Brief
description of instances given in Table 5 and solutions provided by Q4RealBPP.
Red lines show the bin boundaries. The activated restrictions work as
expected.

Besides that, we have conducted additional experimentation with the goal of
further understanding the performance of Q4RealBPP. For this purpose, we have
solved all the instances described in Table 5 under different time limits.
Thus, each instance has been run 10 times with 5, 10, 30 and 60 seconds as
time limits. In the top of Figure 5, the obtained results are shown using the
mean $\mu$ and and standard deviation $\sigma$ of the energy value
$\\{e_{i}\\}_{i=1}^{10}$, being $e_{i}$ the $i$-th energy returned by the
solver upon the assigned time limit for each instance. Moreover, the mean QPU
access time in nanoseconds is also attached. As a complementary analysis, in
the botton part of Figure 5, since the returned energies vary considerably
depending on the nature of the instance, we have computed the deviation around
the mean energies in terms of

$\overline{\sigma}=\frac{1}{10}\sum_{i=1}^{10}\left|\frac{e_{i}}{\mu}-1\right|$
(28)

for illustrating more clearly the stability of the solution. This additional
analysis is depicted in the bottom part of Figure 5.

Three main conclusions can be drawn from Figure 5: 1) generally, the longer
the time limit given, the lower the energy returned (thus the better solution
quality); 2) the deviation around the mean values of the objective function
remains stable against the different time limits given as well as it does not
show a remarkable dependency with the nature of the instance studied; and 3)
although different time limits have been given to the solver, the QPU access
time did not vary significantly for each one, indicating that the optimization
process on the LeapCQMHybrid workflow mainly relies on the heuristic module of
the solver. Despite the clear behaviour exhibited by our results, further work
should be done for having a deeper understanding of how the presented
framework performs.

Figure 5: Top: mean + std for the 10 runs belonging to each instance. From
left to right on each instance, the time limits given to the solver are
$5\text{\,}\mathrm{s}$, $10\text{\,}\mathrm{s}$, $30\text{\,}\mathrm{s}$ and
$60\text{\,}\mathrm{s}$. Numbers placed above and below the shaded areas show
the mean QPU access time for every time limit within each instance (in units
of nanoseconds). Bottom: using (28), deviation around the mean energy of the
results depicted above. For both plots, shaded area shows the region where the
minimum and maximum values fell during the study.

## Conclusions and future work

Conclusions and future work

In this work we have presented Q4RealBPP, a quantum-classical framework for
solving real-world instances of the 3dBPP. This software can be easily used
for both end-users and practitioners for dealing with 3dBPP instances
considering constraints such as the weight, load bearing, package categories
and load balancing.

To prove the applicability of Q4RealBPP, we have tested it over 12 instances
of different nature, with the main intention of showcasing the capacity of the
method to encompass real-world constraints. As depicted in Figure 4, Q4RealBPP
has successfully tackled all the generated instances, contemplating different
real-world situations. Particularly noteworthy are the last two instances,
3dBPP_11 and 3dBPP_12 (Figures 4(l) and 4(m), respectively), where all the
constraints are activated.

The future work comprises 3 main interests: i) to develop a more advanced
version of the Q4RealBBP to generalise the framework to other BPP variants,
and considering further features such as multi-class categorisation of items;
ii) to exploit this framework in conjunction to complementary Artificial
Intelligence algorithms to enhance its potential real applications; and iii)
to further analyse the results by comparing performance with classical
solvers.

## Data availability

Data availability

The code is available from the corresponding author (E.O.) upon reasonable
request. The data used, as well as Q4RealBPP- DataGen and all the results
discussed in this work, are available at
http://dx.doi.org/10.17632/y258s6d939.1.

## References

  * [1] Garey, M. R. & Johnson, D. S.  Approximation algorithms for bin packing problems: A survey.  In _Analysis and design of algorithms in combinatorial optimization_ , 147–172 (Springer, 1981).
  * [2] Munien, C. & Ezugwu, A. E.  Metaheuristic algorithms for one-dimensional bin-packing problems: A survey of recent advances and applications.  _Journal of Intelligent Systems_ 30, 636–663 (2021).
  * [3] Delorme, M., Iori, M. & Martello, S.  Bin packing and cutting stock problems: Mathematical models and exact algorithms.  _European Journal of Operational Research_ 255, 1–20 (2016).
  * [4] Martello, S., Pisinger, D. & Vigo, D.  The three-dimensional bin packing problem.  _Operations research_ 48, 256–267 (2000).
  * [5] Lodi, A., Martello, S. & Vigo, D.  Heuristic algorithms for the three-dimensional bin packing problem.  _European Journal of Operational Research_ 141, 410–420 (2002).
  * [6] Yang, H. & Shi, J.  A hybrid cd/vnd algorithm for three-dimensional bin packing.  In _2010 Second International Conference on Computer Modeling and Simulation_ , vol. 3, 430–434 (IEEE, 2010).
  * [7] Parreño, F., Alvarez-Valdés, R., Oliveira, J. F. & Tamarit, J. M.  A hybrid grasp/vnd algorithm for two-and three-dimensional bin packing.  _Annals of Operations Research_ 179, 203–220 (2010).
  * [8] Elhedhli, S., Gzara, F. & Yildiz, B.  Three-dimensional bin packing and mixed-case palletization.  _INFORMS Journal on Optimization_ 1, 323–352 (2019).
  * [9] Ramos, A. G., Silva, E. & Oliveira, J. F.  A new load balance methodology for container loading problem in road transportation.  _European Journal of Operational Research_ 266, 1140–1152 (2018).
  * [10] Paquay, C., Schyns, M. & Limbourg, S.  A mixed integer programming formulation for the three-dimensional bin packing problem deriving from an air cargo application.  _International Transactions in Operational Research_ 23, 187–213 (2016).
  * [11] Paquay, C., Limbourg, S., Schyns, M. & Oliveira, J. F.  Mip-based constructive heuristics for the three-dimensional bin packing problem with transportation constraints.  _International Journal of Production Research_ 56, 1581–1592 (2018).
  * [12] Silva, E. F., Machado Toffolo, T. A. & Wauters, T.  Exact methods for three-dimensional cutting and packing: A comparative study concerning single container problems.  _Computers & Operations Research_ 109, 12–27 (2019).
  * [13] Lucas, A.  Ising formulations of many np problems.  _Frontiers in Physics_ 2 (2014).
  * [14] Gill, S. S. _et al._ Quantum computing: A taxonomy, systematic review and future directions.  _Software: Practice and Experience_ 52, 66–114 (2022).
  * [15] Chandarana, P. _et al._ Meta-learning digitized-counterdiabatic quantum optimization.  _arXiv preprint arXiv:2206.09966_ (2022).
  * [16] Huang, T. _et al._ Time-optimal quantum driving by variational circuit learning.  _arXiv preprint arXiv:2211.00405_ (2022).
  * [17] Luckow, A., Klepsch, J. & Pichlmeier, J.  Quantum computing: Towards industry reference problems.  _Digitale Welt_ 5, 38–45 (2021).
  * [18] Osaba, E., Villar-Rodriguez, E. & Oregi, I.  A systematic literature review of quantum computing for routing problems.  _IEEE Access_ (2022).
  * [19] Orús, R., Mugel, S. & Lizaso, E.  Quantum computing for finance: Overview and prospects.  _Reviews in Physics_ 4, 100028 (2019).
  * [20] Garcia-de Andoin, M., Osaba, E., Oregi, I., Villar-Rodriguez, E. & Sanz, M.  Hybrid quantum-classical heuristic for the bin packing problem.  In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2214–2222 (Association for Computing Machinery, 2022).
  * [21] De Andoin, M. G., Oregi, I., Villar-Rodriguez, E., Osaba, E. & Sanz, M.  Comparative benchmark of a quantum algorithm for the bin packing problem.  In _2022 IEEE Symposium Series on Computational Intelligence (SSCI)_ , 930–937 (2022).
  * [22] Bozhedarov, A. _et al._ Quantum and quantum-inspired optimization for solving the minimum bin packing problem.  _arXiv preprint arXiv:2301.11265_ (2023).
  * [23] Layeb, A. & Boussalia, S. R.  A novel quantum inspired cuckoo search algorithm for bin packing problem.  _International Journal of Information Technology and Computer Science_ 4, 58–67 (2012).
  * [24] Zendaoui, Z. & Layeb, A.  Adaptive cuckoo search algorithm for the bin packing problem.  In _Modelling and implementation of complex systems_ , 107–120 (Springer, 2016).
  * [25] Layeb, A. & Boussalia, S. R.  A novel greedy quantum inspired cuckoo search algorithm for variable sized bin packing problem.  _International Journal of Mathematics in Operational Research_ 6, 732–751 (2014).
  * [26] Zhang, G.  Quantum-inspired evolutionary algorithms: a survey and empirical study.  _Journal of Heuristics_ 17, 303–351 (2011).
  * [27] D-Wave Developers.  Measuring Performance of the Leap Constrained Quadratic Model Solver.  Tech. Rep. 14-1065A-A, D-Wave Systems Inc. (2022).
  * [28] DWave Ocean Developers Team.  3d-bin-packing (GitHub repository) (2022).  Last retrieved 2023/02/27.
  * [29] Preskill, J.  Quantum Computing in the NISQ era and beyond.  _Quantum_ 2, 79 (2018).
  * [30] Dahmani, N. & Krichen, S.  Solving a load balancing problem with a multi-objective particle swarm optimisation approach: application to aircraft cargo transportation.  _International Journal of Operational Research_ 27, 62–84 (2016).
  * [31] Zhu, R. & Wang, L.  Research on real-time channel optimization of ship based on load balancing algorithm.  In _The 29th International Ocean and Polar Engineering Conference_ (OnePetro, 2019).
  * [32] D-Wave Developers.  Hybrid Solver for Constrained Quadratic Models.  Tech. Rep. 14-1055A-A, D-Wave Systems Inc. (2021).
  * [33] Osaba, E., Villar, E. & V. Romero, S.  Benchmark dataset and instance generator for real-world 3dbpp.  http://dx.doi.org/10.17632/y258s6d939.1 (2023).  Online at Mendeley Data.
  * [34] Osaba, E., Villar-Rodriguez, E. & V. Romero, S.  Benchmark dataset and instance generator for real-world three-dimensional bin packing problems.  _arXiv preprint arXiv:2304.14712_ (2023).

## Funding

Funding

This work was supported by the Basque Government through HAZITEK program
(Q4_Real project, ZE-2022/00033), and by the Spanish CDTI through Proyectos
I+D Cervera 2021 Program (QOptimiza project, 095359) and Misiones Ciencia e
Innovación Program (CUCO) under Grant MIG-20211005.

## Author contributions statement

Author contributions statement

All authors conceived the research. S.V.R. formulated the problem and
developed the code. E.V.R. formulated and developed the instance generator.
S.V.R. and E.O. conceived and conducted the experiments. All authors wrote the
manuscript. All authors reviewed the manuscript.

## Competing interests

Competing interests

The authors declare no competing interests.