This article was downloaded by: [131.178.125.

46] On: 20 September 2016, At: 09:35

Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
INFORMS is located in Maryland, USA

Operations Research
Publication details, including instructions for authors and subscription information:
http://pubsonline.informs.org

The Three-Dimensional Bin Packing Problem

Silvano Martello, David Pisinger, Daniele Vigo,

To cite this article:

Silvano Martello, David Pisinger, Daniele Vigo, (2000) The Three-Dimensional Bin Packing Problem. Operations Research
48(2):256-267. http://dx.doi.org/10.1287/opre.48.2.256.12386

Full terms and conditions of use: http://pubsonline.informs.org/page/terms-and-conditions

This article may be used only for the purposes of research, teaching, and/or private study. Commercial use
or systematic downloading (by robots or other automatic processes) is prohibited without explicit Publisher
approval, unless otherwise noted. For more information, contact permissions@informs.org.

The Publisher does not warrant or guarantee the article’s accuracy, completeness, merchantability, fitness
for a particular purpose, or non-infringement. Descriptions of, or references to, products or publications, or
inclusion of an advertisement in this article, neither constitutes nor implies a guarantee, endorsement, or
support of claims made of that product, publication, or service.

© 2000 INFORMS

Please scroll down for article—it is on subsequent pages

INFORMS is the largest professional society in the world for professionals in the fields of operations research, management
science, and analytics.
For more information on INFORMS, its publications, membership, or meetings visit http://www.informs.org
 THE THREE-DIMENSIONAL BIN PACKING PROBLEM
SILVANO MARTELLO
DEIS, University of Bologna, Viale Risorgimento 2, Bologna, Italy, smartello@deis.unibo.it

DAVID PISINGER
DIKU, University of Copenhagen, University Parken 1, Copenhagen, Denmark
Downloaded from informs.org by [131.178.125.46] on 20 September 2016, at 09:35 . For personal use only, all rights reserved.

DANIELE VIGO
DEIS, University of Bologna, Viale Risorgimento 2, Bologna, Italy
(Received June 1997; revisions received March 1998, August 1998; accepted October 1998)

The problem addressed in this paper is that of orthogonally packing a given set of rectangular-shaped items into the minimum
number of three-dimensional rectangular bins. The problem is strongly NP-hard and extremely difficult to solve in practice. Lower
bounds are discussed, and it is proved that the asymptotic worst-case performance ratio of the continuous lower bound is 81. An exact
algorithm for filling a single bin is developed, leading to the definition of an exact branch-and-bound algorithm for the three-
dimensional bin packing problem, which also incorporates original approximation algorithms. Extensive computational results,
involving instances with up to 90 items, are presented: It is shown that many instances can be solved to optimality within a reasonable
time limit.

1. INTRODUCTION An approximation algorithm for 3D-BPP was presented

We are given a set of n rectangular-shaped items, each by Scheithauer (1991). Chen et al. (1995) considered a
characterized by width wj, height hj, and depth dj ( j 僆 J ⫽ generalization of the problem, where the bins may have
{1, . . . , n}), and an unlimited number of identical three- different sizes: An integer programming formulation is de-
dimensional containers (bins) having width W, height H, veloped, and a small instance with n ⫽ 6 items is solved to
and depth D. The three-dimensional bin packing problem optimality using an MIP solver. Further details on 1D-BPP
(3D-BPP) consists of orthogonally packing all the items can be found in Martello and Toth (1990a) and Coffman et
into the minimum number of bins. We assume that the al. (1997); for 2D-BPP the reader is referred to Martello
items may not be rotated, i.e., that they are packed with and Vigo (1998).
each edge parallel to the corresponding bin edge. We also The 3D-BPP is closely related to other three-
assume, without loss of generality, that all the input data dimensional loading problems:
are positive integers satisfying wj 聿 W, hj 聿 H, and dj 聿 D
Y Knapsack Loading. In the knapsack loading of a con-
( j 僆 J). No further restriction is present: The items need
tainer each item has an associated profit, and the problem
not be packed in layers, and we do not impose the so-
is to choose a subset of the items that fits into a single
called guillotine constraint, which requires that the patterns
container (bin) so that maximum profit is loaded. If the
be such that the items can be obtained by sequential face-
profit of an item is set to its volume, this corresponds to
to-face cuts parallel to the faces of the bin (patterns satis-
fying such constraint are called guillotine packings). the minimization of wasted space. Heuristics for the knap-
Problem 3D-BPP is strongly NP-hard because it is a gen- sack loading problem have been presented in Gehring et
eralization of the well-known (one-dimensional) bin pack- al. (1990) and Pisinger (1997).
ing problem (1D-BPP), in which a set of n positive values Y Container Loading. In this version, all the items have
wj has to be partitioned into the minimum number of sub- to be packed into a single bin, which does, however, have
sets so that the total value in each subset does not exceed a an infinite height. The problem is thus to find a feasible
given bin capacity W. It is clear that 1D-BPP is the special solution such that the height to which the bin is filled is
case of 3D-BPP arising when hj ⫽ H and dj ⫽ D for all j 僆 minimized. The first heuristic for the container loading
J. Another important related problem arises when dj ⫽ D problem was presented by George and Robinson (1980),
for all j 僆 J: We have in this case the two-dimensional bin but several variants have been presented since then.
packing problem (2D-BPP), calling for the determination Bischoff and Marriott (1990) compare 14 different heuris-
of the minimum number of identical rectangular bins of tics based on the George-Robinson framework. Heuristics
size W ⫻ H needed to pack a given set of rectangles of with asymptotic worst-case performance guarantee have
sizes wj ⫻ hj ( j 僆 J). been presented by Li and Cheng (1990).

Subject classifications: Production/scheduling: cutting stock/trim. Transportation: freight/material handling. Programming: integer, branch-and-bound.
Area of review: TRANSPORTATION.

Operations Research, 䉷 2000 INFORMS 0030-364X/00/4802-0256 $05.00

Vol. 48, No. 2, March–April 2000, pp. 256 –267 256 1526-5463 electronic ISSN
 MARTELLO, PISINGER, AND VIGO / 257
For a general classification of packing and loading prob- solution requiring a number of bins arbitrarily close to
lems we refer to Dyckhoff (1990), Dyckhoff and Finke 8L0(I).
(1992), and Dyckhoff et al. (1997).
To our knowledge, no algorithms for the exact solution The heuristic applies at each iteration an algorithm
of 3D-BPP have been published, thus we start this presen- (called H2D hereafter) proposed by Martello and Vigo
tation by considering a number of lower bounds. In §2 we (1998) for the two-dimensional bin packing problem.
Given an instance Ĩ of 2D-BPP, algorithm H2D deter-
Downloaded from informs.org by [131.178.125.46] on 20 September 2016, at 09:35 . For personal use only, all rights reserved.

determine the worst-case behavior of the so-called contin-

uous lower bound for 3D-BPP. It is proved, through a mines a feasible solution requiring, say, U(Ĩ) bins such that
constructive algorithm, that the asymptotic worst-case per- the first U(Ĩ) ⫺ 2 of them are filled, on average, to at least
1
formance ratio of the continuous bound is 8. New bounds one-quarter of their area, i.e.,
are introduced and analyzed in §3. In §4 we present an
冘
U共 Ĩ 兲⫺2
HW
exact algorithm for selecting a subset of items that can be A i ⭓ 共U共Ĩ兲 ⫺ 2兲 ,
packed into a single bin by maximizing the total volume i⫽1 4
packed. These results are used in §5 to obtain two approx- where Ai denotes the total area occupied by the rectangles
imation algorithms and an exact branch-and-bound algo- packed by H2D into bin i. The heuristic algorithm for
rithm. An extensive computational test is presented in §6, 3D-BPP works as follows:
showing that the exact algorithm is able to solve instances
1. Partition the items, according to their depth, into a
with up to 90 items to optimality within reasonable time.
number q ⫽ log2 D ⫹ 1 of subsets J0, . . . , Jq⫺1, using the
In the following we will denote by Z an optimal solution
following rule:
value of 3D-BPP. The volume of item j will be denoted by
n
vj ⫽ wjhjdj, the total volume of the items in J by V ⫽ ¥j⫽1 D D
Item j is assigned to set J i iff ⬍ dj ⭐ i .
vj, and the bin volume by B ⫽ WHD. 2 i⫹1 2
In other words, J0 contains all the items with a depth
2. THE CONTINUOUS LOWER BOUND greater than D/ 2, J1 contains all the items with a depth not
An obvious lower bound for 3D-BPP comes from a relax- greater than D/ 2 and greater than D/4, and so on.
ation in which each item j is cut into wjhjdj unit-length 2. For each non empty subset Ji do the following:
cubes, thus producing the so-called continuous lower 2.1 Let Ĩi be the instance of 2D-BPP defined by 兩Ji兩
bound: rectangles having sizes wj and hj for each j 僆 Ji and bin

