Bin Packing with Linear Usage Costs
Hadrien Cambazarda , Deepak Mehtab,, Barry O’Sullivanb , Helmut Simonisb
a

G-SCOP, Université de Grenoble; Grenoble INP; UJF Grenoble 1; CNRS, France
b
Insight Centre for Data Analytics, Universiy College Cork, Ireland

arXiv:1509.06712v1 [cs.DS] 22 Sep 2015

Abstract
Bin packing is a well studied problem involved in many applications. The classical bin packing
problem is about minimising the number of bins and ignores how the bins are utilised. We focus
in this paper, on a variant of bin packing that is at the heart of efficient management of data
centres. In this context, servers can be viewed as bins and virtual machines as items. The efficient
management of a data-centre involves minimising energy costs while ensuring service quality. The
assignment of virtual machines on servers and how these servers are utilised has a huge impact
on the energy consumption. We focus on a bin packing problem where linear costs are associated
to the use of bins to model the energy consumption. We study lower bounds based on Linear
Programming and extend the bin packing global constraint with cost information.
Keywords: Bin Packing, Constraint Programming

1. Introduction
Data centres are a critical and ubiquitous resource for providing infrastructure for banking,
Internet and electronic commerce. They use enormous amounts of electricity, and this demand is
expected to increase in the future. For example, a report by the EU Stand-by Initiative stated that
in 2007 Western European data centres consumed 56 Tera-Watt Hours (TWh) of power, which
is expected to almost double to 104 TWh per year by 2020.1 Energy consumption is one of the
most important sources of expense in data centres and energy efficiency is at the core of their
competitive advantage. The ongoing increase in energy prices (a 50% increase is forecasted by the
French senate by 2020) and the growing market for cloud computing are the main incentives for
the design of energy efficient centres. Minimising energy consumption is not only important for
economic reason but also for environmental reason. The consulting firm McKinsey reported that
only 6-12% of electricity used by data centres can be attributed to the performance of productive
computation [10]. Hence, there is a lot of scope for reducing the carbon footprint of data centres
by utilising servers more efficiently.
Email addresses: hadrien.cambazard@grenoble-inp.fr (Hadrien Cambazard),
deepak.mehta@insight-centre.org (Deepak Mehta), barry.osullivan@insight-centre.org (Barry
O’Sullivan), helmut.simonis@insight-centre.org (Helmut Simonis)
1

http://re.jrc.ec.europa.eu/energyefficiency/html/standby_initiative_data_centers.htm

Preprint submitted to Elsevier

September 23, 2015

We study a problem associated with the EnergeTIC2 project which was accredited by the
French government (FUI) [7] that brought together four companies (Bull, Business & Decision
Eolas, Schneider Electric, UXP), several academic partners (G2Elab, G-SCOP, LIG), and a startup
company (Vesta-System). The objective is to control the energy consumption of a data center and
ensure that it is consistent with application needs, economic constraints and service level agreements. We focus on how to reduce energy cost by taking cpu requirements of client applications,
IT equipment and virtualisation techniques into account.
The EnergeTIC optimisation problem for energy-cost aware data centre assignment systems is
about allocating virtual machines demands to servers where the energy cost per unit of computation can vary between different servers.
The problem can be defined by a set of servers and a set of virtual applications to be run
on those servers. Each server is associated with a set of available resources, e.g. CPU, RAM,
DISK etc. Each virtual application is associated with a set of required resource values. The
solution of the problem is an assignment of virtual machines to servers which respects a set of hard
constraints. The objective is to take advantage of differences in energy costs across the servers,
the requirements of virtual applications, and consolidate machine workload to ensure that servers
are well utilised so that energy costs can be reduced.
A combinatorial optimisation model for the problem of loading servers to a desired utilisation
level has, at its core, a variant of bin packing (BP) problem [18]. In such a model each server
is represented by a bin with a capacity equal to the amount of resource available. Bin packing
is a very well studied NP-Hard problem. In the present context, energy consumption cannot be
accurately modelled by only considering the number of active servers since the energy cost of a
server is a function of the workload. Furthermore, servers require energy not only to run processes
but also when they are idle which must be considered in the energy management process. We
focus on an extension of bin packing problem with linear costs associated with the use of bins in
Section 2. This is a key sub-problem of the application domain and we show how to handle it efficiently with Constraint Programming (CP). We study lower bounds based on Linear Programming
and extend the bin packing global constraint with cost information. The present work has been
partially published in [3] which focus on the real-life application.
2. Bin Packing with Linear Usage Costs
In this section we consider a variant of the Bin Packing problem (BP) [18], which is the key
sub-problem of the application investigated here. We denote by S = {w1 , . . . , wn } the integer sizes
of the n items such that w1 ≤ w2 ≤ . . . wn . A bin j is characterised by an integer capacity C j , a
non-negative fixed cost f j and a non-negative cost c j for each unit of used capacity. We denote by
B = {{C1 , f1 , c1 }, . . . , {Cm , fm , cm }} the characteristics of the m bins. A bin is used when it contains
at least one item. Its cost is a linear function f j + c j l j , where l j is the total size of the items in bin j.
P
The total load is denoted by W = ni=1 wi and the maximum capacity by Cmax = max1≤ j≤mC j . The
problem is to assign each item to a bin subject to the capacity constraints so that we minimise the
2

Minalogic EnergeTIC is a Global competitive cluster located in Grenoble France and fostering research-led innovation in intelligent miniaturised products and solutions for industry.

2

