Introduction to Bin Packing Problems
Fabio Furini
December 8, 2014
Outline
Origins and applications
Applications:
Definition: Bin Packing Problem (BPP)
Solution techniques for the BPP
Heuristic Algorithms
Compact MIP formulation
Stronger MIP formulation
Pseudo-polynomial MIP formulation
Arc-flow Formulation
Dyckhoff Formulation
Bin Packing
Extended Formulations Branch-and-Price Algorithms
Knapsack Problems (KP01)
Set Partitioning Formulation for BPP
Set Covering Formulation for BPP
Column Generation
Branch and Price Algorithm
Branching rule
Fabio Furini | Universit Paris Dauphine LAMSADE
3/33
Bin Packing
Origins and applications
Fabio Furini | Universit Paris Dauphine LAMSADE
4/33
Bin Packing
Applications:
Consider the following problem: determining the smallest number of rolls of a
fixed width that have to be cut in order to satisfy the demand of clients.
filling up containers;
loading trucks with weight capacity constraints;
creating file backups;
placing data on multiple disks;
job scheduling.
Fabio Furini | Universit Paris Dauphine LAMSADE
5/33
Bin Packing
Definition: Bin Packing Problem (BPP)
Fabio Furini | Universit Paris Dauphine LAMSADE
6/33
Bin Packing
Given a positive integer number of bins m of capacity W and a list of n items of
integer sizes w1 , . . . , wn (0 wi W ), the problem is to assign the items to
the bins so that the capacity of the bins is not exceeded and the number of bins
used is minimized
Fabio Furini | Universit Paris Dauphine LAMSADE
7/33
Bin Packing
Theorem (Garey and Johnson (1979))
The BPP is NP-Hard (reduce from PARTITION).
BPP has several real-world applications such as:
Fabio Furini | Universit Paris Dauphine LAMSADE
8/33
Bin Packing
How difficult is the BPP in practice?
Some NP-Hard problems can be solved to optimality for instances of
reasonable size:
TSP thousands of nodes (cutting planes)
BPP up to 1000 items (Branch and Bound, Branch and Price)
BPP and its variants are really difficult from the practical viewpoint.
Fabio Furini | Universit Paris Dauphine LAMSADE
9/33
Bin Packing
Solution techniques for the BPP
Fabio Furini | Universit Paris Dauphine LAMSADE
10/33
Bin Packing
Heuristic Algorithms
First FitAlgorithm: pack the current item into the first nonempty bin in which
it fits. If no such bin exists, pack the current item into an empty bin.
Best FitAlgorithm: pack the current item into the nonempty bin of largest free
space in which it fits. If no such bin exists, pack the current item into an empty
bin.
Fabio Furini | Universit Paris Dauphine LAMSADE
11/33
Bin Packing
Compact MIP formulation
Variables (i = 1, . . . , n
xhi =
1
0
h = 1, . . . , m):
item i goes to bin h
otherwise
min
m
X
yh =
1
0
if bin h is used
otherwise
yh
(1)
h=1
m
xhi = 1
i = 1, . . . , n
(2)
h = 1, . . . , m
(3)
i = 1, . . . , n, h = 1, . . . , m
(4)
h = 1, . . . , m
(5)
h=1
n
wi xhi W y h
i=1
xhi {0, 1}
h
y {0, 1}
Fabio Furini | Universit Paris Dauphine LAMSADE
12/33
Bin Packing
Question 1: write the Model ((1),(5)) for the following example: 2 bins
and 3 items, W = 4, w1 = 1, w2 = 3, w3 = 4.
Question 2: try to figure out the optimal solution value of its Linear
Programming relaxation and a possible solution vector of the variable
values.
Question 3: Cutting Stock Problem try to extend the Model ((1),(5) in
case each item has a demand of di copies (i = 1, . . . , n)
Fabio Furini | Universit Paris Dauphine LAMSADE
13/33
Bin Packing
Model ((1),(5)) is a weak! The Linear Relax has a useless value of:
Pn
LR =
i=1 wi
y h = LR/m
xhi
= 1/m
(6)
h = 1, . . . , m
(7)
i = 1, . . . , n, h = 1, . . . , m
(8)
Huge symmetry!! for each integer solution of value k, there exist
equivalent solutions.
Fabio Furini | Universit Paris Dauphine LAMSADE
m
k k!
14/33
Bin Packing
Stronger MIP formulation
a feasible solution of value k (k < m)
Variables (i = 1, . . . , n;
min
h = 1, . . . , k):
yh
(9)
h=1,...,k
xhi = 1
i = 1, . . . , n
(10)
h = 1, . . . , k
(11)
xhi y h
i = 1, . . . , n, h = 1, . . . , k
(12)
xhi
{0, 1}
i = 1, . . . , n, h = 1, . . . , k
(13)
y {0, 1}
h = 1, . . . , k
(14)
h=1,...,k
n
X
wi xhi W y h
i=1
Fabio Furini | Universit Paris Dauphine LAMSADE
15/33
Bin Packing
Pseudo-polynomial MIP formulation
Fabio Furini | Universit Paris Dauphine LAMSADE
16/33
Bin Packing
Arc-flow Formulation
Cutting pattern corresponds to a path in an acyclic directed graph G =
(V, A), with V = 0, 1, . . . , W as its set of W + 1 vertices, which define
positions in the stock sheet, and
A = {(a, b) : 0 a < b W, b a = wi , i = 1, . . . , n}
as its set of arcs. Minimum flow problem, where:
variables ab correspond to the flow in arc (a, b), (item number of
width b a placed at a units from the beginning of a bin
variable corresponds to the total flow through the graph, and can
be seen as the return flow from vertex W to vertex 0.
Fabio Furini | Universit Paris Dauphine LAMSADE
17/33
Bin Packing
min
(15)
X
ab
ba
(a,b)A
(a,b)A
X
if b=0
if b=W
if b=1,. . . ,W-1
cc+wi 1
(16)
i = 1, . . . , n (17)
(c,c+wi )A
ab R+
Fabio Furini | Universit Paris Dauphine LAMSADE
(a, b) A (18)
18/33
Bin Packing
Example: graph associated with an instance with bins of capacity W = 7
and items of sizes 5, 3, 2, respectively:
Fabio Furini | Universit Paris Dauphine LAMSADE
19/33
Bin Packing
Dyckhoff Formulation
Residual Bins (RB): each time a bin of width W is cut in order to produce
an item i of length wi , a residual bin of size W wi is obtained, which
can be further used to produce additional items. m
is the number of all
the possible Residual Bins.
Decision variables:
iz =
if item i is cut in residual bin z
otherwise.
Fabio Furini | Universit Paris Dauphine LAMSADE
20/33
Bin Packing
aizt =
if RB t results from cutting item type i from the RB z
otherwise.
Fabio Furini | Universit Paris Dauphine LAMSADE
21/33
Bin Packing
min
n
X
i0
i=1
m
iz
z=0
m
X
n
X
(19)
1
aizt iz
z=1 i=1
iz R+
n
X
it
i = 1, . . . , n
(20)
t = 1, . . . , m
(21)
z = 0, . . . , m
(22)
i=1
i = 1, . . . , n
Fabio Furini | Universit Paris Dauphine LAMSADE
22/33
Bin Packing
Extended Formulations Branch-and-Price
Algorithms
Fabio Furini | Universit Paris Dauphine LAMSADE
23/33
Bin Packing
Knapsack Problems (KP01)
Given:
n items, with pj profit and wj weight of item j (j = 1, . . . , n)
1 container (knapsack) of capacity W
select a subset of the items so that the sum of the profits is maximum
and the sum of the weights does not exceed the capacity W .
N P-Hard problem, pj and wj integer, wj c,
n
X
wj > W
j=1
Fabio Furini | Universit Paris Dauphine LAMSADE
24/33
Bin Packing
max
n
X
i=1
n
X
pi xi
wi xi W
(23)
i = 1, . . . , n
(24)
i = 1, . . . , n
(25)
i=0
xi {0, 1}
Fabio Furini | Universit Paris Dauphine LAMSADE
25/33
Bin Packing
Set Partitioning Formulation for BPP
S = {s N : s is a KP 01 solution} .
(
xs =
1 if KP01 s is in the solution
0 otherwise
min
xs
(26)
sS
xs = 1
i = 1, . . . , n
(27)
sS
(28)
sS:is
xs {0, 1}
Fabio Furini | Universit Paris Dauphine LAMSADE
26/33
Bin Packing
Set Covering Formulation for BPP
min
xs
(29)
sS
xs 1
i = 1, . . . , n
(30)
sS
(31)
sS:is
xs {0, 1}
S can be defined as the family of all maximal KP01 solutions.
The LP of this formulation leads to tight lower bounds and avoids symmetry
The number of maximal KP01 solutions is exponential in the number of items n
(we need column generation and Branch-and-Price).
Fabio Furini | Universit Paris Dauphine LAMSADE
27/33
Bin Packing
Question 6: explicitly write the Set Partitioning and the Set Covering
formulation of the following instance: bins of capacity W = 7 and items
of sizes 5, 3, 2.
Question 7: write the dual of these models and discuss how they change
in case of having only a subset of the original variables
Fabio Furini | Universit Paris Dauphine LAMSADE
28/33
Bin Packing
Primal
min
n variables
m constraints
constraint ai x bi
constraint ai x bi
constraint ai x = bi
variable xj 0
variable xj 0
variable xj R
Dual
max
n constraints
m variables
variable ui 0
variable ui 0
variable ui R
constraint aTj u cj
constraint aTj u cj
constraint aTj u = cj
Fabio Furini | Universit Paris Dauphine LAMSADE
29/33
Bin Packing
Column Generation
min
xs
(32)
max
sS
xs 1
iN
(33)
sS:is
xs 0
(35)
iN
i 1
sS
(36)
iN
(37)
is
sS
(34)
i 0
We solve the model with a subset S 0 of the variables. Given an optimal
solution (x , ) of the restricted master problem, does it exist a set s S:
X
i > 1
(38)
is
Fabio Furini | Universit Paris Dauphine LAMSADE
30/33
Bin Packing
Question 8: write a MIP model which allow the separation of the family
of constraints (38)
Question 9: write this MIP model for the following instance: bins of
capacity W = 7 and items of sizes 5, 3, 2.
Fabio Furini | Universit Paris Dauphine LAMSADE
31/33
Bin Packing
Branch and Price Algorithm
Column generation methods: necessary when the number of variables of a
Linear Program is exponential
Branch-and-Price
Impose a subset of the variables
1 Solve the LP and get the current solution x ,
2 If some constraints in the Dual are violated by x , , add the columns to the
LP and go to 1
3 x is optimal and feasible for the LP (possibly fractional)
Branch on a feasible disjunction for the problem and go to 1
Fabio Furini | Universit Paris Dauphine LAMSADE
32/33
Bin Packing
Branching rule
Basic idea (Ryan/Foster branching): at each node of the search tree we
select two items i and j N . Then:
1) Same bin create a super item merging i and j,
2) Different bins create an extra constraints:
xi + xj 1
In both cases 1) and 2) the resulting pricing problem is still a KP01, with
1) a super item forced to be packed together
2) an extra constraints not allowed to be packed together
Fabio Furini | Universit Paris Dauphine LAMSADE
33/33
Questions?