L0 ⫽
冘 n
j⫽1 vj
. (1)
sizes W and H;
2.2 Apply algorithm H2D to Ĩi, thus obtaining a solution
B
of value U(Ĩi) ⫽ ui ⫹ 2 with the first ui bins filled, on
Bound L0 can be computed in O(n) time. We next exam- average, to at least one-quarter of their area;
ine its worst-case behavior.
2.3 Derive the corresponding three-dimensional solution
Let Z(I) be the value of an optimal solution to an in-
using ui ⫹ 2 bin slices with width W, height H, and depth
stance I of a minimization problem, L(I) the value pro-
D/ 2i. Observe that, by definition of Ji, the first ui slices are
vided by a generic lower bound L, and let ␳(I) ⫽ L(I)/
filled, on average, to more than one-eighth of their vol-
Z(I). The absolute worst-case performance ratio of L is then
ume, i.e.,
defined as the smallest real number ␳ such that ␳(I) 肁 ␳

冘V
ui
for any instance I of the problem. The asymptotic worst- D HW 1 B
k ⬎ ui ⫽ ui ,
case performance ratio of L is instead the smallest real k⫽1 2 i⫹1 4 8 2i
number ␳⬁ such that there exists a (large) positive integer
value N for which ␳(I) 肁 ␳⬁ for all instances I satisfying where Vk denotes the total volume occupied by the items
Z(I) 肁 N. packed into bin slice k. Call fractional bin slices the last
It is known that, for 1D-BPP, the absolute worst-case two (possibly less filled) slices.
performance ratio of the continuous lower bound (¥j⫽1 n 3. Observe that all the bin slices have width W, height
1
wj/W) is 2 (see, e.g., Martello and Toth 1990a). Recently H, and a depth that is a “power-of-2” fraction of D. Hence
Martello and Vigo (1998) proved that, for 2D-BPP, the consider all the bin slices, apart from the fractional ones,
continuous lower bound (¥j⫽1 n
wjhj/(WH)) has an abso- according to decreasing depth, and combine them into full
1
lute worst-case performance ratio equal to 4. bins of depth D by simply filling up the bins with slices
from one end. This will give a number u of bins that have a
THEOREM 1. The asymptotic worst-case performance ratio total filling of more than u B/8, plus at most one possibly
1
of lower bound L0 is 8. less filled bin, u ⫹ 1.
4. Consider now the fractional bin slices and combine
PROOF. We prove the thesis by introducing a heuristic al- them, as done in Step 3, into full bins of depth D. Observe
gorithm that, given an instance I of 3D-BPP with a suffi- that at most four new bins are needed because there are two
ciently large solution value Z(I), produces a feasible such slices per subset, and their total depth is bounded by
 258 / MARTELLO, PISINGER, AND VIGO

冘 2 2D ⭐ 4D. 兵 D
其
q⫺1
J ᐉ 共 p兲 ⫽ j 僆 J WH : D ⫺ p ⭓ d j ⬎ , (5)
i 2
i⫽0
J 共 p兲 ⫽ 兵 j 僆 J 其
WH D
s : ⭓ dj ⭓ p . (6)
We have thus obtained a feasible solution that uses u ⫹ 5 2
n
bins. The total volume of all the items is V ⫽ ¥j⫽1 vj ⬎ THEOREM 2. LWH is a valid lower bound for 3D-BPP.
1
u B/8. Because Z(I) 聿 u ⫹ 5, we obtain
Downloaded from informs.org by [131.178.125.46] on 20 September 2016, at 09:35 . For personal use only, all rights reserved.

PROOF. By definition, items of JWH can possibly be packed

V u Z共I兲 5 into the same bin only by placing them one behind the
L 0 共I兲 ⫽ ⬎ ⭓ ⫺ . (2)
B 8 8 8 other. Hence, the relaxed instance of 3D-BPP consisting of
only such items is equivalent to an instance of 1D-BPP
To show that the bound is tight, it is sufficient to con-
defined by the values dj ( j 僆 JWH) with bin size D. A valid
sider an instance in which n is a multiple of eight, W ⫽
lower bound for 3D-BPP is thus given by any valid lower
H ⫽ D ⫽ a (where a is a very large even value) and, for
bound for 1D-BPP. Equation (4) has the form LWH ⫽␣⫹
each j 僆 J, wj ⫽ hj ⫽ dj ⫽ a/ 2 ⫹ 1. The optimal solution 1
max1聿p聿D/ 2{␤( p), ␥( p)} combining two such bounds: ␣ ⫹
value is clearly Z ⫽ n. If we denote with a3/8 ⫹ ⌬ the
max1聿p聿D/ 2{␤( p)} has been introduced by Martello and
volume of an item, we have L0 ⫽ n/8 ⫹ n⌬/a3 ⫽ n/8 ⫹ 1
Toth (1990b), and ␣ ⫹ max1聿p聿D/ 2{␥( p)} by Dell’Amico
(by assuming a 肁 3公n⌬), so the ratio L0/Z is arbitrarily
1 and Martello (1995). □
close to 8 for sufficiently large n. □
COROLLARY 2. A valid lower bound for 3D-BPP is
As previously mentioned, a variant of the problem may
admit rotation of the items. L 1 ⫽ max兵L 1WH, L 1WD, L 1HD其, (7)

COROLLARY 1. The asymptotic worst-case performance ra- where LWH1 is defined by (3)–(6), while LWD
1 (resp. LHD
1 )
1
tio of lower bound L0 is 8 even if rotation of the items (by are obtained from (3)–(6) by interchanging hj (resp. wj)
any angle) is allowed. with dj and H (resp. W) with D.

PROOF. Given any instance I, let Zr(I) denote the optimal PROOF. Immediate, because JWD ⫽ { j 僆 J : wj ⬎ W/ 2 and
solution value if the items may be rotated. Because dj ⬎ D/ 2} and JHD ⫽ { j 僆 J : hj ⬎ H/ 2 and dj ⬎ D/ 2},
Zr(I) 聿 Z(I), we immediately have from (2) that L0(I) 肁 i.e., LWD
1 and LHD
1 are equivalent to LWH
1 over a rotated
5
Zr(I)/8 ⫺ 8. On the other hand, the tightness example instance. □
above holds for this variant too. □ It has been proved in Martello and Toth (1990b) and
Dell’Amico and Martello (1995) that L1 can be computed
3. NEW LOWER BOUNDS in O(n2) time.
The continuous lower bound of the previous section is PROPOSITION 1. Lower bounds L0 and L1 do not dominate
likely to produce tight values when the item sizes are small each other.
with respect to the bin size. The lower bounds presented in
this section are better suited to the cases in which there PROOF. For the instance introduced in the tightness proof
are relatively large items. of Theorem 1 we have { j 僆 JWH : dj ⬎ D/ 2} ⫽ J, so from
Our first bound is obtained by reduction to the one- (4) we obtain L1 ⫽ n (⫽ Z), while L0 ⫽ n/8 ⫹ 1. Now
dimensional case. Let consider a similar instance with n multiple of eight, W, H,
and D even and, for each j 僆 J, wj ⫽ W/ 2, hj ⫽ H/ 2, and
兵
J WH ⫽ j 僆 J : w j ⬎
W
2
and h j ⬎
H
2
, 其 (3) dj ⫽ D/ 2. In this case L0 ⫽ n/8(⫽ Z), whereas L1 ⫽ 0,
because JWH ⫽ JWD ⫽ JHD ⫽ À. The latter instance also
and define shows that the worst-case performance of L1 can be arbi-
trarily bad. □
L 1WH ⫽ 冏再 j 僆 J WH
: dj ⬎
D
2
冎冏 Analogous bounds could be obtained by adapting to