sum of the costs of all bins. We refer to this problem as the Bin Packing with Usage Cost problem
(BPUC). BP is a special case of BPUC where all f j are set to 1 and all c j to 0. The following
example shows that a good solution for BP might not yield a good solution for BPUC.
Example 1. In Figure 1, Scenario 1, B ={(9,0,1),(3,0,2),(3,0,2),(3,0,2),(3,0,2)} and S = {2,2,2,2,3,3,3}.
Notice that ∀ j, f j = 0. The packing (P1 ) : {{2,2,2,2}, {3}, {3}, {3}, {}} is using the minimum number
of bins and has a cost of 26 (8*1 + 3*2 + 3*2 + 3*2). The packing (P2 ): {{3,3,3}, {2}, {2}, {2}, {2}}
is using one more bin but has a cost of 25 (9 + 2*2 + 2*2 + 2*2 + 2*2). Here, (P2 ) is better than
(P1 ) and using the minimum number of bins is not a good strategy. Now change the last unit cost
to c5 = 3 (see Figure 1, Scenario 2). The cost of (P1 ) remains unchanged since it does not use bin
number 5 but the cost of (P2 ) increases to 27, and thus (P1 ) is now better than (P2 ).

Figure 1: Example of optimal solutions in two scenarios of costs. In Scenario 1, the best solution has no waste on the
cheapest bin. In Scenario 2, it does not fill completely the cheapest bin.

Literature Review. A first relevant extension of BP for the current paper is called Variable Size
Bin-Packing, where bins have different capacities and the problem is to minimise the sum of the
wasted space over all used bins [13]. It can be seen as a special case of BPUC where all f j = C j
and c j = 0. Recent lower bounds and an exact approach are examined in [11]. A generalisation
to any kind of fixed cost is presented in [4], which can be seen as a special case of BPUC where
all c j = 0. Concave costs of bin utilisation studied in [12] are more general than the linear cost
functions of BPUC. However [12] does not consider bins of different capacities and deals with
the performance of classical BP heuristics whereas we are focusing on lower bounds and exact
algorithms. Secondly, BP with general cost structures have been introduced in [1] and studied
in [8]. The authors investigated BP with non-decreasing and concave cost functions of the number
of items put in a bin. They extend it with profitable optional items in [2]. Their framework can
model a fixed cost but does not relate to bin usage.
3. Basic Formulation and Lower Bounds of BPUC
Numerous linear programming models have been proposed for BP [6]. We first present a
formulation for BPUC. For each bin a binary variable y j is set to 1 if bin j is used in the packing,
and 0 otherwise. For each item i ∈ {1, . . . , n} and each bin j ∈ {1, . . . , m} a binary variable xi j is set
to 1 if item i is packed into bin j, and 0 otherwise. We add non-negative variables l j representing

3

the load of each bin j. The model is as follows:
P
Minimize
z1 = mj=1 ( f j y j + c j l j )
Pm
(1.1)
x = 1,
Pnj=1 i j
(1.2)
i=1 wi xi j = l j ,
(1.3)
l j ≤ C jy j,
(1.4)
xi j ∈ {0, 1}, y j ∈ {0, 1}, l j ≥ 0

∀i ∈ {1, . . . , n}
∀ j ∈ {1, . . . , m}
∀ j ∈ {1, . . . , m}
∀ j ∈ {1, . . . , m}, ∀i ∈ {1, . . . , n}

(1)

Constraint (1.1) states that each item is assigned to one bin whereas (1.2) and (1.3) enforce the
capacity of the bins. We now characterise the linear relaxation of the model. Let r j = f j /C j + c j be
a real number associated with bin j. If bin j is filled completely, r j is the cost of one unit of space
in bin j. We sort the bins by non-decreasing r j : ra1 ≤ ra2 ≤ . . . ≤ ram ; a1 , . . . , am is a permutation
P
of the bin indices 1, . . . , m. Let k be the minimum number of bins such that kj=1 Ca j ≥ W.
Proposition 1. Let z∗1 be the optimal value of the linear relaxation of the formulation (1). We have
P
Pk−1
z∗1 ≥ Lb1 with Lb1 = k−1
j=1 C a j ra j + (W −
j=1 C a j )rak .
P
P
l
Proof 1. z∗1 = mj=1 ( f j y j + c j l j ) ≥ mj=1 ( f j Cjj + c j l j ) because of the constraint l j ≤ C j y j , so z∗1 ≥
Pm
Pm f j
Pm
P
j lj = W
j=1 ( C j +c j )l j ≥
j=1 r j l j . Lb1 is the quantity minimising
j=1 r j l j under the constraints
where each l j ≤ C j . To minimise the quantity we must split W over the l j related to the smallest
P
coefficients r j . Hence, z∗1 ≥ mj=1 r j l j ≥ Lb1 .

Lb1 is a lower bound of BPUC that can be computed in O(mlog(m) + n). Also notice that Lb1 is
the bound that we get by solving the linear relaxation of formulation (1).
Proposition 2. Lb1 is the optimal value of the linear relaxation of the formulation (1).
P
Proof 2. For all j < k, we set each ya j to 1 and la j to C j . We fix lak to (W − k−1
j=1 C a j ) and yak to
lak /Cak . For all j > k we set ya j = 0 and la j = 0. Constraints (1.3) are thus satisfied. Finally we fix
la

xi,a j = Wj for all i, j so that constraints (1.2) and (1.1) are satisfied. This is a feasible solution of
the linear relaxation of (1) achieving an objective value of Lb1 . We have, therefore, Lb1 ≥ z∗1 and
consequently z∗1 = Lb1 from Proposition 1.

Adding the constraint xi j ≤ y j for each item i and bin j, strengthens the linear relaxation only if
W < Cak . Indeed, the solution given in the proof is otherwise feasible for the constraint, (∀ j <
la
la
la
k, xi,a j = Wj ≤ ya j = 1 and for j = k we have Wk ≤ Cak if W ≥ Cak ).
k

Dominance and symmetries.. Formulation (1) can be used to solve the problem exactly and strengthened to take some bin and item symmetries into account. Typically, if bins i and j are such that
fi ≤ f j , ci ≤ c j and Ci ≥ C j then bin i is said to dominate bin j and the constraints y j ≤ yi as well
as l j ≤ li can be added to rule out some dominated solutions. Suppose now that we have k items
that have the same size, any permutation of the items in a feasible solution remains feasible and
have the same overall cost. A simple way to break this symmetry is to replace for each bin j, the
0
k variables xi j ∈ {0, 1} corresponding to the identical items by a variable x j ∈ {0, . . . , k} giving the
4

P 0
number of the k items assigned to j (and adding j x j = k). We also perform in practice another
simple pre-processing by tightening the capacities of the bins using dynamic programming. Given
the item sizes and for each bin i, one can compute efficiently (when Ci is sufficiently small) the
largest integer less than or equal to Ci that is also equal to the sum of a subset of S .
4. Two Extended Formulations of BPUC
The Cutting Stock Model. The formulation of Gilmore and Gomory for the cutting stock prob0
lem [9] can be adapted for BPUC. The items of equal size are now grouped and for n ≤ n different
0
0
sizes we denote the number of items of sizes w1 , . . . , wn0 by q1 , . . . , qn0 respectively. A cutting pattern for bin j is a combination of item sizes that fits into bin j using no more than qd items of size
0
0
wd . In the i-th pattern of bin j, the number of items of size wd that are in the pattern is denoted gdi j .
Let I j be the set of all patterns for bin j. The cost of the i-th pattern (assumed to be non empty)
P0
0
of bin j is therefore equal to coi j = f j + ( nd=1 gdi j wd )c j . The cutting stock formulation is using a
variable pi j for the i-th pattern of bin j:
P P
Minimize
z2 = mj=1 i∈I j coi j pi j
Pm P
0
(2.1)
g p = qd
∀d ∈ {1, . . . , n }
P j=1 i∈I j di j i j
(2.2)
∀ j ∈ {1, . . . , m}
i∈I j pi j = 1
(2.3)
pi j ∈ {0, 1}
∀ j ∈ {1, . . . , m}, i ∈ I j

(2)

Constraint (2.1) states that each item has to appear in a pattern (thus in a bin) and (2.2) enforces
one pattern to be designed for each bin (convexity constraints). A pattern pi j for bin j is valid if
Pn0
0
d=1 gdi j wd ≤ C j and all gdi j are integers such that qd ≥ gdi j ≥ 0. The sets I j have an exponential
size so the linear relaxation of this model can be solved using column generation. The pricing step
is a knapsack problem that can be solved efficiently by dynamic programming if the capacities
are small enough. The pricing problem for bin j can be written as follows (where πd is the dual
variable associated to the d-th constraint (2.1) and λ j is the dual variable related to j-th constraint
(2.2)):
P0
P0
0
Minimize
f j y + ( nd=1 gd wd )c j − nd=1 πd gd − λ j
Pn0
0
d=1 gd wd ≤ C j y
0
gd ∈ {0, 1, . . . , qd }
∀d ∈ {1, . . . , n }
y ∈ {0, 1}
In practice, we solve the pricing problem using Dynamic Programming in O(nC j ).
The Arc-Flow Model. Carvalho introduced an elegant Arc-Flow model for BP [5, 6]. His model
explicitly uses each unit of capacity of the bins. In the following we show how to adapt it for
BPUC. Consider a multi-graph G(V, A), where V = {0, 1, ..., Cmax } ∪ {F} is the set of Cmax + 2 nodes
labelled from 0 to Cmax and a final node labelled F, and A = I ∪ J is the set of two kinds of edges.
An edge (a, b) ∈ I between two nodes labelled a ≤ Cmax and b ≤ Cmax represents the use of an item
of size b − a. An edge of (a, F) ∈ J for each bin j represents the usage a of the bin j, and therefore
a ≤ C j . An example of such a graph is shown in Figure 3(a). Notice that this formulation has
5

Figure 2: (a) An example of the graph underlying the Arc-Flow model for S = {2, 2, 3, 5}, B =
{{3, 1, 2}, {4, 3, 1}, {7, 3, 3}} so that Cmax = 7. A packing is shown using a dotted line: {3} is put in the first bin for
a cost of 7, {2, 2} is in the second bin for a cost of 7 and {5} in the last bin for a cost of 18. (b) The graph underlying
the Arc-Flow model after the elimination of symmetries.