冘 冘 the three-dimensional case other one-dimensional

⫹ max
1聿p聿D/ 2 冦 j僆J s 共 p兲 d j ⫺ 共兩J ᐉ 共 p兲兩D ⫺
D
j僆J ᐉ 共 p兲 dj兲
,
bounds, such as the extension of the Martello and Toth
bound proposed by Labbé et al. (1991). In the following
we describe an improved bound, which explicitly takes
into account the three item dimensions. Given any pair
冘 D ⫺ dj

冧
兩J s 共 p兲兩 ⫺ j僆J ᐉ 共 p兲 of integers ( p, q), with 1 聿 p 聿 W/ 2 and 1 聿 q 聿 H/ 2,
p define
, (4)
D
K v 共 p, q兲 ⫽ 兵 j 僆 J : w j ⬎ W ⫺ p and h j ⬎ H ⫺ q其, (8)
p
where 兵
K ᐉ 共 p, q兲 ⫽ j 僆 J⶿K v 共 p, q兲 : w j ⬎
W
2
and h j ⬎
H
2其, (9)
 MARTELLO, PISINGER, AND VIGO / 259
K s 共 p, q兲 ⫽ 兵 j 僆 J⶿共K v 共 p, q兲 艛 K ᐉ 共 p, q兲兲 : w j in the computation of (12) it is sufficient to consider the
values of p and q that correspond to distinct values of wj
⭓ p and h j ⭓ q其, (10)
and hj, respectively. Indeed, given any p value, let q1 and
and let q2 (with q1 ⬍ q2) be two distinct q values such that Ks( p,

再 冘 冘 冎
Downloaded from informs.org by [131.178.125.46] on 20 September 2016, at 09:35 . For personal use only, all rights reserved.

j僆K ᐉ 共 p, q兲艛K s 共 p, q兲 v j ⫺ 共D L 1WH ⫺ j僆K v 共 p, q兲 d j 兲WH

L 2WH共 p, q兲 ⫽ L 1WH ⫹ max 0, , (11)
B

and q1) ⫽ Ks( p, q2), and note that the increase of q from q1 to
q2 may cause one or more items to move from Kᐉ( p, q) to
L 2WH ⫽ max 兵L 2WH共 p, q兲其. (12)
1聿p聿W/ 2; 1聿q聿H/ 2 Kv( p, q), i.e., Kᐉ( p, q2) ⫽ Kᐉ( p, q1)⶿K and Kv( p, q2) ⫽
Kv( p, q1) 艛 K. Hence, LWH WH
2 ( p, q1) 聿 L2 ( p, q2) because
THEOREM 3. LWH
2 is a valid lower bound for 3D-BPP.
for each item i 僆 K the value of the numerator in (11) is
PROOF. We will show that, for any pair ( p, q), LWH 2 ( p, q)
increased by di(WH ⫺ wihi) 肁 0. Therefore, only distinct
is a valid lower bound for the relaxed instance of 3D-BPP values q ⫽ hj 聿 H/ 2 need be considered because they
consisting of only the items in Kv( p, q) 艛 Kᐉ( p, q) 艛 Ks( p, induce different sets Ks( p, q), while all the intermediate q
q). For any pair ( p, q), Kv( p, q) 艛 Kᐉ( p, q) coincides with values produce dominated lower bounds. Analogously, we
set JWH (see (3)), so LWH 1 is a valid lower bound on the obtain that for any q value only the values p ⫽ wj 聿 W/ 2
number of bins needed for such items. The second term in need be considered.
(11) increases this value through a lower bound on the We conclude the proof by showing that given a p value,
number of additional bins needed for the items in Ks( p, q). the computation of the bounds LWH 2 ( p, q) for all q may be

To this end observe that an item of Kᐉ( p, q) 艛 Ks( p, q) parametrically performed in O(n) time. Indeed, let us as-
and one of Kv( p, q) could be packed into the same bin sume that items are renumbered according to nondecreas-
only by placing them one behind the other. In other words, ing hj values. The determination of the initial sets Kv( p,
with respect to our relaxed instance, any item of Kv( p, q) h1), Kᐉ( p, h1), and Ks( p, h1), as well as the computation of
of size wj ⫻ hj ⫻ dj can be seen as a larger equivalent item LWH
2 ( p, h1), may be clearly performed in O(n) time. As to

of size W ⫻ H ⫻ dj. Hence, the total volume of the LWH 1

the remaining q values, the computation of the corre-
bins that can be used for the items of Ks( p, q) is given by sponding bounds simply requires the updating of
BLWH1 minus the volume of the equivalent items of Kv( p, ¥j僆Kᐉ( p,q)艛Ks( p,q) vj and ¥j僆Kv( p,q) dj. Indeed Kv( p, q) 艛
q), minus the volume of the items of Kᐉ( p, q). It follows Kᐉ( p, q) ⫽ JWH is invariant, while for each new q value
that at least some items may move from Kᐉ( p, q) to Kv( p, q), and some

max 0,再 冘 j僆K s 共 p,q兲 v j ⫺ 共B L 1WH ⫺ WH 冘 j僆K v 共 p,q兲 dj ⫺ 冘 j僆K ᐉ 共 p,q兲 vj兲
冎 (13)
B

additional bins are needed for the items of Ks( p, q), hence new items may enter Ks( p, q). Hence, for each p value the
the thesis. □ overall computation requires O(n) time. □

COROLLARY 3. A valid lower bound for 3D-BPP is Although the worst-case time complexity of L2 is equal
to that of L1, it should be noted that the computational
L 2 ⫽ max兵L 2WH, L 2WD, L 2HD其, (14)
effort required to compute L2 is considerably greater than
where LWD2 (resp. LHD
2 ) are obtained from (8)–(11) and that required by L1. However:
(12) by interchanging hj (resp. wj) with dj and H (resp. W)
PROPOSITION 3. L2 dominates both L0 and L1.
with D.
PROOF. For p ⫽ q ⫽ 1 we have Kv( p, q) ⫽ { j 僆 J : wj ⫽
PROOF. Immediate, because LWD2 and LHD
2 are equivalent
WH W and hj ⫽ H} and Kv( p, q) 艛 Kᐉ( p, q) 艛 Ks( p, q) ⫽ J.
to L2 over a rotated instance. □
Hence, from (11)
PROPOSITION 2. L2 can be computed in O(n2) time.
L 2WH共1, 1兲 ⫽ L 1WH ⫹ max 0, 再 冘 j僆J v j ⫺ BL 1WH
冎
PROOF. We show how to compute LWH 2 in O(n2) time. B
WH
First observe that L1 is independent of p and q, hence it
can be computed once (in O(n2) time). We now prove that 再
⫽ max L 1WH,
冘 j僆J vj
冎 , (15)
B
 260 / MARTELLO, PISINGER, AND VIGO
from which LWH
2 肁 max{LWH
1 , L0}. Analogously we have Figure 1. Two-dimensional single bin filling. (The en-
L2 肁 max{L1 , L0} and LHD
WD WD
2 肁 max{LHD1 , L0}. □ velope associated with the placed items is
marked by a dashed line, and black points
4. FILLING A SINGLE BIN indicate corner points in Ĉ(I).)
In §5 we describe an enumerative algorithm for the exact
solution of 3D-BPP. This algorithm repeatedly solves asso-
Downloaded from informs.org by [131.178.125.46] on 20 September 2016, at 09:35 . For personal use only, all rights reserved.