symmetries since a packing can be encoded by many different paths. Some reduction rules were
given by Carvalho [5], which help in reducing such symmetries (see Figure 3(b)).
BPUC can be seen as a minimum cost flow between 0 and F with constraints enforcing the
number of edges of a given length used by the flow to be equal to the number of items of the
corresponding size. We have variables xab for each edge (a, b) ∈ I as well as variables ya j for each
pair of bin j ∈ {1, . . . , m} and a ∈ V. The cost of using an edge (a, F) ∈ J for bin j with a > 0 is
coa j = f j + a · c j and co0 j = 0. The model is as follows:
P P max
Minimize
z3 = mj=1 k=C
cok j yk j
k=0
(
P
P
Pm
0
∀b ∈ {1, 2, . . . , Cmax }
(3.1)
x
−
x
−
y
=
(a,b)∈A ab
(b,c)∈A bc
j=1 b j
−m for b = 0
PC j
(3.2)
y =1
∀ j ∈ {1, . . . , m}
Pa=0 a j
0
0
0 = q
(3.3)
x
∀d ∈ {1, 2, . . . , n }
d
(k,k+wd )∈A k,k+wd
(3.4) ya j = 0
∀( j, a) ∈ {1, . . . , m} × {C j + 1, . . . , Cmax }
(3.5) xab ∈ N
∀(a, b) ∈ A
(3.6) ya j ∈ {0, 1}
∀( j, a) ∈ {1, . . . , m} × {0, . . . , Cmax }

(3)

Constraint (3.1) enforces the flow conservation at each node, and Constraint (3.2) states that each
bin should be used exactly once. Constraint (3.3) ensures that all the items are packed, while
Constraint (3.4) enforces that bin j is not used beyond its capacity C j . A solution can be obtained
0
again by decomposing the flow into paths. The number of variables in this model is in O((n + m) ·
0
Cmax ) and the number of constraints is O(Cmax + m + n ). Although its LP relaxation is stronger
than that of Model (1), it remains dominated by that of Model (2).
Proposition 3. z∗3 ≤ z∗2 . The optimal value of the linear relaxation of (3) is less than the optimal
value of the linear relaxation of (2).
Proof 3. Let (p∗ ) be a solution of the linear relaxation of (2). Each pattern p∗i j is mapped to a
path of the Arc-Flow model. A fractional value p∗i j is added on the arcs corresponding to the item
sizes of the pattern (the value of the empty patterns for which all gdi j = 0 is put on the arcs y0 j ).
The flow conservation (3.1) is satisfied by construction, so is (3.2) because of (2.2) and so are the
demand constraints (3.3) because of (2.1). Any solution of (2) is thus encoded as a solution of (3)
for the same cost so z∗3 ≤ z∗2 .

6

Proposition 4. z∗2 can be stronger than z∗3 i.e. there exist instances such that z∗2 > z∗3 .
Proof 4. Consider the following instance: S = {1, 1, 2} and B = {{3, 1, 1}, {3, 4, 4}}. Two items of
0
0
0
size 1 occurs so that n = 2, q1 = 2, q2 = 1 corresponding to w1 = 1, w2 = 2. The two bins have
to be used and the first dominates the second (the maximum possible space is used in bin 1 in any
optimal solution) so the optimal solution is the packing {{2, 1}, {1}} (cost of 12). Let’s compute the
value of z∗2 . It must fill the first bin with the pattern [g111 , g211 ] = [1, 1] for a cost of 4. Only three
possible patterns can be used to fill the second bin: [0, 0], [1, 0] and [2, 0] (a valid pattern pi2 is
such that g1i2 ≤ 2). The best solution is using [g112 , g212 ] = [2, 0] and [g122 , g222 ] = [0, 0] taking
both a 0.5 value to get a total cost z∗2 = 4 + 6 = 10. The Arc-Flow model uses a path to encode the
same first pattern [1,1] for bin 1. But it can build a path for bin 2 with a 31 unit of flow taking three
consecutive arcs of size 1 to reach a better cost of 13 ∗ 16 ≈ 5, 33. This path would be a pattern
[3,0] which is not valid for (2). So z∗3 ≈ 9.33 and z∗2 > z∗3 .

0

The Arc-Flow model may use a path containing more than qd arcs of size wd with a positive
flow whereas no such patterns exist in (3) because the sub-problem is subject to the constraint
0 ≤ gdi j ≤ qd . The cutting stock formulation used in [5] ignores this constraint and therefore the
bounds are claimed to be equivalent.
5. Extending the Bin Packing Global Constraint
A bin packing global constraint was introduced for constraint programming by [17] and discussions about its filtering can be found in [16, 14]. We present an extension of this global constraint
to handle BPUC. The scope and parameters are as follows:
BinPackingUsageCost([x1 , . . . , xn ], [l1 , . . . , lm ], [y1 , . . . , ym ], b, z, S , B)
Variables xi ∈ {1, . . . , m}, l j ∈ [0, . . . , C j ] and b ∈ {1, . . . , m} denote the bin assigned to item i,
the load of bin j, and the number of bins used, respectively. These variables are also used by the
BinPacking constraint. Variables yi ∈ {0, 1} and z ∈ R are due to the cost. They denote whether bin
j is open, and the cost of the packing. The last two arguments refers to BPUC and give the size of
the items as well as the costs (fixed and unit). In the following, x (resp. x) denotes the lower (resp.
upper) bound of variable x.
Cost-based Propagation using Lb1 . The characteristics of the bins of the restricted BPUC prob0
lem based on the current state of the domains of the variables is denoted by B , and defined by
0
0
0
0
0
0
0
B = {{C1 , f1 , c1 }, . . . , {Cm , fm , cm }} where C j = l j − l j is the remaining capacity, and f j is the re0
maining fixed cost f j = (1 − y j ) f j that is set to 0 if the bin is known to be open. The total load
P
0
that remains to be allocated to the bins is denoted W = W − mj=1 l j . Notice that we use the lower
bounds of the loads rather than the already packed items. We assume it is strictly better due to the
reasoning of the bin packing constraint.

7

Lower bound of z. The first propagation rule is the update of the lower bound of z denoted by z.
The bound is computed by summing the cost due to open bins and minimum loads with the value
of Lb1 on the remaining problem. It gives a maximum possible increase in cost denoted by gap:
P
0
0
0
0
0
z ← max( z, Lb1 );
gap = z − Lb1
Lb1 = mj=1 (l j c j + y j f j ) + Lb1 (W , B );
(4)
Bounds of the load variables. We use the notation L j to denote the units of space used by
0
Lb1 on bin a j . The bins a1 , . . . , ak−1 are fully used so ∀ j < k, L j = Ca j , for bin ak we have
P
0
0
00
Lk = W − k−1
j=1 C a j and ∀ j > k, L j = 0. We define the bin packing problem B obtained by
0
0
excluding the space supporting the lower bound Lb1 (W , B ). The resulting bins are defined as
00
00
0
00
0
00
00
0
00
0
B = {{C1 , f1 , c1 }, . . . , {Cm , fm , cm }} where Ca j = 0 for all j < k, Cak = Cak − Lk and Ca j = Ca j for
all j > k. Lower and upper bounds of loads are adjusted with rules (5).
Let q−a j be the largest quantity that can be removed from a bin a j , with j ≤ k, and put at the
other cheapest possible place without overloading z. Consequently, when j < k, q−a j is the largest
00
value in [0, L j ] such that (Lb1 (q−a j , B ) − q−a j ra j ) ≤ gap. When j = k, the same reasoning can be
00
00
done by setting Cak = 0 in B .
0
Similarly, let q+a j be the largest value in [0, Ca j ] that can be put on a bin a j , with j ≥ k, without
0
triggering a contradiction with the remaining gap of cost. q+a j is thus the largest value in [0, Ca j ]
0
0
0
0
such that (q+a j ra j − (Lb1 (W , B ) − Lb1 (W − q+a j , B ))) ≤ gap.
∀ j ≥ k, la j ← la j + q+a j .

∀ j ≤ k, la j ← la j + L j − q−a j ;

(5)

Channelling. The constraint ensures two simple rules relating the load and open-close variables (a
bin of zero load can be open): y j = 0 =⇒ l j = 0 and l j > 0 =⇒ y j = 1.
Bounds of the open-close variables. The propagation rule for l j can derive l j > 0 from (5), which
in turn (because of the channelling between y and l) will force a bin to open i.e. ya j ∈ {0, 1} will
change to ya j = 1. To derive that a y j has to be fixed to 0, we can use Lb1 similarly to the reasoning
presented for the load variables (checking that the increase of cost for opening a bin remains within
the gap).
Tightening the bounds of the load variables can trigger the existing filtering rules of the bin
packing global constraint thus forbidding or committing items to bins. Notice that items are only
increasing the cost indirectly by increasing the loads of the bins because the cost model is defined
by the state of the bins (rather than the items). The cost-based propagation on x is thus performed
by the bin packing global constraint solely as a consequence of the updates on the bin related
variables, i.e. l and y.
Filtering the load variables with dynamic programming. Another filtering rule based on dynamic
programming can be added to the Bin-Packing global constraint. We can simply update l j (resp.
l j ) to the smallest (resp. largest) integer greater than (resp. less than) or equal to the current value
of l j (resp. l j ) that can be reached with the remaining items that can still go on bin j. We can
solve this problem by dynamic programming (taking into account the items already assigned to j).
This is generally very costly in practice and is not performed by default by the bin-packing global
8

Figure 3: Visualisation of the lower bound Lb1 and optimal solution for the instance of example 2. The bins have
been sorted by increasing r.

constraint. Nevertheless, in this case, one can notice that Lb1 strongly relies on the accuracy of
l j and l j and we observed that it can help significantly in practice for some hard instances. This
technique has been originally proposed by [19] for knapsack constraints.
Example 2. Let’s consider the following instance: B ={(9,9,5), (3,1,5), (7,14,3), (5,1,10), (12,12,10)}
and S = {3,5,5,5}. The total load is therefore W = 18 and the values or r j sorted increasingly are
r3 = 14/7 + 3 = 5 < r2 = 5.33 < r1 = 6 < r4 = 10.2 < r5 = 11. The lower bound is therefore
Lb1 = 7 × 5 + 3 × 5.33 + 8 × 6 = 99. Figure 3 is visualising Lb1 and shows the optimal solution.
Propagation on the bounds of the load variables by dynamic programming is not performed here
for the illustrative purposes.
Assuming that we have an upper bound z of value 130, the gap is therefore initially equal to
130 - 99 = 31. Initially Lb01 = Lb1 as W 0 = W and B0 = B. Afterwards, the propagation is able to
deduce l3 = l1 = 1 as well as l5 = 6 as illustrated on the left of Figure 4. Indeed l3 = 0 would lead
to a lower bound of 3 × 5.33 + 9 × 6 + 5 × 10.2 + 1 ∗ 11 = 132 thus overloading z. Similarly l1 = 0
would give Lb1 = 135 > 130 and with l5 = 7 we get Lb1 = 134 > 130. At this stage we know that
bins 3 and 1 are open in any solution of cost less than 130. This is affecting the propagation as
0
the fixed cost of bins 1 and 3 are now included in Lb1 and propagation is strengthened. The cost
due to open bins is 9 + 14 = 23 and due to lower bounds of loads of bins 1 and 3 is 5 + 3 = 8.
Consequently, B0 = {(8, 0, 5), (3, 1, 5), (6, 0, 3), (5, 1, 10), (6, 12, 10)} and W 0 = 16. Therefore, the
r values are now ranked: r3 = 3 < r1 = 5 < r2 = 5.33 < r4 = 10.2 < r5 = 12. Notice that the
ordering on bins have changed. The new value of Lb1 is 6 × 3 + 8 × 5 + 2 × 5.33 = 68.66 and thus
the new value of Lb01 is 99.66. When the fix point is reached we know that l3 = l1 = 3 as well as
l5 = 3.
Let’s now add the propagation using dynamic programming (l3 would typically be reduce to
5). The lower bound observed at the root node is 119.66 whereas the one obtained by linear
programming i.e. with formulation (1) (including the initial tightening of the capacities by dynamic
programming) is 114.4.
Algorithms and Complexity. Assuming that B and W are available, Lb1 (W , B ) can be com0

9

0

0

0

Upper bound = 130
Update upper bounds
Update lower bounds
9
6
8

7
1

3
5

3

3

7

5

9

3

1

0
6

5.33

10.2

11

3

5

2
5.33

10.2

12

Fix point

Step 1

Figure 4: Propagation of lower and upper bounds of the load variables. The state of the domains at the end of the first
iteration is depicted on the left. The lower bounds of l1 and l3 are increased to 1 and the upper bound of l5 is decreased
to 6. The state of the domains when the fix point is reached is shown on the right.
0

puted in O(m log(m)) time. Firstly we compute the r j values corresponding to B for all bins.
Secondly, we sort the bins in non-decreasing r j . Finally, the bound is computed by iterating over
0
0
the sorted bins and the complexity is dominated by the sorting step. After computing Lb1 (W , B ),
the values a j (the permutation of the bins) such that ra1 ≤ ra2 ≤ . . . ≤ ram are available as well as
P
0
0
the critical k and Lk = W − k−1
j=1 C . The update of la j and la j can then be done in O(m) as shown
in Figure 5. Notice that this process can be repeated until a fix point is reached.
Algorithm UpdateMinimumLoad of Figure 5 is used to update the lower bounds of the load
variables for each bin a j such that ra j ≤ rak . Recall that k is the number of bins supporting the
lower bound Lb1 . If j < k (resp. j = k) then the algorithm tries to find the largest quantity, denoted
by q−a j , that can be removed from the bin a j and can be put on the bins ab , where b ≥ k (resp.
b ≥ k + 1), such that the increment in the cost remains smaller than the gap (Lines 4–10). The
algorithm loops over the bins as long as the q−a j has not reached its maximum amount on bin a j
i.e. L j and the gap has not been overloaded. When the increment in cost exceeds the gap then the
minimum load if known. Similarly, UpdateMinimumLoad of Figure 5 is used to update the upper
bounds of the load variables for each bin a j such that ra j ≥ rak .
5.1. Dominance and symmetries.
The dominance and symmetries previously mentioned can be similarly eliminated here. We
go a step further and eliminate some dominances during search. In particular, for two bins i, j
that are known to be open (yi = y j = 1) such that ci ≤ c j and Ci ≥ C j , we can enforce li ≥ l j
in the remaining sub-tree. Regarding item symmetries, we prefer to avoid changing the domain’s
definitions (as done for Formulation (1)) to keep the semantics of the global constraint unchanged.
Instead, each time a bin is proved to be infeasible for an item, the same value is removed from all
the ungrounded items of the same size.
5.2. Search.
The propagation scheme relies on the knowledge of good upper bounds so the search process
is driven by this need. We branch first on the bin variables y before the item’s variables x. We
branch on the cheapest bins first by selecting the y with minimum r value and setting it to 1. The y
variables are therefore sorted lexicographically by non-decreasing r j values. Once all y variables
are grounded, we select the open bin k with the smallest slope (ck ) and assign to it the largest item
10

Algorithm 1: UpdateMinimumLoad
Algorithm 2: UpdateMaximumLoad
0
0
Input: a j with j ≤ k, B , gap
Input: a j with j ≥ k , B , gap
Output: a lower bound of la j
Output: an upper bound of la j
1. costInc ← 0; q−a j ← 0; b ← k;
1. costInc ← 0; q+a j ← 0; b ← k;
2. If ( j = k) {b ← k + 1;}
2. If ( j = k) {q+a j ← Lk ; b ← k − 1;}
−
0
3. While (qa j < L j && b ≤ m)
3. While (q+a j < Ca j && b ≥ 0)
0
0
4.
loadAdd ← min(L j − q−a j , Cab − Lb ); 4.
loadAdd ← min(Lb , Ca j − q+a j );
5.
costIncb ← loadAdd × (rab − ra j );
5.
costIncb ← loadAdd × (ra j − rab );
6.
If ((costIncb + costInc) > gap)
6.
If ((costIncb + costInc) > gap)
7.
q−a j ← q−a j + b gap−costInc
rab −ra j c;
7.
q+a j ← q+a j + b gap−costInc
ra j −rab c;
−
8.
return la j + L j − qa j ;
8.
return l + q+ ;
9.
10.
11.

costInc ← costInc + costIncb;
q−a j ← q−a j + loadAdd; b = b + 1;
return la j

aj

9.
10.
11.

aj

costInc ← costInc + costIncb;
q+a j ← q+a j + loadAdd; b = b − 1;
return la j

Figure 5: Propagation algorithms for updating the lower and upper bounds of the load variables

that can fit in a perfect packing of the bin. We thus check by dynamic programming that the item
selected belongs to a subset of items that perfectly (up to its capacity) fill the bin. The search is
binary, i.e. on the left branch we enforce xi = k and on the right branch we simply have xi , k.
5.3. Propagating a stronger lower bound.
The lower bound z∗2 obtained by solving the linear relaxation of the cutting stock model can
also be propagated by the constraint. However current restrictions of the domains have to be
taken into account when computing the bound during search. The master and pricing problem
are affected as we apply the bound by taking into account items already assigned (the capacity of
the bins is reduced accordingly), and bins known to be open/close and currently possible items
for each bin. The bound thus benefits from all other reasoning that acts on the domains. Since
the pricing problem is time-consuming we found that the following techniques are important for
efficiency:
• We keep the columns of the previous call to the cutting stock model that are still compatible
(feasible) with respect to the current domains.
• When solving the pricing problem for a bin, an upper bound is first computed by sorting the
items from the most beneficial to the least and adding them greedily as long as the capacity
is not overloaded. If the column obtained has a negative reduced cost, the dynamic programming algorithm is not called and the algorithm moves on. This is a very common technique
in column generation that pays off when the pricing is costly and the master very easy to
solve (because it usually increases the number of iterations). The dynamic programming
algorithm is called at least once to prove that no negative reduced cost columns still exist
and ensure the validity of the bound.
11

Table 1: Comparison of the results obtained using MIP. Arc-Flow. and CP approaches approaches on random bin
packing with usage cost problem instances with 600 seconds time-limit.
n
n
15
15
15
25
25
25
25
25
25
200
200
200
250
250
250
500
500
500

m X
m X
10 1
10 2
10 3
15 1
15 2
15 3
25 1
25 2
25 3
10 1
10 2
10 3
15 1
15 2
15 3
30 1
30 2
30 3

MIP
gap z∗1 #ns
cpu
4.81 10
1.2
2.91 10
1.1
3.31 10
0.8
1.76 10 35.1
1.91 10 74.2
2.60 10 22.6
1.67
9
19.0
1.47
9
97.4
2.30 10 33.7
2.73 10
1.9
2.16 10 18.9
1.82 10 16.2
1.53 10
3.9
1.30
9
26.3
0.96
4 190.9
0.62 10 18.1
0.46
7 173.2
0.28
1 184.6

CP
nodes #ns
cpu
2112 10
0.3
2050 10
0.1
1847 10
0.4
29546 10 20.1
114068 10 10.1
46350
8
26.9
10876
8
14.5
114530
9
17.6
53462
8 109.5
1011 10
6.4
68121 10
2.9
93306 10
0.4
1627 10
7.4
50275 10
6.1
546599 10
4.8
7449 10 30.6
193274 10 16.7
322806 10 24.2

CP+CG
nodes #ns
cpu nodes gap z∗3
1270 10
0.3
1109
4.53
1020 10
0.1
785
1.81
4372 10
0.2
972
1.36
140533 10
1.2
1410
1.60
78297 10
0.8
1498
1.53
198792 10
7.3
3359
0.93
99250 10
1.3
1394
1.42
117327 10
2.1
1706
1.08
537144 10
2.2
1816
0.93
14626 10
13.5 14626
2.73
6641 10
10.3 6641
2.16
4064 10
1.7
4064
1.82
11159 10
11.7 11159
1.53
12902 10
20.4 12902
7.21
14111 10
23.7 14111
0.96
14829 10
77.9 14829
0.62
14340 10
78.4 14340
0.46
21285
9 187.9 19678
0.28

Arc-Flow
CG
#ns cpu nodes gap z∗2
10 2.1 2402
4.47
10 0.7 1508
1.77
10 0.6
420
1.33
9 47.5 891
1.59
10 61.2 12557
1.51
10 11.3 1039
0.93
9 31.2 4582
1.42
10 54.8 5967
1.07
10 20.6 510
0.92
0
2.73
0
2.16
0
1.82
0
1.53
0
1.30
0
0.96
0
0.62
0
0.46
0
0.28

6. Experimental Results
In this section we report the results for solving bin packing with usage cost problem to show
the efficiency of the BPUC global constraint.
We compare on randomly generated instances the lower bounds z∗1 , z∗2 , z∗3 as well as exact algorithms: Model (1), Arc-Flow Model (3), and two CP models using the BinPackingUsageCost
constraint. The second CP model referred to as CP+CG activates the propagation of the z∗2 bound
by the BinPackingUsageCost constraint. Standard symmetry/dominance breaking techniques for
BP are applied to the MIP [15] of Model (1) and CP [17]. A random instance is defined by
(n, m, X), where n is the number of items (n ∈ {15, 25, 200, 250, 500}), m is the number of bins (m ∈
{10, 15, 25, 30}), and parameter X ∈ {1, 2, 3} denotes that the item sizes are uniformly randomly
generated in the intervals [1, 100], [20, 100], and [50, 100] respectively. The capacities of the bins
are picked randomly from the sets {80, 100, 120, 150, 200, 250} and {800, 1000, 1200, 1500, 2000,
2500} when n ∈ {15, 25} and n ∈ {200, 250, 500} respectively. The fixed cost of each bin is set to
its capacity and the unit cost is randomly picked from the interval [0, 1]. For each combination of
(n, m) ∈ {(15, 10), (25, 15), (25, 25), (200, 10), (250, 15), (500, 30)} and X ∈ {1, 2, 3} we generated
10 instances giving 180 instances in total.
The time-limit was 600 seconds. All the experiments were carried out on a Dual Quad Core
Xeon CPU, running Linux 2.6.25 x64, with 11.76 GB of RAM, and 2.66 GHz processor speed.
The LP solver used was CPLEX 12.5 (default parameters) and the CP solver was Choco 2.1.5.
Table 1 reports the average cpu time in seconds (denoted cpu), the average number of nodes
in the search tree (denoted nodes) and the average gap of the lower-bounds found at root node
(denoted gap z∗x ). This gap is computed as a percentage of the best known solution found. Column
#ns gives the number of instances solved to optimality (i.e optimal value was found and proved
optimal) within the time limit.
The CP approach shows better performance when scaling to larger size instances (and capac12

ities) than the MIP and Arc-Flow models. Overall, the Arc-Flow model fails to solve optimally
92 instances of the 180 instances, MIP fails on 21, CP fails on 7 and CP+CG only on 1.
On one side, the search space is dramatically reduced by the propagation of z∗2 (CP+CG) for
small problems. On the other side, the bound becomes ineffective on large problems (this can also
be seen on the gap at the root node).

7. Conclusion and Future Work
Bin Packing with Usage Costs (BPUC) problem can be viewed as a core subproblem of many
optimisation problems related with workload consolidation in data centres. The main contribution of this paper is the study of various lower bounds and exact formulation for BPUC. Firstly,
the value of the linear relaxation of a basic LP model for BPUC can be easily computed. Secondly, we show that this bound can be strengthened with filtering algorithms reasoning on the
minimum/maximum load of each bin and that the resulting CP approach can efficiently handle
relatively large instances.
References
[1] Anily, S., Bramel, J., Simchi-Levi, D., 1994. Worst-case analysis of heuristics for the bin packing problem with
general cost structures. Operational Research 42.
[2] Baldi, M. M., Crainic, T. G., Perboli, G., Tadei, R., 2012. The generalized bin packing problem. Transportation
Research Part E: Logistics and Transportation Review 48 (6), 1205 – 1220.
URL http://www.sciencedirect.com/science/article/pii/S1366554512000580
[3] Cambazard, H., Mehta, D., O’Sullivan, B., Simonis, H., 2013. Bin packing with linear usage costs - an application to energy management in data centres. In: Schulte, C. (Ed.), Principles and Practice of Constraint
Programming - 19th International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013. Proceedings. Vol. 8124 of Lecture Notes in Computer Science. Springer, pp. 47–62.
URL http://dx.doi.org/10.1007/978-3-642-40627-0_7
[4] Crainic, T. G., Perboli, G., Rei, W., Tadei, R., Nov. 2011. Efficient lower bounds and heuristics for the variable
cost and size bin packing problem. Comput. Oper. Res. 38 (11), 1474–1482.
URL http://dx.doi.org/10.1016/j.cor.2011.01.001
[5] de Carvalho, J. M. V., 1999. Exact solution of bin-packing problems using column generation and branch-andbound. Annals of Operations Research 86 (0), 629–659.
[6] de Carvalho, J. M. V., 2002. Lp models for bin packing and cutting stock problems. European Journal of Operational Research 141 (2), 253–273.
[7] EnergeTIC, 2013. Efficience des data centers, les retombés du projet energetic. Tech. rep.
URL www.vesta-system.cades-solutions.com/images/vestalis/4/energetic\white%20paper.
pdf
[8] Epstein, L., Levin, A., Apr. 2012. Bin packing with general cost structures. Math. Program. 132 (1-2), 355–391.
URL http://dx.doi.org/10.1007/s10107-010-0403-5
[9] Gilmore, P. C., Gomory, R. E., 1963. A linear programming approach to the cutting-stock problem. Operations
research 11, 863–888.
[10] Glanz, J., September 2012. Power, Pollution and the Internet. http://www.nytimes.com/2012/09/23/
technology/data-centers-waste-vast-amounts-of-energy-belying-industry-image.html.
[11] Haouari, M., Serairi, M., Mar. 2011. Relaxations and exact solution of the variable sized bin packing problem.
Comput. Optim. Appl. 48 (2), 345–368.
URL http://dx.doi.org/10.1007/s10589-009-9276-z