ciated subproblems in which all the items of a given subset

J៮ have to be packed, if possible, into a single bin. This
problem too is NP-hard in the strong sense, because solv-
ing a special case in which all the items have the same
depth dj ⫽ D and the same height hj ⫽ 1 answers the
question of whether an instance of the one-dimensional
bin packing problem admits a solution requiring no more
than H bins. In the present section we describe a branch-
and-bound algorithm for the exact solution of an optimiza-
tion version of the problem (maximize the total volume of
the packed items), which is also used within one of the
heuristic algorithms presented in §5.3.
The problem we consider is that of selecting a subset J៮ ⬘
債 J៮ of items and assigning coordinates (xj, yj, zj) to each item
j 僆 J៮⬘ such that no item goes outside the bin, no two items
overlap, and the total volume of the items in J៮⬘ is a maximum. a “cycle” of items in which two items are both one to the
For the two-dimensional case, a knapsack loading version of right of the other (i.e., a is to the right of b and b to the
the problem has been considered in Hadjiconstantinou and right of a), or one above the other, or one behind the other.
Christofides (1995). In the following we present a nontrivial It is well known that the vertices of an acyclic digraph can
generalization of the two-dimensional approach to the be renumbered so that i ⬍ j if arc (i, j) exists. □
three-dimensional case, and we give an effective algorithm
for this problem. We assume that the origin of the coordi- It follows that the enumeration scheme for filling a sin-
nate system is in the left-bottom-back corner of the bin. gle bin can be limited to generate only solutions that: (i)
At each node of the branch-decision tree, described in satisfy Property 1 and (ii) are such that the sequence in
more detail in §4.2, a current partial solution, which packs which the items are assigned (starting from the root node)
the items of a certain subset I 傺 J៮ , is increased by selecting constitute an item numbering satisfying Property 2.
in turn each item j 僆 J៮ ⶿ I and generating descendant nodes An important consequence of (ii) is that at any decision
by placing j into all the admissible points. By placing an node, where the items of I are already packed and item
item into a point p we mean that its left-bottom-back cor- j 僆 J៮ ⶿ I is selected for branching, j may be placed only at
ner is positioned at p. points p such that no item of I has some part right of p, or
Let ( xp, yp, zp) be the coordinates of point p: Obviously above p, or in front of p. In other words, the items of I
item j cannot be placed at p if xp ⫹ wj ⬎ W or yp ⫹ hj ⬎ define an “envelope” separating the two regions where the
H or zp ⫹ dj ⬎ D. The set of admissible points to be items of J៮ ⶿ I may (resp. may not) be placed. More formally,
considered may be further drastically reduced through the a new item may be placed only in the set
following properties.
S共I兲 ⫽ 兵共 x, y, z兲 : ᭙ i 僆 I, x ⭓ x i ⫹ w i or y ⭓ y i
PROPERTY 1. Any packing of a bin can be replaced by an ⫹ h i or z ⭓ z i ⫹ d i 其. (17)
equivalent packing where no item may be moved leftward,
downward, or backward. Figure 1 shows, for the two-dimensional case (in which the
feasible region is Ŝ(I) ⫽ {( x, y) : @i 僆 I, x 肁 xi ⫹ wi or y 肁
PROOF. Obvious. A similar property was observed by yi ⫹ hi}), a set of already placed items and the corresponding
Christofides and Witlock (1977) for the two-dimensional envelope. Observe that, as a result of Property 1, the next
case. □ item j may be placed only at points where the slope of the
PROPERTY 2. An ordering of the items in an optimal solu- envelope changes from vertical to horizontal (black points in
tion exists such that, if i ⬍ j, Figure 1); such points are called in the following corner points
of the envelope. In the next subsection we show how the set
x i ⫹ w i ⭐ x j or y i ⫹ h i ⭐ y j or z i ⫹ d i ⭐ z j . (16) of feasible corner points can be efficiently determined.
PROOF. Given any optimal solution, define an associated
digraph with a vertex for each item and an arc from vertex 4.1. Finding Possible Positions for Placing an Item
i to vertex j if and only if (16) holds. It is clear that the We solve this problem by repeatedly solving two-
resulting digraph is acyclic because otherwise we would have dimensional problems obtained by considering the x-y
 MARTELLO, PISINGER, AND VIGO / 261
faces of a subset of items. We thus start with the descrip- Figure 2. Three-dimensional single bin filling. (Corner
tion of the two-dimensional algorithm. points C(I) are found by applying algorithm
Given an item set I, it is quite easy to find, in two 2D-CORNERS five times, one for each value
dimensions, the set Ĉ(I) of corner points of the envelope of z⬘k. True corner points are black dots, false
associated with the feasible region Ŝ(I) defined by the x-y corner points are empty circles.)
faces of the items in I. Following Property 2, let us order
Downloaded from informs.org by [131.178.125.46] on 20 September 2016, at 09:35 . For personal use only, all rights reserved.

the items according to their end points ( xj ⫹ wj, yj ⫹ hj), so

that the values of yj ⫹ hj are nonincreasing, breaking ties
by the largest value of xj ⫹ wj (see Figure 1). The following
algorithm for determining the corner points set consists of
three phases. First, extreme items are found, i.e., items whose
end point coincides with a point where the slope of the enve-
lope changes from horizontal to vertical. In the second phase,
corner points are defined at intersections between the lines
leading out from end points of extreme items. Finally, infea-
sible corners, where no further item of J៮ ⶿I can fit, are re-
moved. Thus we get the following algorithm.

Algorithm 2D-CORNERS:
begin
if I ⫽ À then Ĉ(I) :⫽ {(0, 0)} and return;
comment: Phase 1 (identify the extreme items e1, . . . ,
em);
x៮ :⫽ m :⫽ 0; the set of three-dimensional items currently packed into
for j :⫽ 1 to 兩I兩 do the bin. One may apply the algorithm for z ⫽ 0 and for
if xj ⫹ wj ⬎ x៮ each distinct z coordinate where an item of I ends, by
then m :⫽ m ⫹ 1; em :⫽ j; x៮ :⫽ xj ⫹ wj; increasing 2 values. For each such coordinate z⬘, 2D-
comment: Phase 2 (determine the corner points); CORNERS can be applied to the subset of those items i 僆
Ĉ(I) :⫽ {(0, ye1 ⫹ he1)}; I that end after z⬘, i.e., such that
for j :⫽ 2 to m do z i ⫹ d i ⬎ z⬘, (19)
Ĉ(I) :⫽ Ĉ(I) 艛 {( xej⫺1 ⫹ wej⫺1, yej ⫹ hej)};
adding the resulting corner points to C(I). In this way,
Ĉ(I) :⫽ Ĉ(I) 艛 {( xem ⫹ wem, 0)};
however, one may obtain some false corner points because
comment: Phase 3 (remove infeasible corner points);
they are corner points in the two-dimensional case, but not
for each ( x⬘j, y⬘j) 僆 Ĉ(I) do
in the three-dimensional case (see, e.g., Figure 2). Such
if x⬘j ⫹ mini僆J៮ ⶿ I{wi} ⬎ W or y⬘j ⫹ mini僆J៮ ⶿ I{hi} ⬎ H
points are easily removed by dominance, where we say that
then Ĉ(I) :⫽ Ĉ(I)⶿{( xj, y⬘j)}
a corner point ( x⬘b, y⬘b, z⬘b) is dominated by another corner
end.
point ( x⬘a, y⬘a, z⬘a) that is “hidden” behind it. Formally this
Consider the example in Figure 1. The extreme items may be written as
are 1, 3, 4, 6, and 9, and the resulting corner points are x⬘a ⫽ x⬘b and y⬘a ⫽ y⬘b and z⬘a ⬍ z⬘b , (20)
indicated by black dots; Phase 3 could remove some of the
first and/or last corner points. where we have equalities in the first two expressions be-
The time complexity of 2D-CORNERS is O(兩I兩), plus cause (19) ensures that all the items in front of z⬘k are
O(兩I兩 log 兩I兩) for the initial item sorting, i.e., O(n) plus O(n chosen, and thus no corner point will be generated inside
log n). the three-dimensional envelope. This is done in the follow-
Assume that the resulting corner points are Ĉ(I) ⫽ {( x⬘1, ing algorithm, where the generation of corner points ends
y⬘1), . . . , ( x⬘ᐉ, y⬘ᐉ)} ⫽ À. Then the area occupied by the as soon as a z coordinate is found such that no further item
envelope is could be placed after it.