13

[12] lun Li, C., long Chen, Z., 2006. Bin-packing problem with concave costs of bin utilization. Naval Research
Logistics 53, 298–308.
[13] Monaci, M., 2012. Algorithms for packing and scheduling problems. Ph.D. thesis, Universit di Bologna.
[14] Régin, J.-C., Rezgui, M., 2011. Discussion about constraint programming bin packing models. In: AI for Data
Center Management and Cloud Computing. Vol. WS-11-08 of AAAI Workshops. AAAI.
[15] Salvagnin, D., 2013. Orbital shrinking: A new tool for hybrid MIP/CP methods. In: Gomes, C., Sellmann,
M. (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization
Problems. Vol. 7874 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, pp. 204–215.
URL http://dx.doi.org/10.1007/978-3-642-38171-3_14
[16] Schaus, P., 2009. Solving balancing and bin-packing prob- lems with constraint programming. Ph.D. thesis,
Universit catholique de Louvain-la-Neuve.
[17] Shaw, P., 2004. A constraint for bin packing. In: Wallace, M. (Ed.), CP. Vol. 3258 of Lecture Notes in Computer
Science. Springer, pp. 648–662.
[18] Srikantaiah, S., Kansal, A., Zhao, F., 2008. Energy aware consolidation for cloud computing. In: Proceedings
of HotPower.
[19] Trick, M. A., 2003. A dynamic programming approach for consistency and propagation for knapsack constraints.
Annals OR 118 (1-4), 73–84.

14