冘 共 x⬘ ⫺ x⬘ Algorithm 3D-CORNERS:
ᐉ
A共I兲 ⫽ x⬘1 H ⫹ i i⫺1 兲 y⬘i⫺1 ⫹ 共W ⫺ x⬘ᐉ 兲 y⬘ᐉ , (18) begin
i⫽2
if I ⫽ À then C(I) :⫽ {(0, 0, 0)} and return;
where the first (resp. last) term is nonzero whenever the T :⫽ {0} 艛 { zi ⫹ di : i 僆 I} (comment: do not
first (resp. last) corner point found in Phase 2 has been duplicate equal values in T );
removed in Phase 3. In the special case where Ĉ(I) ⫽ À, sort T by increasing values, and let T ⫽ { z⬘1, . . . , z⬘r};
we obviously set A(I) ⫽ WH. C(I) :⫽ Ĉ(I0) :⫽ À; k :⫽ 1;
Algorithm 2D-CORNERS can be used to determine the while k 聿 r and z⬘k ⫹ mini僆J៮ ⶿ I{di} 聿 D do
set C(I) of corner points in three dimensions, where I is begin
 262 / MARTELLO, PISINGER, AND VIGO
Ik :⫽ {i 僆 I :zi ⫹ di ⬎ z⬘k}; experiments have shown that the algorithm is very time
apply 2D-CORNERS to Ik yielding Ĉ(Ik); consuming. However, in the branch-and-bound algorithm
for each ( x⬘j, y⬘j) 僆 Ĉ(Ik) do (comment: add true described in the next section, the single bin filling has often
corner points to C(I)) to be solved for a small subset J៮ of items. Thus ONEBIN
if ( x⬘j, y⬘j) 僆
兾 Ĉ(Ik⫺1) includes a specific procedure for solving the subproblem
then C(I) :⫽ C(I) 艛 {( x⬘j, y⬘j, z⬘k)}; when 兩J៮ 兩 聿 4 through direct enumeration of all the possible
Downloaded from informs.org by [131.178.125.46] on 20 September 2016, at 09:35 . For personal use only, all rights reserved.

k* :⫽ k; k :⫽ k ⫹ 1 placings of the boxes, avoiding symmetric or dominated

end solutions as those described by Scheithauer (1997).
end. For the case of two items, there are only three arrange-
The time complexity of 3D-CORNERS is O(n2). In- ments in which the items may be placed with respect to
deed, there are at most 兩I兩 ⫹ 1 distinct z coordinates in T, each other: one beside the other, one above the other, one
and each set Ĉ(Ik) is derived by 2D-CORNERS in O(兩Ik兩) behind the other. Thus these three arrangements are sim-
time because the sorting of the items can be done once ply tested.
and for all at the beginning of the algorithm. For each z⬘k With three items it is obvious that a guillotine packing
value, the check of corner points prior to their addition to always exists. Thus the problem may be reduced to that of
C(I) requires O(兩Ĉ(Ik⫺1)兩) time in total because both placing two items at one side of the cut and the remaining
Ĉ(Ik⫺1) and Ĉ(Ik) are ordered by increasing x⬘j and de- item at the other side. Hence, there are three ways in
creasing y⬘j. The overall complexity follows from the obser- which the items can be partitioned, and for each partition
vation that both 兩I兩 and 兩Ĉ(Ik)兩 are O(n). the cut can be made in three orthogonal orientations. The
The volume V(I) occupied by the envelope associated two items at one side of the cut can then be handled as the
with I is packing problem with two items.
With four items the case is more involved because non-
冘 共 z⬘ ⫺ z⬘
k*
V共I兲 ⫽ k k⫺1 兲 A共I k⫺1 兲 ⫹ 共D ⫺ z⬘k* 兲 A共I k* 兲, (21) guillotine packing is also possible (when the four items lay
k⫽2 on the same plane). If the items are guillotine packed,
where the last term is nonzero whenever k* ⬍ r. depending on how the first cut separates the items, the
possible placings can be handled as the packing problem
4.2. ONEBIN: An Exact Algorithm for Filling a Single with two or three items. As to non-guillotine packings, for
Bin reasons of symmetry, we may fix one of the items in a
We can now easily derive, in a recursive way, a branch- corner and consider the 3! placings of the remaining items
and-bound algorithm called ONEBIN for finding the best in the three remaining corners of the same plane, checking
filling of a single bin using items from a given set J៮ . Ini- that no two items overlap.
tially, no item is placed, so C(À) ⫽ {(0, 0, 0)}. At each
iteration, given the set I 傺 J៮ of currently packed items, set 5. EXACT AND APPROXIMATION ALGORITHMS
C(I) is determined through 3D-CORNERS together with FOR 3D-BPP
the corresponding volume V(I). If F is the total volume
The exact algorithm for 3D-BPP is based on the two-level
achieved by the current best filling, we may backtrack
decomposition principle presented by Martello and Vigo
whenever
(1998) for 2D-BPP. A main branching tree assigns items to
冘 v ⫹ 共B ⫺ V共I兲兲 ⭐ F,
i僆I
i (22) bins without specifying their actual position, while a spe-
cialized version of algorithm ONEBIN of §4.2 is used, at
because even if the remaining volume was completely certain decision nodes, to test whether a subset of items
filled, we would not improve on F. can be placed inside a single bin and to determine the
If no more items fit into the bin (i.e., if C(I) ⫽ À), we placing when the answer is affirmative. To construct a good
possibly update F and backtrack. Otherwise, for each posi- starting solution, two heuristic algorithms have been de-
tion ( x⬘, y⬘, z⬘) 僆 C(I) and for each item j 僆 J៮ ⶿ I, we assign fined, one based on a first-fit-decreasing approach and one
the item to this position (provided that its end points do based on an m-cut version of algorithm ONEBIN. In the
not exceed the bin limits) and call the procedure next subsections we describe the main components of our
recursively. exact algorithm.
The best performance of the branch-and-bound algo-
rithm was obtained when the items were ordered a priori 5.1. Main Branching Tree
according to nonincreasing volumes. This is not surprising The main branching tree assigns items to the different bins
because such ordering is consistent with the good perfor- without specifying their actual position. The items are pre-
mance of the well-known best-fit decreasing algorithm for viously sorted according to nonincreasing volumes, and the
1D-BPP. exploration follows a depth-first strategy. Let Z be the
Although the branch-and-bound approach based on 3D- incumbent solution value and M ⫽ {1, . . . , m} the current
CORNERS considerably limits the enumeration compared set of bins used to allocate items in the ascendant decision
to a naive technique trying all placings of items, practical nodes. A bin of M is called open if there is no evidence
 MARTELLO, PISINGER, AND VIGO / 263
Table 1. Item generation for Classes 1–5. Figure 3. A non-guillotine-cuttable pattern with five
items.
Type wj u.r. in hj u.r. in dj u.r. in
1
1 [1, 2 W] [32 H, H] [32 D, D]
2
2 [3 W, W] [1, 21 H] [32 D, D]
2
3 [3 W, W] [32 H, H] [1, 21 D]
Downloaded from informs.org by [131.178.125.46] on 20 September 2016, at 09:35 . For personal use only, all rights reserved.

1
4 [2 W, W] [21 H, H] [21 D, D]
1 1
5 [1, W]
2
[1, H]
2
[1, 21 D]

that no further item can be placed into it; otherwise, it is

called closed.
At each decision node the next free item is assigned, in
turn, to all the open bins; in addition, if 兩M兩 ⬍ Z ⫺ 1, the
item is also assigned to a new bin (hence opening it).
When an item k is assigned to a bin i (current bin) that 5.3. Approximation Algorithms
already contains, say, a subset Ji ⫽ À of items, the actual
feasibility of the assignment is checked as follows. First, To obtain a good upper bound at the root node of the
lower bound L2 is computed for the subinstance defined by branching tree and to limit the number of executions of
the items of J៮ ⫽ Ji 艛 {k}: if L2 肁 2 the node is immedi- ONEBIN, two different heuristics were used. The two ap-
ately killed. Otherwise, the heuristics of §5.3 are executed proaches computationally proved to have a “complementa-
for the subinstance: If a solution requiring a single bin is ry” behavior: For many instances a poor performance of
obtained, the assignment is accepted. If instead no such one of them corresponded to a good performance of the
solution is found, the optimal solution for the subinstance other one, although on average the second one gives better
is determined through the algorithm of §5.2. The node is results.
then accepted if a single bin solution is found, or killed The first heuristic is based on a layer building principle
otherwise. derived from shelf approaches used by several authors for
When the current node is accepted, an attempt is made 2D-BPP (see, e.g., Chung et al. 1982 and Berkey and
to close the current bin i. For each free item k⬘ we com- Wang 1987). In such approaches the rectangles are sorted
pute lower bound L2 for the subinstance defined by the by nonincreasing height and packed, from left to right, in
items of J៮ 艛 {k⬘}. If the lower bound is greater than one rows forming shelves. The first shelf is the bottom of the
for each k⬘, then the bin is closed because we know that no two-dimensional bin; when a new shelf is needed, it is
further item could be placed into it. Otherwise, the follow- created along the horizontal line that coincides with the
ing dominance rule is tested. Let K be the subset of those top of the tallest rectangle packed into the highest shelf.
free items for which the above lower bound computation For the three-dimensional case we first construct bin slices
has given value one. If one of the heuristics of §5.3 can having width W, height H, and different depths. Each slice
find a single bin solution for the subinstance defined by the is obtained through a two-dimensional shelf algorithm ap-
items in J៮ 艛 K, then we know that no better placing is plied to a subset containing the deepest items not yet
possible for these items, so we assign all of them to bin i packed. Because the shelf algorithm discards items that do
and close it. not fit into the current packing, the input subset consists of
Whenever a bin is closed, lower bound L2 is computed items with a total x-y area close to twice the available area.
for the instance defined by all the items not currently as- The slices are then combined into three-dimensional bins.
signed to closed bins: If Z 聿 L2 ⫹ c, where c is the Let J៮ be the set of items to be packed. The algorithm
number of closed bins, we backtrack. Because closed bins works as follows.
are seldom completely filled, this improved bound gener-
ally increases as the branching propagates. Algorithm H1:
begin
5.2. Single Bin Filling ៮ sort the items of T by nonincreasing depth;
T :⫽ J;
When a decision node is neither killed by the lower bound while T ⫽ À do
nor accepted by the heuristics, the feasibility of the current begin
assignment of the items in J៮ is tested through algorithm let T ⫽ { j1, . . . , j兩T兩};
r
ONEBIN of §4.2. Because we are only interested in find- k :⫽ max{r : ¥s⫽1 wjshjs ⬍ 2WH};
ing a solution where all the items in J៮ are packed, we comment: construct a single slice of depth dj1;
initialize the current best filling to F ⫽ ¥ᐉ僆J៮ vᐉ ⫺ 1: If the T⬘ :⫽ { j1, . . . , jk};
algorithm returns an unchanged value of F, then no filling sort the items of T⬘ by nondecreasing height;
exists with all the items inside the same bin. for each item j 僆 T⬘ do
 264 / MARTELLO, PISINGER, AND VIGO
Table 2. Number of instances, out of 10, solved to proved optimality.
Class
n 1 2 3 4 5 6 7 8 9 Total
10 10 10 10 10 10 10 10 10 10 90
15 10 10 10 10 10 10 10 10 10 90
20 10 10 10 10 10 10 10 10 10 90
Downloaded from informs.org by [131.178.125.46] on 20 September 2016, at 09:35 . For personal use only, all rights reserved.

25 10 10 10 10 10 10 9 10 10 89
30 10 10 10 10 10 10 5 10 10 85
35 9 9 10 10 7 10 5 6 9 75
40 9 8 8 10 4 10 3 8 8 68
45 5 6 4 10 8 10 1 7 2 53
50 5 2 4 10 3 10 2 4 — 40
60 1 1 — 9 1 6 — 5 — 23
70 — — — 6 2 4 — 4 — 16
80 — — 1 4 — 4 — 2 — 11
90 — — — 2 — 7 — 1 — 10
Total 79 76 77 111 75 111 55 87 69 740

if j fits into an existing shelf Because the solution times of algorithm ONEBIN may
then pack j into the lowest shelf where it fits be unacceptable when 兩T兩 is large, the branching scheme of
else if there is enough vertical space for j §4.2 has been changed to an m-cut enumeration as de-
then pack j into a new shelf; scribed in Ibaraki (1987), where at each decision node only
remove the packed items from T the first m branches are considered. Good values for m
end; were experimentally found to be m ⫽ 4 when 兩T兩 聿 10,
combine the slices into bins of depth D through a m ⫽ 3 when 10 ⬍ 兩T兩 聿 15, and m ⫽ 2 for larger prob-
1D-BPP algorithm lems. Moreover, a limit of 5,000 decision nodes was im-
end. posed on each filling of a bin, and the best solution found
within this limit was returned. Because of the limit on the
For the final step we used the FORTRAN code MTP,
provided in Martello and Toth (1990a), with a limit of 106 number of branches, algorithm H2 too produces different
backtrackings. By rotating the instance, algorithm H1 will solutions if the instance is rotated; hence this algorithm,
construct bin slices with width W, depth D, and different too, is run three times at the root node.
heights, or bin slices with height H, depth D, and different At other decision nodes, where the heuristics are used
widths. Thus at the root node H1 is run three times, cor- to find a single bin filling (see §5.1), we first run H2 once
responding to these rotations, and the best solution is and, if it fails, we run H1 once. Computational experi-
taken. ments showed indeed that the instance rotation very rarely
The second heuristic repeatedly fills a single bin. Let J៮ helps in the single bin case. The experiments also proved
be the set of items to be packed. Algorithm H2 initializes a that it is not convenient to use the heuristics, at each
set T to J៮ and sorts it by nondecreasing volume. Then H2 decision node, to produce complete feasible solutions
iteratively applies ONEBIN to T and removes the packed starting from the partial solution associated with the node.
items from it until T becomes empty. Both algorithms are obviously truncated as soon as it turns

Table 3. Average solution times expressed in HP9000/C160 160 Mhz CPU seconds.
Class
n 1 2 3 4 5 6 7 8 9
10 0.03 0.02 0.03 0.01 0.14 0.08 0.13 0.11 0.00
15 0.05 0.04 0.06 0.01 0.26 0.15 0.24 0.30 0.00
20 0.19 0.11 0.10 0.02 0.43 0.48 0.38 0.31 0.12
25 1.02 0.27 1.70 0.03 9.08 0.80 5.94 0.82 0.34
30 78.17 8.46 9.50 0.15 1.10 15.55 3.05 1.26 56.46
35 2.63 112.70 42.32 0.17 2.13 4.18 61.64 2.17 6.36
40 72.16 30.61 268.04 0.21 1.25 36.24 15.58 66.39 220.37
45 115.65 209.21 35.11 0.29 7.36 72.80 0.97 14.67 498.90
50 248.62 101.86 30.01 22.24 238.73 68.56 1.34 27.17 —
60 74.25 250.63 — 18.99 9.01 139.68 — 257.73 —
70 — — — 11.78 355.20 211.31 — 298.74 —
80 — — 4.03 4.74 — 31.76 — 137.16 —
90 — — — 223.13 — 131.31 — 308.66 —
 MARTELLO, PISINGER, AND VIGO / 265
Table 4. Average deviation of lower bound L0 with respect to the optimal solution value.
Class
n 1 2 3 4 5 6 7 8 9
10 24.2 37.1 38.9 45.5 40.0 31.0 40.0 28.6 0.0
15 31.9 31.1 33.3 42.5 37.9 31.8 30.0 27.0 0.0
20 30.0 34.8 30.0 46.3 30.8 27.8 34.2 32.7 0.0
Downloaded from informs.org by [131.178.125.46] on 20 September 2016, at 09:35 . For personal use only, all rights reserved.

25 27.0 30.0 33.8 46.1 30.4 23.7 28.2 30.9 0.0

30 30.2 30.0 29.1 44.8 29.6 20.6 31.8 28.3 0.0
35 25.6 26.7 27.2 46.4 33.3 18.2 26.9 28.9 0.0
40 23.7 27.9 29.3 47.3 31.0 19.3 38.1 26.2 0.0
45 28.8 28.9 24.5 47.8 28.6 17.7 50.0 25.8 0.0
50 26.6 32.1 26.4 46.3 25.8 14.3 35.3 25.6 0.0
60 21.4 26.7 — 47.8 30.0 14.5 — 21.6 0.0
70 — — — 48.0 25.9 12.1 — 22.0 0.0
80 — — 27.8 48.1 — 14.9 — 19.2 0.0
90 — — — 48.6 — 14.6 — 18.8 0.0

out that a single bin filling cannot be obtained. Namely, H1 is Y Class 6: bin size W ⫽ H ⫽ D ⫽ 10; items with wj, hj, dj
halted if the sum of the slice depths exceeds D, whereas u.r. in [1, 10].
H2 reduces to a single call to an approximate ONEBIN. Y Class 7: bin size W ⫽ H ⫽ D ⫽ 40; items with wj, hj, dj
u.r. in [1, 35].
6. COMPUTATIONAL EXPERIMENTS Y Class 8: bin size W ⫽ H ⫽ D ⫽ 100; items with wj, hj, dj
u.r in [1, 100].
To our knowledge no test instances have been published
for the three-dimensional bin packing problem. Thus in Finally, a new difficult class of all-fill problems has been
our computational experiments we have chosen to gener- introduced (Class 9). These instances have a known solu-
ate three-dimensional instances by generalizing some tion with three bins because the items are generated by
classes of randomly generated two-dimensional instances. cutting the bins into smaller parts. For a problem with n
Also a new class of “all-fill” instances was introduced. For items, bins 1 and 2 are cut into n/3 items each, while bin
short in the following “u.r.” means “uniformly random.” 3 is cut into n ⫺ 2n/3 items. The cutting is made using a
All test instances are available on website http://www. recursion, which may occasionally generate non-guillotine
diku.dk/⬃pisinger/codes.html. cutting patterns as that shown in Figure 3. A complete
The first classes of instances are generalizations of the description of the generation of the instances can be found
instances considered by Martello and Vigo (1998). The bin in Martello, Pisinger, and Vigo (1997).
size is W ⫽ H ⫽ D ⫽ 100, and five types of items are The exact code was implemented in C, and the experi-
considered, as described in Table 1. We then obtained five ments were run on a HP9000/C160 160 MHz. The out-
classes of instances as follows. For Class k (k ⫽ 1, . . . , 5), come of our experiments is given in Tables 2 through 8. A
each item is of type k with probability 60% and of the time limit of 1,000 seconds was given to each instance, and
other four types with probability 10% each. 10 instances were generated for each class and size of a
The second group of classes is a generalization of the problem. Fine-tuning of the algorithm showed that the
instances presented by Berkey and Wang (1987). The best performance was obtained if the principle of closing a
three classes may be described as: bin, described in §5.1, was tested only at branching nodes

Table 5. Average deviation of lower bound L1 with respect to the optimal solution value.
Class
n 1 2 3 4 5 6 7 8 9
10 6.1 11.4 22.2 1.5 16.0 27.6 32.0 17.9 3.3
15 17.0 17.8 22.9 1.1 24.1 29.5 20.0 13.5 6.7
20 13.3 13.6 18.3 0.8 15.4 24.1 15.8 14.3 6.7
25 12.2 15.7 12.7 1.9 19.6 22.0 20.5 16.4 16.7
30 14.0 16.2 16.3 3.5 16.7 29.4 27.3 18.3 3.3
35 9.8 10.5 15.5 2.4 14.6 26.0 23.1 15.6 16.7
40 13.4 12.8 16.3 2.1 13.8 18.2 23.8 16.9 10.0
45 13.6 13.2 18.4 2.2 19.0 18.8 12.5 14.5 10.0
50 12.5 7.1 15.1 2.4 19.4 22.4 11.8 18.6 20.0
60 7.1 13.3 — 1.5 20.0 18.4 — 11.8 36.7
70 — — — 2.0 11.1 20.7 — 12.0 10.0
80 — — 0.0 1.1 — 13.4 — 7.7 16.7
90 — — — 0.9 — 16.2 — 18.8 26.7
 266 / MARTELLO, PISINGER, AND VIGO
Table 6. Average deviation of lower bound L2 with respect to the optimal solution value.
Class
n 1 2 3 4 5 6 7 8 9
10 6.1 11.4 19.4 1.5 16.0 17.2 28.0 14.3 0.0
15 12.8 13.3 16.7 1.1 24.1 20.5 10.0 10.8 0.0
20 13.3 12.1 16.7 0.8 15.4 14.8 13.2 12.2 0.0
Downloaded from informs.org by [131.178.125.46] on 20 September 2016, at 09:35 . For personal use only, all rights reserved.

25 9.5 8.6 11.3 1.9 13.0 13.6 17.9 10.9 0.0

30 11.6 10.0 12.8 3.5 13.0 13.2 22.7 13.3 0.0
35 6.1 7.0 10.7 2.4 10.4 11.7 11.5 11.1 0.0
40 6.2 8.1 9.8 2.1 10.3 6.8 23.8 10.8 0.0
45 6.8 7.9 6.1 2.2 14.3 9.4 12.5 9.7 0.0
50 6.2 3.6 7.5 2.4 12.9 11.2 11.8 11.6 0.0
60 0.0 6.7 — 1.5 20.0 9.2 — 9.8 0.0
70 — — — 2.0 11.1 8.6 — 10.0 0.0
80 — — 0.0 1.1 — 9.0 — 7.7 0.0
90 — — — 0.9 — 7.7 — 12.5 0.0

not farther than 16 nodes from the root; this value appears About 40% of them, involving no more than four items,
to be surprisingly robust, at least for all the instances of were solved through the specific procedure (see §4.2),
our experiments, and independent of the size and the whereas for the remaining 60%, involving 5 to 20 items,
class. the full branch-and-bound algorithm was executed.
Tables 2 and 3 give the number of instances solved to Tables 4 through 6 show the average deviation of the
proved optimality and the average CPU time required for lower bounds values Li, i ⫽ 0, 1, 2 computed at the root
the solution, computed over all the solved instances. node of the branch-decision tree, with respect to the opti-
Nearly all the instances with n 聿 30 and 84% of those with mal solution value Z. The deviation is defined as 100(Z ⫺
n 聿 50 were solved to optimality within reasonable com- Li)/Z, i ⫽ 0, 1, 2 and is computed for the solved instances
puting times. In total, we solved more than 63% of the only. In Proposition 3 we proved that L2 dominates both
problems within the given time limit (i.e., 740 out of L0 and L1, but it is interesting to see that also in practice
1,170). Almost all the instances of Classes 4 and 6, where L2 is considerably better than both of the other bounds. In
large items are more frequent, were solved to optimality fact, over all the solved instances, the average deviation of
also for large values of n. On the other hand, the instances L2 is 9.6%, whereas those of L0 and L1 are 28.4% and
of Classes 5, 7, and 9, where the average number of items 14.4%, respectively. Table 7 shows the average deviation
per bin is much higher, turned out to be harder. Indeed, of the best upper bound value U found by algorithms H1
L1 and L2 are clearly more effective if large items are and H2 at the root node with respect to the optimal solu-
present (and cannot improve L0 if all the items are small). tion value. In this case the deviation is defined as 100(U ⫺
Additional tests with instances having similar characteris- Z)/Z, and is again computed for the solved instances only.
tics confirmed this trend. Algorithm ONEBIN is the most It may be noted that the heuristic solutions are generally
time-consuming component: For instances of “average” very good, except for the very difficult “all-fill” instances of
difficulty, such as Class 9 with n ⫽ 40, it took on average Class 9. Over all solved instances, the average deviation of
about 99% of the total CPU time. For the same instances U is 5.3%, whereas the average deviation of U obtained by
we had to determine a total of 33,686 single bin fillings: excluding the instances of Class 9 is 3.3%. Finally, Table 8

Table 7. Average deviation of upper bound U with respect to the optimal solution value.
Class
n 1 2 3 4 5 6 7 8 9
10 0.0 0.0 0.0 0.0 0.0 0.0 5.0 0.0 0.0
15 0.0 0.0 0.0 0.0 3.3 1.7 10.0 6.7 0.0
20 2.0 0.0 4.0 0.0 5.0 3.3 5.0 0.0 6.7
25 1.7 4.7 3.1 0.0 5.8 4.0 3.3 5.8 30.0
30 2.9 3.9 1.2 0.0 4.2 3.7 0.0 4.8 40.0
35 7.9 3.4 3.0 0.0 0.0 9.8 5.4 4.0 40.0
40 7.5 3.7 6.0 0.0 1.2 9.9 1.1 11.1 53.3
45 4.3 2.5 4.1 0.4 2.5 11.1 0.0 8.9 56.7
50 5.5 1.4 3.2 0.8 2.9 11.5 0.0 4.9 66.7
60 0.7 0.7 — 0.6 0.0 6.5 — 7.3 60.0
70 — — — 0.0 0.8 4.9 — 8.0 83.3
80 — — 1.1 0.0 — 4.3 — 3.8 93.3
90 — — — 0.2 — 7.8 — 1.2 103.3
 MARTELLO, PISINGER, AND VIGO / 267
Table 8. Average deviation of upper bound U with respect to lower bound L2.
Class
n 1 2 3 4 5 6 7 8 9
10 8.3 15.0 29.2 2.5 30.0 28.3 48.3 25.0 0.0
15 16.5 18.3 22.0 1.1 47.5 30.7 19.2 23.3 0.0
20 19.2 14.5 27.7 0.8 26.7 20.5 25.8 18.3 6.7
Downloaded from informs.org by [131.178.125.46] on 20 September 2016, at 09:35 . For personal use only, all rights reserved.

25 13.2 14.0 18.7 2.4 23.7 20.2 30.8 21.8 30.0

30 16.8 15.7 16.6 3.9 22.3 20.2 37.5 25.9 40.0
35 15.7 11.6 15.5 2.5 18.1 25.0 33.5 28.1 40.0
40 16.1 14.7 17.3 2.2 34.1 19.3 39.4 28.1 53.3
45 15.6 12.5 12.1 3.2 25.2 23.0 45.6 30.4 56.7
50 17.4 14.4 17.1 3.5 31.6 25.6 33.7 35.2 66.7
60 15.2 15.6 14.0 2.8 33.3 23.5 41.0 23.3 60.0
70 14.9 14.8 15.8 3.6 31.0 24.1 47.2 32.2 83.3
80 17.0 14.9 12.8 2.7 32.6 22.5 37.9 35.2 93.3
90 13.4 14.0 13.8 3.4 30.1 21.3 45.0 32.8 103.3

shows the average deviation of the best upper bound value ——, U. Finke. 1992. Cutting and Packing in Production and
U with respect to the best lower bound value L2, computed Distribution. Physica Verlag, Heidelberg, Germany.
over all instances. ——, G. Scheithauer, J. Terno. 1997. Cutting and packing
(C&P). In Annotated Bibliographies in Combinatorial Op-
timization. M. Dell’Amico, F. Maffioli, and S. Martello
ACKNOWLEDGMENTS (eds.) John Wiley & Sons, Chichester, U.K.
The first and third authors acknowledge Ministero Gehring, M., K. Menscher, M. Meyer. 1990. A computer-
dell’Università e della Ricerca Scientifica e Tecnologica based heuristic for packing pooled shipment containers.
(MURST) and Consiglio Nazionale delle Ricerche (CNR), Eur. J. Oper. Res. 44 277–288.
Italy, for the support of this project. The second author George, J. A., D. F. Robinson. 1980. A heuristic for packing
thanks the EC Network DIMANET for supporting the boxes into a container. Comput. Oper. Res. 7 147–156.
Hadjiconstantinou, E., N. Christofides. 1995. An exact algo-
research by European Research Fellowship No.
rithm for general, orthogonal, two-dimensional knapsack
ERBCHRXCT-94 0429.
problems. Eur. J. Oper. Res. 83 39 –56.
Ibaraki, T. 1987. Enumerative Approaches to Combinatorial
REFERENCES Optimization—Part 2, volume 11, Annals of Operations
Research. Baltzer, Basel, Switzerland.
Berkey, J. O., P. Y. Wang. 1987. Two dimensional finite bin
packing algorithms. J. Oper. Res. Soc. 38 423– 429. Labbé, M., G. Laporte, H. Mercure. 1991. Capacitated vehicle
Bischoff, E. E., M. D. Marriott. 1990. A comparative evalua- routing on trees. Oper. Res. 39 616 – 622.
tion of heuristics for container loading. Eur. J. Oper. Res. Li, K., K.-H. Cheng. 1990. On three-dimensional packing.
44 267–276. SIAM J. Comput. 19 847– 867.
Chen, C. S., S. M. Lee, Q. S. Shen. 1995. An analytical model Martello, S., D. Pisinger, D. Vigo. 1997. The three-
for the container loading problem. Eur. J. Oper. Res. 80 dimensional bin packing problem. Technical Report OR-
68 –76. 97-6, DEIS, University of Bologna, Italy.
Christofides, N., C. Whitlock. 1977. An algorithm for two- ——, P. Toth. 1990a. Knapsack Problems: Algorithms and
dimensional cutting problems. Oper. Res. 25 30 – 44. Computer Implementations. John Wiley & Sons, Chiches-
Chung, F. K. R., M. R. Garey, D. S. Johnson. 1982. On pack- ter, U.K.
ing two-dimensional bins. SIAM J. Algebraic and Discrete ——, ——. 1990b. Lower bounds and reduction procedures
Methods 3(1) 66 –76. for the bin packing problem. Discrete Applied Mathemat-
Coffman, E. G., Jr., M. R. Garey, D. S. Johnson. 1997. Ap- ics 28 59 –70.
proximation algorithms for bin packing: A survey. In Ap- ——, D. Vigo. 1998. Exact solution of the two-dimensional
proximation Algorithms for NP-Hard Problems. D. S. finite bin packing problem. Management Sci. 44 388 –399.
Hochbaum (ed.) PWS Publishing Company, Boston, MA. Pisinger, D. 1997. The container loading problem. In Proceed-
Dell’Amico, M., S. Martello. 1995. Optimal scheduling of ings NOAS’97.
tasks on identical parallel processors. ORSA J. Comput. Scheithauer, G. 1991. A three-dimensional bin packing algo-
7(2) 191–200. rithm. J. Inform. Process. Cybernet. 27 263–271.
Dyckhoff, H. 1990. A typology of cutting and packing prob- ——. 1997. Equivalence and dominance for problems of opti-
lems. Eur. J. Oper. Res. 44 145–159. mal packing of rectangles. Ricerca Operativa 83 3–34.