A heuristic algorithm for the
Bin Packing Problem with Conflicts
on Interval Graphs
arXiv:1707.00496v2 [math.CO] 14 Sep 2017

Tiziano Bacci

∗

Sara Nicoloso†

September 15, 2017

Abstract
In this paper we deal with the Bin Packing Problem with Conflicts on interval
graphs: given an interval graph, a nonnegative integer weight for each vertex, and a
nonnegative integer B, find a partition of the vertex set of the graph into k subsets
such that the sum of the weights of the vertices assigned to same subset is less
than or equal to B, two vertices connected by an edge do not belong to the same
subset, and k is minimum. We design a heuristic algorithm, and propose a new
random interval graph generator which builds interval conflict graphs with desired
edge density. We test the algorithm on a huge test bed, and compare the results
with existing algorithms.

Keywords: Bin Packing with Conflicts, Interval Graphs, Threshold Graphs, Random
Interval Graph Generator.

∗

Università di Roma Tor Vergata, Dipartimento di Ingegneria Informatica e Civile, Via del Politecnico
1, 00133 Roma, Italia, bacci.tiziano@gmail.com
†
IASI - CNR, Via dei Taurini 19, 00185 Roma, Italia, sara.nicoloso@iasi.cnr.it

1

1

Introduction

In this paper we deal with the Bin Packing problem with Conflicts (BP P C) on interval
graphs.
BP P C, first introduced in a scheduling context (Jansen and Oehring (1997)), is defined as follows. Given a graph G = (V, E), a nonnegative integer weight wi for each
vertex i ∈ V , and a nonnegative integer B, find a partition of V into k subsets V1 , . . . , Vk ,
such that the sum of the weights of the vertices assigned to a same subset is less than or
equal to B, two vertices connected by an edge do not belong to the same subset, and k
is minimum. Such minimum value of k will be denoted kBP P C . The graph G = (V, E)
is called conflict graph and two vertices connected by an edge are said to be in conflict.
BP P C is the union of two well known combinatorial optimization problems, the Bin
Packing problem (BP ) and the Vertex Coloring problem (V C), which we now introduce.
The Bin Packing problem (BP ) is defined as follows. Given a set V of items, a
nonnegative integer weight wi for each item i ∈ V , and a nonnegative integer B, find a
partition of V into k subsets V1 , . . . , Vk , such that the sum of the weights of the items
assigned to same subset is less than or equal to B and k is minimum. Such minimum
value of k will be denoted kBP . Notice that both BP P C and BP can also be defined
with rational weights in [0, 1] and B = 1.
The Vertex Coloring problem (V C) is defined as follows. Given a graph G = (V, E),
find a partition of V into k subsets V1 , . . . , Vk , such that two vertices connected by an edge
do not belong to the same subset and k is minimum. Throughout the paper k-coloring
denotes a feasible vertex coloring with k colors. The minimum value of k such that G
admits a k-coloring is called the chromatic number χ(G) of the graph G. Notice that each
Vi for i = 1, . . . , p is an independent set, that is a subset of vertices no two of which are
connected by an edge.
Clearly, kBP P C ≥ max{kBP , χ(G)}.
Throughout the paper n = |V |, the words vertex and item will be used interchangeably,
and the subsets of a feasible solution to BP P C, BP , and V C will be called colors or bins.
Since V C on arbitrary graphs and BP are both NP -hard (Garey and Johnson (1978)),
BP P C is NP -hard too.
Observe that when the edge set E of the graph G is empty, BP P C reduces to BP .
For increasing |E|, the effects of V C on BP P C also increase, because of the increasing
number of conflicting pairs of items. Let t be the maximum number of heaviest items
whose sum of the weights does not exceed B. If α(G) ≤ t, then BP P C reduces to V C,
where α(G)Pis the cardinality of a maximum independent set of G. As a consequence,
when B ≥ i∈V wi , BP P C reduces to V C.
An application of BP P C is discussed in Christofides et al. (1979), where some flammable, explosive, or toxic substances cannot be placed in the same vehicle.
In this paper we focus on BP P C where G = (V, E) is an interval graph. A graph
G = (V, E) is an interval graph if every vertex p ∈ V can be put in one-to-one correspondence with an open intervals Ip = (lp , rp ) of the real line, and two vertices p, q ∈ V are
connected by edge (p, q) ∈ E if and only if the corresponding intervals intersect, i.e. lp < rq
and lq < rp . The family of intervals I = {Ih = (lh , rh ), h = 1, . . . , n} is called an interval
model for G. Any interval graph admits an interval model. Notice that when the edge
set of the graph is empty, any set of n mutually non-intersecting intervals is an interval
model for G. In what follows, w.l.o.g. we can assume that min{lj , j = 1, . . . , n} = 0, and
define R = max{rj , j = 1. . . . , n}. It is worth observing that V C is solvable in linear time
2

on interval graphs, nevertheless BP P C with an interval conflict graph remains NP -hard.
In this paper we design a new heuristic algorithm for BP P C with interval conflict graphs
and test it on thousands of instances.
As far as we know, no tests on instances of BP P C with arbitrary interval conflict
graphs were performed in the literature. In fact, Sadykov and Vanderbeck (2013) realize
that the conflict graphs of the benchmark instances by Muritiba et al. (2010) are interval
graphs, and not arbitrary graphs: actually, the conflict graphs of these instances are not
arbitrary interval graphs, but special ones, namely threshold graphs (see Section 6).
Since the existing random interval graph generators output graphs with edge density
in a very narrow range and we want to test our algorithm on interval graphs with edge
density ranging from 0 to 1, we design a new random interval graph generator which
outputs interval graphs with desired edge density. We use this generator to generate
4000 interval conflict graphs, each of which is associated with a set of item weights. By
varying B in ten different ways, we obtain 40000 BP P C instances and test our algorithm
on all of them. We also implement some heuristics which are an adaptation of three
classical algorithms for BP , as in Muritiba et al. (2010), run them on the same test bed
and compare the results with ours.
The paper is organized as follows. In Section 2 we review the literature on BP P C.
In Section 3 a new heuristic algorithm is proposed, while a new random interval graph
generator is found in Section 4. Experimental results are discussed in Section 5, where we
compare our results with other existing approaches. In Section 6, our heuristic is tested
over instances taken from the literature. Section 7 concludes.

2

Literature review

The BP P C is widely discussed in literature. We start by surveying papers where approaches to BP P C with arbitrary conflict graphs are proposed, then we discuss some
issue about literature BP P C instances and some papers devoted to BP P C on interval
graphs.
Kalfakakou et al. (2003) present a heuristic algorithm which repeatedly create a new
bin for a maximal independent subset with weight close to B. Gendreau et al. (2004)
propose a lower bound and six heuristics: one is a direct adaptation of the First-Fit Decreasing algorithm by Johnson (1974), three are based on graph coloring, and two are
based on finding large cliques. They also describe a random graph generation scheme.
Basnet and Wilson (2005) compare their heuristic algorithm with two of the best approaches by Gendreau et al. (2004), with the algorithm by Kalfakakou et al. (2003), and
with a standard beam search algorithm: the proposed algorithm outperforms all the others, on average. Maiza and Guéret (2009) present a lower bound which outperforms those
by Gendreau et al. (2004) and by Muritiba et al. (2009) and is based on iterative runs of
the lower bound algorithms by Gendreau et al. (2004). A Column Generation approach
is proposed by Joncour et al. (2010) and tested on 280 instances with density between
10%-40% (the generation scheme is not specified). An exact algorithm based on a setcovering formulation is discussed by Muritiba et al. (2010). The authors propose a very
effective but time consuming lower bounds; the upper bounds are obtained by means
of fast and good heuristic algorithms which are an adaptation of the classical First-Fit
Decreasing, Best-Fit Decreasing, Worst-Fit Decreasing for BP ; lower and upper bounds
are better than those by Gendreau et al. (2004). If no optimal solution is found then a
3

population-based metaheuristic is applied and possibly a Branch-and-Price algorithm is
adopted. Khanafer et al. (2010) improve some lower bounds by Muritiba et al. (2010) by
applying reduction procedures. Elhedhli et al. (2011) propose a Branch-and-Price algorithm which is compared with those by Muritiba et al. (2010): results show that neither
one outperforms the other. Maiza and Radjef (2011) propose seven heuristics: one is an
adaptation of the Minimum Bin Slack heuristic by Gupta and Ho (1999); the others six
repeatedly create a new bin by selecting (by means of classical bin packing methods) a
subset of items from a maximal independent set previously generated. The experimental
results show that these heuristics outperform those by Gendreau et al. (2004). Yuan et al.
(2014) show the effectiveness of an ant colony optimization approach to determine a feasible coloring solution to which an improved First-Fit Decreasing heuristic bin packing
procedure is applied. Gschwind and Irnich (2016) describe an effective Column Generation approach to solve BP P C and other problems to optimality, providing new classes
of valid inequalities. Brandão and Pedroso (2016) present an exact method based on
an arc-flow formulation with side constraints. The method builds very strong integer
programming models that can be given in input to any state-of-the-art mixed integer programming solver. The algorithm is applied to many classical combinatorial problems and,
in particular, all the instances by Muritiba et al. (2010) are efficiently solved to optimality.
We remark that the generator by Gendreau et al. (2004) has been improperly used
to generate arbitrary graphs (Basnet and Wilson (2005); Brandão and Pedroso (2016);
Capua et al. (2015); Clautiaux et al. (2011); Cornaz et al. (2017); Elhedhli et al. (2011);
Gschwind and Irnich (2016); Joncour (2010); Joncour et al. (2010); Jouida et al. (2015);
Khanafer (2010); Khanafer et al. (2012a, 2010, 2012b); Maiza and Guéret (2009); Maiza and Radjef
(2011); Muritiba (2010); Muritiba et al. (2010); Sadykov and Vanderbeck (2013); Yuan et al.
(2014)). In Section 6 we show that these are not arbitrary graphs but special interval
graphs, namely threshold graphs. BP P C on threshold graphs turns out to be easier than
on arbitrary interval graphs and arbitrary graphs (see Bacci and Nicoloso (2017b)). We
remark that Muritiba et al. (2010) used the generator by Gendreau et al. (2004) to build
publicly available instances (see http://or.dei.unibo.it/library/bin-packing-problem-conflicts)
and many of the authors above used them.
Few papers are devoted to BP P C with interval conflict graphs. Epstein and Levin
(2008) present a 73 -approximation algorithm. Sadykov and Vanderbeck (2013) present a
generic effective Branch-and-Price algorithm for the BP P C with arbitrary conflict graphs,
using a Dynamic Programming algorithm for pricing when the conflict graph is an interval graph. They test their algorithm on the instances by Muritiba et al. (2010) and
Elhedhli et al. (2011), closing all open instances, and on harder instances with an arbitrary conflict graph and a larger number of items per bin. A 2-approximation algorithm
exists if G is a threshold graph. In fact, Myung (2008) proposes a 2-approximation algorithm for the Minimum Clique Partitioning Problem on a weighted interval graph: given
an interval graph with nonnegative vertex weights, find a partition of the vertices into
the minimum number of cliques such that the sum of vertex weights in each clique does
not exceed a given bound B. Since G is a threshold graph, it is also a co-interval graph,
hence G, the complement of G, is an interval graph and BP P C on a threshold graph G is
equivalent to the Minimum Clique Partitioning Problem on the weighted interval graph
G.
We recall the following problems related to BP P C. Given an instance of BP P C,
let Dp = {i ∈ V : wi = Wp } be the set of items whose weight is equal to Wp , and let
dp = |Dp |. If we say that the items in Dp are items of type p and that dp is their demand,
4

then BP P C is usually known as Cutting Stock problem (CS) (Delorme et al. (2016))
and it is formulated with integer variables and not binary ones like BP P C. CS arises
in industrial contexts and often the number of different types of items is small w.r.t. the
number n of items, while in BP P C and BP it is not. The special case of BPPC when
wi = 1 for i = 1, . . . , n is the optimization version of Bounded Independent Sets (also
known as Mutual Exclusion Scheduling, see Baker and Coffman (1996)), which is NP complete when G is an interval graph and B ≥ 4 (Bodlaender and Jansen (1995)). An
application of Mutual Exclusion Scheduling on interval conflict graphs is described in
Gardi (2009). In Gupta et al. (2008) also item-bin conflicts are considered. When the
number of bin is fixed, Kowalczyk and Leus (2016) minimize the weight of the heaviest
bin, while Khanafer et al. (2012a) minimize the number of violated conflicts.

3

Heuristic algorithm

Since BP P C is the union of BP and V C, we believe that in order to design effective heuristic algorithms one has to adopt one of the following two approaches, where
P ∈ {V C, BP }: modify an algorithm designed for a problem P to directly obtain a feasible solution for BP P C, or determine a feasible solution for problem P , first, then modify
it to obtain a feasible solution for BP P C.
The first approach is used by the algorithms UF F (α) , UBF (α) , and UW F (α) by Muritiba et al.
(2010): an algorithm designed for BP is modified in such a way that an item p is not
assigned to a bin containing an item q in conflict with p. The first approach is applied also
by Gendreau et al. (2004): an algorithm designed for V C is modified in such a way that
when a new color S is P
created and its weight exceeds B, then a suitable subset S ′ ⊂ S is
determined such that i∈S\S ′ wi ≤ B, and removed from S.
Here we adopt the second approach, as V C on interval graphs is solvable in linear
time. In particular we construct an optimum feasible vertex coloring solution and modify
it with a local search approach to obtain a feasible BP P C solution.
In the algorithm, we will make use of an interval model of G and of the following notations
or definitions.
• λ = max{LBBP , ω(G)}, a lower bound for BP P C, where LBBP denotes a lower
bound for the Bin Packing problem underlying the given BP P C and ω(G) denotes
the size of a maximum clique of G (recall, in fact, that ω(G) = χ(G) as G is an
interval graph);
• C, the leftmost subset of ω(G) mutually intersecting intervals, i.e. the leftmost maximum clique;
• π = max{lj , Ij ∈ C}, the leftmost coordinate belonging to ω(G) intervals;
• Ilef t , the set of intervals whose right endpoint lays on the left of π;
• Iright , the set of intervals whose left endpoint lays on the right of π;
• W est (Vi ), the estimated weight of the empty space on the right of the interval belonging to Vi ∩ C, if any, or on the right of π: assuming that the interval
P weights are
1
uniformly distributed among the R × λ unit segments, let µ = Rλ
j=1,...,n wj be
the average weight of a unit segment, denote by Ij = (lj , rj ) the (unique) interval
5

in C which belongs also to Vi for i = 1, . . . , ω(G), then Ri = rj for i = 1, . . . , ω(G),
and Ri = π for i = ω(G) + 1, . . . , λ, and W est (Vi ) = µ(R − Ri );
• z and V1 , . . . , Vz , the number of subsets and the subsets in the current (possibly
infeasible) solution, respectively;
• W (X), the weight of a subset X of intervals, i.e. the sum of the weights of the
intervals belonging to X ⊆ V ; if W (X) > B the subset X is heavy, otherwise it is
light;
• T ail(Vi , ρ) ⊆ Vi , where ρ ∈ [0, R] denotes a coordinate, a subset of intervals of Vi
which we define only for those i such that ∄Ij ∈ Vi : lj < ρ < rj ; when defined,
T ail(Vi , ρ) = {Ij ∈ Vi : lj ≥ ρ}.
• a subset Vi non-conflicting w.r.t. interval Ij , i.e. an independent subset Vi such that
Vi ∪ {Ij } is an independent subset too.
The algorithm consists of two phases.
In the first phase the algorithm constructs a λ-coloring {V1 ,. . . ,Vλ } of G working on
the chosen interval model of G. In particular, among all the feasible λ-colorings of G, the
algorithm finds a coloring where the weight of the lightest color is as large as possible, as
we now describe.
It starts by assigning each interval of the leftmost maximum clique C to a different
subset, then it assigns the intervals on the left of π, and finally those on the right of π. On
the left of π, the algorithm repeatedly assigns an unassigned interval with rightmost right
endpoint to the color Vi with minimum (current) weight W (Vi ) + W est (Vi ). On the right
of π, the algorithm repeatedly assigns an unassigned interval with leftmost left endpoint
to the color Vi with smallest (current) weight W (Vi ).
The algorithm ends the first phase with a feasible λ-coloring {V1 ,. . . ,Vλ } of G. If
W (Vi ) ≤ B for i = 1, . . . , λ, the partition {V1 ,. . . ,Vλ } is a feasible solution (of value λ) for
BP P C. Since its value equals the lower bound, {V1 ,. . . ,Vλ } is also an optimum solution
for BP P C. If this is not the case, the algorithm proceeds with the second phase.
In the second phase the algorithm repeatedly selects a heaviest subset Vg and suitably
modifies it to get a light subset. This is accomplished in two different ways: the tailexchange, and the insertion.
The tail-exchange w.r.t. a coordinate ρ between the chosen heavy subset Vg and
a light subset Vh with minimum W (T ail(Vh , ρ)), consists of exchanging T ail(Vg , ρ) with
T ail(Vh , ρ). It can be done iff the following three conditions are verified: both T ail(Vg , ρ)
and T ail(Vh , ρ) are defined, W (T ail(Vh , ρ)) < W (T ail(Vg , ρ)), and the resulting Vh keeps
being light. Notice that the weight of Vg after the exchange is decreased. Precisely, the
algorithm finds the leftmost coordinate ρ ≥ min{rs : Is ∈ Vg } such that there exists a
subset Vh allowing a tail-exchange operation with Vg . If the resulting Vg is still heavy,
the algorithm finds the next ρ with the same properties and repeats this step again,
stopping as soon as ρ ≥ R or the current Vg is light. If Vg is still heavy the algorithm
tries to apply the insertion.
In an insertion, an interval Ij ∈ Vg which minimizes |W (Vg )−wj −B| is selected, and
inserted into a light non-conflicting Vh such that the resulting Vh is light and W (Vh )+wj is
maximum, if any. Otherwise Ij is inserted into a heavy non-conflicting Vh with minimum

6

weight, if any. The first time that no insertion is performed w.r.t. Vg , then a new subset
is created and Ij is inserted into it.
The algorithm description follows. By tail-exchange step (insertion step, respectively) we mean the repeated application of a tail-exchange (insertion, respectively).
We recall that, when ω(G) = 1 (i.e. the edge density is zero), any set of n mutually nonintersecting intervals is an interval model of G, and BP P C reduces to BP .

ALGORITHM BN
Input: an interval model for the graph G, wi ∈ Z+ ∀i ∈ V , B ∈ Z+ .
Output: z and a feasible partition {V1 , . . . , Vz } of V .
• Phase I
Define z := λ;
Define z empty sets V1 , ..., Vz ;
Assign each interval of C to a different subset;
Let Ij ∈ Ilef t be an interval with righmost right endpoint,
assign Ij to a non-conflicting subset Vi with minimum W (Vi )+W est(Vi ),
remove Ij from Ilef t , and repeat until Ilef t is empty;
Let Ij ∈ Iright be an interval with leftmost left endpoint,
assign Ij to a non-conflicting subset Vi with minimum W (Vi ),
remove Ij from Iright , and repeat until Iright is empty;
• Phase II
While V1 , . . . , Vz is infeasible do
Let Vg be a subset with maximum weight;
ρ := min{rs : Is ∈ Vg };
tail-exchange step:
While W (Vg ) > B and ρ < R do
let Vh , h 6= g, with minimum W (T ail(Vh , ρ)) be a light subset
such that W (T ail(Vh , ρ)) < W (T ail(Vg , ρ)) and
W (Vh ) − W (T ail(Vh , ρ)) + W (T ail(Vg , ρ)) ≤ B, if any;
set Vg := Vg \ T ail(Vg , ρ) ∪ T ail(Vh , ρ)
and Vh := Vh \ T ail(Vh , ρ) ∪ T ail(Vg , ρ)
ρ = ρ + 1;
new subset:=false;
insertion step:
While W (Vg ) > B do
let Ij ∈ Vg be an interval with minimum |W (Vg ) − B − wj |
If there exists a Vh , h 6= g, non-conflicting w.r.t. Ij ,
such that W (Vh ) + wj is maximum and ≤ B,
then remove Ij from Vg , and insert it in Vh ,
otherwise if there exists a Vh , h 6= g, non-conflicting
w.r.t. Ij , such that W (Vh ) is mimimum and ≥ B,
then remove Ij from Vg , and insert it in Vh ,
otherwise if new subset=false set z := z+1 and new subset:=true
then remove Ij from Vg and insert it in Vz .

If the partition at the end of Phase I is feasible then the algorithm terminates, otherwise
the algorithm enters Phase II and chooses a heaviest subset Vg . If Vg after the tailexchange step is light then the algorithm terminates an iteration of the main whileinstruction of Phase II and the number of heavy subsets is decreased by one, otherwise
7

the algorithm performs the insertion step: if no new subset is created then, again,
the algorithm terminates an iteration of the main while-instruction of Phase II and the
number of the heavy subsets is decreased by one; on the contrary, if a new subset Vz+1 is
created, the algorithm terminates this iteration of the main while-instruction either with
Vg and Vz+1 light or with Vg light and Vz+1 heavy but verifying W (Vz+1 ) < W (Vg ). In the
former case the number of heavy subsets is decreased by one, in the latter the number
of heavy subsets keeps constant but the overall infeasibility is decreased. This discussion
show that the algorithm terminates.
The computational complexity of Phase I is O(n log n). As for Phase II, the complexity
of the tail-exchange step is O(nR) and the complexity of the insertion step is
O(n2). Since the main while-instruction is repeated at most n times and R ≤ 2n (in
fact, w.l.o.g., one can delete all the coordinates which belong to at most one interval), the
overall computational complexity of Phase II is O(n3 ), and so is the complexity of the
entire algorithm.
The algorithm has been tested over thousands of randomly generated instances. Computational results are presented in Section 5.

4

A random interval graph generator

The easiest way to generate a random interval graph is to randomly choose the endpoints
of each of the n intervals and then construct the intersection graph of them (Vasileios
(2005); Justicz et al. (1990)).
Another (equivalent) generator is the following. Given a non-negative integer n, let
π = (π1 , . . . , π2n ) be a random permutation of (1, 1, 2, 2, . . . , n, n); then for j = 1, . . . , n
define interval Ij = (lj , rj ), where lj = min{k : πk = j, k = 1, . . . , 2n} and rj = max{k :
πk = j, k = 1, . . . , 2n} (notice that in π there exists exactly two elements of value j).
We generated thousands of set of intervals in both ways. The experimental analysis
we conducted shows that the edge density 2|E|/(n(n − 1)) of almost all the corresponding
interval graphs is 60%-70%. The BP P C instances in the literature (see, for example,
Gendreau et al. (2004); Muritiba et al. (2010); Sadykov and Vanderbeck (2013)) are classified by their edge density ranging from 0% to 90%. Since, to our knowledge, no random
interval graph generator exists which allows to obtain an interval graph with a prescribed
edge density, in the present section we define a new random interval graph generator with
this property. In fact, the edge density of the intersection graph of a set of intervals in
[0; D] depends on the average interval length.
Our generator accepts in input the number n of intervals and the desired edge density
δ of the corresponding intersection graph, and suitably computes three values, D, Λmin,
Λmax to obtain an interval graph with desired edge density δ. The output consists of a set
of n intervals whose endpoints (integer, w.l.o.g.) are uniformly distributed in {0, . . . , D},
and an arbitrary interval Ij = (lj , rj ) in this set will have length Λj = rj − lj verifying
Λmin ≤ Λj ≤ Λmax . Experimental analysis conducted on thousands of graphs shows
that our generator generates arbitrary interval graph with expected edge density δ (the
standard deviation of δ increases for increasing δ and ranges in [0,0.02]). Let’s go into
details.
In order to ensure that the 2n endpoints of the n intervals have space enough to give
a graph with edge density equal to zero (for suitable interval lengths), one has to fix
D ≥ 2n. We tried many different values for D but we did not appreciate any differences,
so we decided to set D = 2.5n.
8

The edge density δ of the resulting interval graph depends on the average interval
length Λ: for example when Λ = 1 then δ ≃ 0, and when Λ > D/2 then δ ≃ 1. We
can determine the equation which ties δ and Λ. The coordinate 0 can be chosen as a left
endpoint, only, the coordinate D can be chosen as a right endpoint, only, and all the other
coordinates can be chosen both as left and right endpoints. Hence the average number
of left endpoints per coordinate is Dn , as well as the average number of right endpoints
per coordinate, and an interval of length Λ intersects 2n
Λ intervals, on average. Thus the
D
2n n
2n
average degree of a vertex is D Λ, resulting in D 2 Λ edges of the interval graph. Dividing
2n
this quantity by n(n−1)
Λ from which we
, one gets that the edge density is δ = (n−1)D
2
n−1
derive that the average inteval length Λ has to be set to δD 2n in order to obtain an
interval graph with expectedP
edge density δ.
Recalling that Λ = 1/n nj=1 Λj and that Λmin ≤ Λj ≤ Λmax for all j, the set of
intervals has average length Λ if one suitably chooses Λmin and Λmax . We decided to
randomly choose Λmin in a suitable range which we discuss in a while; Λmax is consequently
determined. We reason as follows.
By flipping a coin, the generator randomly chooses the left endpoint lj of interval
Ij first, or the right endpoint rj . Assume that the left endpoint lj is randomly chosen
first. In order to ensure that the length Λj verifies Λj ≥ Λmin, lj has to be chosen in
{0, . . . , D − Λmin}. Refer to Figure 1. If lj ∈ {0, . . . , D − Λmax } then rj can be randomly
chosen in {lj + Λmin , . . . , lj + Λmax }. In this case the expected interval length eil(lj ) is
(Λmin +Λmax)/2. If lj ∈ {D −Λmax +1, . . . , D −Λmin } then rj can be randomly chosen only
in {lj + Λmin, . . . , D} and the eil(lj ) is a linear function of lj , namely (D + Λmin − lj )/2.
′
Thus the average interval length Λ when lj is chosen first can be computed dividing the
entire area underlying the drawn function by its width D − Λmin as follows:
′

Λ =


 Λmin + Λmax

1
Λmax − Λmin  Λmin + Λmax
D − Λmax
+
+ Λmin =
D − Λmin
2
2
2

1
[−Λ2max − 3Λ2min + 2D(Λmax + Λmin )]
4(D − Λmin )
Assume now that the right endpoint rj of interval Ij is randomly chosen first. By similar
arguments, rj has to be chosen in {Λmin , . . . , D} and lj ∈ {max{rj −Λmax ; 0}, . . . , rj −Λmin }
′′
′
and the average interval length Λ when rj is chosen first is equal to Λ (the graph of
eil(rj ) can be obtained by horizontally flipping the graph of Figure 1 along the vertical
axis D/2).
Since, on average, one half of the intervals are generated by randomly choosing the
left endpoint first, and one half by randomly choosing the right endpoint first, the overall
average interval length is
=

′

′′

1
Λ +Λ
=
[−Λ2max − 3Λ2min + 2D(Λmax + Λmin )]
Λ=
2
4(D − Λmin )
Given Λmin and Λ, we can use this formula to determine Λmax . Since Λmax > D makes no
sense, we get
q
Λmax = D − D 2 − 4DΛ + 2DΛmin + 4ΛΛmin − 3Λ2min
The non-negativity of the argument of the square root requires 4 Λ−D
≤ Λmin ≤ D. On
3
 4 Λ−D 
the other hand, clearly, 1 ≤ Λmin ≤ Λ. Hence max{1;
} ≤ Λmin ≤ Λ, as Λ ≤ D.
3
9

eil(lj )
Λmax

Λmax +Λmin
2

Λmin

Λmin

Λmax

D−Λmax

D−Λmin

D

lj

Figure 1: The expected interval length eil(lj ) when lj is randomly chosen
Then for each interval
The proposed generator fixesn D and computes Λ as discussed.
o
 4 Λ−D 
Ij , it randomly chooses Λmin ∈ max{1;
} , . . . , Λ , computes the corresponding
3
Λmax , randomly chooses whether to generate rj first or lj and, in both cases, randomly
generates a suitable Λj , and consequently fixes the other endpoint.

RANDOM INTERVAL GRAPH GENERATOR
Input: n ∈ Z+ and δ ∈ [0, 1]
Output: a set of n intervals whose intersection graph has expected edge density δ.
D := 2.5 n;
Λ := δD n−1
2n ;
For j = 1, . . . , n


randomly choose
Λmin ∈ { max{1; 4 Λ−D
} ,..., Λ }
3
q

Λmax := D − D 2 − 4DΛ + 2DΛmin + 4ΛΛmin − 3Λ2min ;
flip a coin;
if coin = head then randomly choose rj ∈ {Λmin , . . . , D} and
Λj ∈ Λmin , . . . , min{rj ; Λmax } , and set lj := rj − Λj ;
if coin = tail then randomly choose lj ∈ {0, . . . , D − Λmin } and
Λj ∈ Λmin , . . . , min{D − lj ; Λmax } , and set rj := lj + Λj ;

5

Computational results

In the present section we discuss the results obtained by solving thousands of instances.
The test bed was generated as we now describe. By T I(n, B, ∆) we denote a set of
100 randomly generated instances of BP P C with n items, weights uniformly distributed
in [20, 100] (as in Falkenauer (1996)), bound B, and interval conflict graph with expected
edge density ∆. When ∆ > 0 we repeatedly run the random interval graph generator
described in Section 4 and we selected 100 sets of n intervals whose intersection graph
had edge density δ ∈ [∆ − 0.02; ∆ + 0.02]. When ∆ = 0 we defined the set I = {Ih =
(h, h + 1), h = 0, . . . , n − 1} of n mutually non-intersecting intervals (in this case BP P C
reduces to BP ). In particular, we chose n ∈ {120, 250, 500, 1000}, B ∈ {120, 150, 180,
10

210, 240, 270, 300, 330, 360, 390}, and ∆ ∈ {0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9}.
Totally we built 40000 instances.
Notice that on these instances the number of different weights is 100 − 20 + 1 = 81.
Hence, every weight is expected to appear in n/81 copies. For increasing n the underlying
(classical) Bin Packing recalls a Cutting Stock (see Section 1).
We compare the computational results obtained by applying the heuristic algorithm
BN proposed in Section 3 and an adaptation to BP P C of the classical heuristic algorithms First-Fit Decreasing, Best-Fit Decreasing, Worst-Fit Decreasing for BP (Johnson
(1974)), as described in Muritiba et al. (2010). In particular, these adaptations, UF F (α) ,
UBF (α) , and UW F (α) (we shall call them algorithms M), consider an extended conflict
graph Gw , obtained by adding to G an edge for each pair of vertices i, j with wi + wj > B,
and consider vertex weights wis defined as follows: wis = α(wi /w)+ (1 − α)(deg(i)/deg),
for i = 1, 2, . . . , n, where α ∈ {0, 0.1, . . . , 1}, deg(i) is the degree of vertex i in Gw , and w
and deg are the average weight of the vertices and their average degree in Gw , respectively.
Notice that Gw \ G is a threshold graph (see Section 6) and its edge density δ ′ decreases
for increasing B. For example, when the weights are uniformly distributed in [20, 100] as
in our test bed, δ ′ = 0.5 when B = 120, δ ′ = 0.18 when B = 150, δ ′ = 0.03 when B = 180,
and δ ′ = 0 when B ≥ 200.
All the algorithms were coded in C++ and run on an Intel Core i7-3632QM 2.20GHz
× 8 (up to 3.2 GHz with turbo boost) with 16 GB RAM under a Linux operating system.
Let S be an instance of BP P C with an interval conflict graph G.
Given
α ∈ {0, 0.1, . . . , 1}, let ux(α) (S) be the value of the solution output by algorithm Ux(α)
on S, for x ∈ {F F, BF, W F }. By uM (S) = min{ux(α) (S), α ∈ {0, 0.1, . . . , 1}, x ∈
{F F, BF, W F }} we denote the minimum among all the 33 values of the (feasible) solutions output by algorithms M on S. By uBN (S) we denote the value of the (feasible)
solution output by algorithm BN on S.
We tested each algorithm on all the 40000 instances of our 
testPbed. To evaluate
the

performances of the algorithms we define LBBP P C (S) = max
i∈V wi /B ; χ(G) , a
lower bound on the value of an optimum solution of BP P C on instance S. The detailed
results obtained for n = 1000 are presented in Table 1; the results for n ∈ {120, 250, 500,
1000} are summarized in Table 2.
In Table 1, where rows are indexed by ∆ and columns by B, we compare the results
obtained by applying the algorithms on the 10000 instances T I(1000, B, ∆). In each cell
there are six values, each one averaged over the corresponding 100 instances: M=LB
(BN=LB, respectively) is the percentage of instances S where uM (S) = LBBP P C (S)
(uBN (S) = LBBP P C (S), respectively), i.e. the percentage of instances where LBBP P C (S)
allows to certify that the corresponding algorithm found an optimum solution; M<BN
(BN<M,
respectively)
is
the
percentage
of
instances
S
where
uM (S) < uBN (S) (uBN (S) < uM (S), respectively) (notice that the complement to 100%
of the sum of the last two values is the percentage of instances where uM (S) = uBN (S));
M
BN
BP P C (S)
BP P C (S)
Gap M (Gap BN, respectively) is the gap u (S)−LB
( u (S)−LB
, respecLBBP P C (S)
LBBP P C (S)
tively). A light grey indicates the algorithm which outperforms the other one w.r.t. the
corresponding data. If in a cell the value X=LB is 100%, then all the data of algorithm
X are colored in light cyan, for X ∈ {M,BN}.
The light cyan cells in Table 1 show that algorithm BN solves to optimality all the
100 instances of 36 out of 100 cells, while algorithms M solve to optimality all the 100
instances of 7 out of 100 cells.
Surprisingly algorithm BN shows a very nice behaviour for ∆ = 0 and B ≥ 180, that is
11

to say on instances of Bin Packing (without conflicts). Algorithms M show better results
when B ∈ {120, 150}: we suspect that it is because these algorithms use the informations
of the extended graph. As a general result, algorithm BN has a better behaviour than M
when B ≥ 180, except when ∆ = 0.9 where the two algorithms are essentially equivalent.
We also measured the average time (in seconds) required by BN to solve one instance
out of the 100 in each cell. At the bottom of each column of Table 1 we report the
minimum, maximum, and average time of these values (tmin BN, tmax BN, tavg BN,
respectively). We remark that the maximum is always reached for ∆ = 0.1. Basically
these times decrease for increasing B: we think that this is due to the reduced number
of operations in Phase II. The average times required by algorithms M to solve one
instance out of the 100 in each cell are not displayed because they are always smaller
than 0.1 seconds for all B and ∆.
In Table 2, the results for n ∈ {120, 250, 500, 1000} are summarized (in column
B ∈ {120, 150} they are averaged over the corresponding 2000 instances, in column
B = 180 over 1000, in column B ∈ {210, . . . , 390} over 7000, and in column
B ∈ {120, . . . , 390} over 10000). Results essentially reflect what happens for n = 1000. In
particular, algorithm BN is definitely better than algorithms M for B ≥ 210, algorithms
M have better performances for B ≤ 150, while for B = 180 algorithm BN improves
with the growth of n. We also remark that for B ∈ {120, 150} the values M=LB and
BN=LB are very small: we suspect that this is due to the poor quality of LBBP P C . In
fact, the experiments conducted in Bacci and Nicoloso (2017a) with n = 250 show that
LB is strictly smaller than the value of the optimum solution in 98 out of 100 instances
with B = 120, 23 out of 100 for B = 150, 3 out of 100 for B = 180, zero in all the other
cases.

6

Computational results on literature instances

In this section we discuss the results obtained by solving the instances by Muritiba et al.
(2010) (see http://www.or.deis.unibo.it) and other instances with threshold conflict graphs
by running algorithms M and BN on them.
A graph is a threshold graph if there exist a real number d (the threshold) and a weight
px for every vertex x such that (i, j) is an edge iff (pi + pj )/2 ≤ d (Chvátal and Hammer
(1973)). A threshold graph has many peculiar properties as it is at the same time an
interval graph, a co-interval graph, a cograph, a split graph, and a permutation graph
(Golumbic (1980)). In addition, its complement, where (i, j) is an edge iff (pi +pj )/2 > d, is
a threshold graph too. V C is solvable in linear time on threshold graphs, too, nevertheless
BP P C with a threshold conflict graph remains NP -hard.
Gendreau et al. (2004) describe the following generator, which we shall refer to as tgenerator: “A value pi was first assigned to each vertex i ∈ V according to a continuous
uniform distribution on [0, 1]. Each edge (i, j) of G was created whenever (pi + pj )/2 ≤ d,
where d is the expected density of G.” This generator clearly produces threshold graphs.
In addition, the expected edge density δ is not d as claimed. Actually, δ is a func2 −nd
tion of d (Bacci and Nicoloso (2017b)), precisely: δ = f (d) = 2(nd)
for d ≤ 0.5
n(n−1)
2

2

(1−d) −n(1−d)
and δ = f (d) = n(n−1)−2nn(n−1)
for d ≥ 0.5; here we recall some useful pairs
(d, δ): (0,0), (0.1,0.02), (0.2,0.08), (0.3,0.18), (0.4,0.32), (0.5,0.5), (0.6,0.68), (0.7,0.82),
(0.8,0.92), (0.9,0.98), (1,1).
This generator has been improperly used to generate arbitrary graphs, and, in particu-

12

B

0

0.1

0.2

0.3

0.4

∆

0.5

0.6

0.7

0.8

0.9

M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
tmin BN
tmax BN
tavg BN

120
0%
100%
1.68%
0%
0%
7.76%
0%
100%
1.68%
0%
0%
7.86%
0%
100%
1.69%
0%
0%
7.91%
0%
100%
1.74%
0%
0%
7.79%
0%
100%
1.82%
0%
0%
8.57%
0%
100%
1.95%
0%
0%
9.92%
0%
100%
2.37%
0%
0%
11.83%
0%
100%
5.53%
0%
0%
14.64%
0%
100%
3.78%
0%
0%
9%
0%
100%
2.61%
0%
0%
5.34%
0.3095
5.0831
1.8845

150
0%
45%
1.19%
0%
24%
1.4%
0%
51%
1.26%
0%
25%
1.5%
0%
45%
1.61%
0%
25%
1.85%
0%
33%
2.61%
0%
61%
2.29%
0%
32%
4.47%
0%
62%
3.51%
0%
41%
6.25%
0%
55%
5.62%
0%
76%
5.02%
0%
21%
7.04%
1%
100%
0.85%
0%
0%
2.81%
3%
92%
0.42%
0%
4%
1.14%
14%
87%
0.25%
1%
5%
0.73%
0.1534
2.2143
0.7478

180
0%
0%
0.89%
0%
97%
0.42%
0%
1%
1.04%
0%
90%
0.57%
0%
0%
1.75%
0%
98%
0.72%
0%
0%
3.63%
0%
100%
1.24%
0%
6%
6.21%
0%
92%
2.67%
0%
46%
4.93%
0%
48%
3.98%
4%
36%
0.79%
6%
46%
0.65%
32%
28%
0.22%
47%
46%
0.15%
71%
7%
0.06%
87%
23%
0.02%
85%
12%
0.02%
82%
8%
0.03%
0.0907
1.1515
0.367

210
0%
0%
3.27%
19%
100%
0.29%
0%
0%
1.61%
7%
100%
0.39%
0%
0%
2.51%
1%
100%
0.54%
0%
0%
4.83%
0%
99%
1.16%
0%
15%
6.56%
0%
83%
3.17%
2%
7%
1.16%
39%
84%
0.41%
24%
3%
0.44%
97%
76%
0.01%
62%
0%
0.14%
100%
38%
0%
98%
0%
0%
100%
2%
0%
100%
0%
0%
100%
0%
0%
0.0292
0.7193
0.2151

240
0%
0%
2.94%
54%
100%
0.18%
0%
0%
1.2%
32%
100%
0.28%
0%
0%
3.25%
7%
100%
0.42%
0%
0%
7.49%
0%
100%
1.19%
0%
1%
3.93%
17%
99%
1.19%
12%
3%
0.92%
94%
88%
0.02%
26%
0%
0.43%
100%
74%
0%
62%
0%
0.14%
100%
38%
0%
98%
0%
0%
100%
2%
0%
100%
0%
0%
100%
0%
0%
0.0294
0.4101
0.1319

270
0%
0%
2.59%
78%
100%
0.1%
0%
0%
1.38%
59%
100%
0.18%
0%
0%
4.1%
26%
100%
0.35%
0%
0%
8.29%
0%
100%
1.5%
2%
0%
2.61%
86%
98%
0.07%
17%
0%
0.88%
100%
83%
0%
26%
0%
0.43%
100%
74%
0%
62%
0%
0.14%
100%
38%
0%
98%
0%
0%
100%
2%
0%
100%
0%
0%
100%
0%
0%
0.0284
0.2772
0.095

300
0%
0%
2.34%
76%
100%
0.12%
0%
0%
1.6%
68%
100%
0.16%
0%
0%
4.92%
23%
100%
0.39%
0%
0%
7.18%
7%
100%
1.71%
3%
0%
2.55%
99%
97%
0%
17%
0%
0.88%
100%
83%
0%
26%
0%
0.43%
100%
74%
0%
62%
0%
0.14%
100%
38%
0%
98%
0%
0%
100%
2%
0%
100%
0%
0%
100%
0%
0%
0.0272
0.2165
0.0762

330
0%
0%
2.13%
81%
100%
0.1%
0%
0%
1.67%
72%
100%
0.15%
0%
0%
6.32%
19%
100%
0.47%
0%
0%
5.71%
57%
100%
0.41%
5%
0%
2.53%
100%
95%
0%
17%
0%
0.88%
100%
83%
0%
26%
0%
0.43%
100%
74%
0%
62%
0%
0.14%
100%
38%
0%
98%
0%
0%
100%
2%
0%
100%
0%
0%
100%
0%
0%
0.0275
0.1726
0.0638

360
0%
0%
1.98%
88%
100%
0.07%
0%
0%
1.91%
78%
100%
0.13%
0%
0%
7.65%
15%
100%
0.56%
0%
0%
5.31%
97%
100%
0.02%
5%
0%
2.52%
100%
95%
0%
17%
0%
0.88%
100%
83%
0%
26%
0%
0.43%
100%
74%
0%
62%
0%
0.14%
100%
38%
0%
98%
0%
0%
100%
2%
0%
100%
0%
0%
100%
0%
0%
0.0255
0.1419
0.0549

390
0%
0%
1.78%
87%
100%
0.08%
0%
0%
2.31%
79%
100%
0.14%
0%
0%
8.4%
10%
100%
0.67%
0%
0%
5.08%
100%
100%
0%
5%
0%
2.52%
100%
95%
0%
17%
0%
0.88%
100%
83%
0%
26%
0%
0.43%
100%
74%
0%
62%
0%
0.14%
100%
38%
0%
98%
0%
0%
100%
2%
0%
100%
0%
0%
100%
0%
0%
0.0255
0.1235
0.049

Table 1: Computational results obtained by algorithms M and algorithm BN on
T I(1000, B, ∆)

13

120

250

n

500

1000

M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN
M=LB
M<BN
Gap M
BN=LB
BN<M
Gap BN

{120.150}
11.95%
83.6%
4.91%
4.4%
1.25%
9.26%
6.15%
89.45%
4.07%
1.3%
2.95%
8.18%
3.75%
85.4%
2.99%
0.75%
6.8%
6.85%
0.9%
80.1%
2.44%
0.05%
14.1%
5.93%

180
44.4%
18.1%
2.23%
42.3%
13.8%
2.35%
33.8%
17.7%
2.07%
32.3%
26.2%
1.9%
27.2%
15.1%
1.92%
27.8%
46.6%
1.45%
9.6%
6.8%
0.98%
11.1%
32.4%
0.52%

B
{210. . . . .390}
65.84%
1.2%
1.52%
83.04%
22.73%
0.68%
47.63%
0.54%
1.72%
79.14%
47.41%
0.41%
37.64%
0.27%
1.87%
75.87%
61.47%
0.35%
30.27%
0.41%
2.05%
73.89%
69.26%
0.24%

{120. . . . .390}
52.92%
19.37%
2.27%
63.24%
17.54%
2.56%
37.95%
20.04%
2.23%
58.89%
36.4%
2.16%
29.82%
18.78%
2.1%
56.04%
49.05%
1.76%
23.29%
17.67%
2.12%
53.95%
57.78%
1.46%

Table 2: General results obtained by algorithms M and algorithm BN on T I(n, B, ∆)

lar, Muritiba et al. (2010) made publicly available (http://www.or.deis.unibo.it) instances
generated in this way and used by many authors (see list in Section 2). Sadykov and Vanderbeck
(2013) observed that the t-generator generates interval conflict graphs (and, in fact, their
Dynamic Programming phase is designed for interval graphs), but actually these graphs
are special interval graphs.
By T M(n, B, f (d)) we denote a set of ten instances with n items, bound B, and
threshold conflict graph with density f (d). In particular n ∈ {120, 250, 500, 1000},
and d ∈ {0, 0.1, . . . , 0.9}. The weights and the conflict graphs of all the T M(n, B, f (d))
are exactly those in the classes 1,2,3,4 by Muritiba et al. (2010). As for B, we considered
B ∈ {120, 150, . . . , 390} ∪ {400}, even if in the cited paper only B = 150 is considered. In
particular, Muritiba et al. (2010) select the first 10 instances of the 20 originally proposed
by Falkenauer (1996) for the Bin Packing (without conflicts), and add 10 random threshold conflict graphs generated by means of the t-generator, varying d from 0 to 0.9. The
Bin Packing instances proposed by Falkenauer (1996) have weights uniformly distributed
in [20, 100] and B = 150 because, as the author says, this setup was the most difficult
for the Bin Packing lower bound algorithms by Martello and Toth (1990). Nevertheless,
Gent (1998) easily solves the last five open instances. The instances T M(n, 150, f (d))
correspond to the so-called “u instances” by Sadykov and Vanderbeck (2013).
In order to verify how much the item weights affect the quality of the solution and/or
the computing time, we also decided to construct the T S instances: by T S(n, B, f (d)) we
will denote a set of ten instances with n items, bound B, and threshold conflict graph with
density f (d). The conflict graphs of a T S(n, ·, f (d)) are those of T M(n, ·, f (d)), and the
weights are uniformly distributed in [500, 2500]. We choose B ∈ {3000, 3750, . . . , 9750} ∪
{10000}. We remark that the item weights of T S(n, B, f (d)) are generated as the “instances with a larger number of items per bin” by Sadykov and Vanderbeck (2013) (the
so-called “d instances”), where, however, only B = 10000 is considered.
Let w be the average weight of an item, then the average number of items per bin
14

500

n

1000

tM=LB
tM<tBN
Gap tM
tBN=LB
tBN<tM
Gap tBN
tM=LB
tM<tBN
Gap tM
tBN=LB
tBN<tM
Gap tBN

{120, 150}
3%
85%
3.18%
0%
7%
5.97%
0.5%
82.5%
2.29%
0%
11.5%
4.96%

180
28%
9%
1.46%
31%
47%
0.61%
18%
4%
1.36%
29%
59%
0.39%

B
{210, . . . , 390}
78.57%
0.71%
0.76%
93%
28.57%
0.16%
77.43%
1%
0.69%
97.29%
28.71%
0.06%

{120, . . . , 390} ∪ {400}
58.4%
18.4%
1.32%
68.2%
26.1%
1.37%
56.1%
17.6%
1.08%
71%
28.3%
1.07%

Table 3: General results obtained by algorithms M and algorithm BN on T M(n, B, f (d))

is B/w. It is worth observing that the same number of items per bin is obtained in the
T M(n, B, f (d)) and in the T S(n, 25 × B, f (d)) instances.
Observe also that in the T S instances the number of different weights is 2500−500+1 =
2001. Hence, every weight is expected to appear in n/2001 copies. For a same n, the
(classical) Bin Packing underlying a T M instance recalls a Cutting Stock problem (see
Section 5) in a stronger way than the one underlying a T S instance.
In Table 3 we compare the results obtained by the heuristic algorithms M and BN over
T M(500, B, f (d)) and T M(1000, B, f (d)) (in column B ∈ {120, 150} the results are averaged over 2000 instances, in column B = 180 over 1000, in column B ∈ {210, . . . , 390} ∪
{400} over 8000, and in column B ∈ {120, . . . , 390} ∪ {400} over 11000).
The results of the heuristic algorithms M and BN over T S(500, B, f (d)) and
T S(1000, B, f (d)) can be found in Table 4 (in column B ∈ {3000, 3750} the results
are averaged over 2000 instances, in column B = 4500 over 1000, in column B ∈
{5250, . . . , 9750} ∪ {10000} over 8000, and in column B ∈ {3000, . . . , 9750} ∪ {10000}
over 11000).
We remind that the values in an arbitrary column in Table 3 (Table 4, respectively)
are the average of the values obtained on T M(n, B, f (d)) (T S(n, B, f (d)), respectively)
for the corresponding B’s and d = 0, 0.1, . . . , 0.9.
The results in Tables 3 and 4 show that the behaviour of each heuristic algorithm
w.r.t. the quality of the solution on the instances T M(n, B, f (d)) and T S(n, B, f (d)) is
essentially the same. We can note that BN outperforms M for B ≥ 180 on all the T M
instances and for the corresponding B ≥ 4500 on all the T S instances, i.e. when the
average number of items per bin is greater than or equal to 3.5.

7

Conclusions

In this paper we dealt with the Bin Packing Problem with Conflicts (BP P C) on instances
with interval conflict graphs.
We proposed a new heuristic algorithm for the problem. We conducted experiments
by varying the number n of items, the edge density of the conflict graph, the value
B, and the values of the weights, hence the average number of items per bin. We
remark that the experiments in the papers Basnet and Wilson (2005); Bettinelli et al.
(2014); Brandão and Pedroso (2016); Elhedhli et al. (2011); Gschwind and Irnich (2016);
Khanafer et al. (2012a, 2010, 2012b); Maiza and Guéret (2009); Maiza and Radjef (2011);
15

500

n

1000

sM=LB
sM<sBN
Gap sM
sBN=LB
sBN<sM
Gap sBN
sM=LB
sM<sBN
Gap sM
sBN=LB
sBN<sM
Gap sBN

{3000, 3750}
3%
83.5%
3.01%
0.5%
9%
5.78%
1%
87%
2.31%
0%
7.5%
5.13%

4500
31%
9%
1.52%
34%
52%
0.61%
24%
5%
1.46%
28%
59%
0.46%

B
{5250, . . . , 9750}
78.86%
0.86%
0.78%
95.86%
28.86%
0.15%
77.14%
1%
0.73%
90.43%
28.29%
0.09%

{3000, . . . , 9750} ∪ {10000}
58.9%
18.2%
1.3%
70.6%
27.2%
1.32%
56.6%
18.6%
1.12%
66.1%
27.2%
1.14%

Table 4: General results obtained by algorithms M and algorithm BN on T S(n, B, f (d))

Muritiba et al. (2010); Yuan et al. (2014) consider weights uniformly distributed in [20; 100],
B = 150, and threshold conflict graphs, only.
We compare the results of our algorithm to the results obtained by running a parameterized adaptation of three classical heuristic algorithms for BP . The results show that
our algorithm outperforms them definitively when the average number of items per bin is
greater than or equal to 3.5, both on instances with interval and threshold conflict graphs.
To our knowledge, no random interval graph generator exists which outputs a graph
with desired edge density. For this reason, we defined a new one with this properties, and
used it to generate thousands of instances on which, grouped by edge density, we tested
our algorithm.

References
T. Bacci and S. Nicoloso. Solving the bin packing problem with conflicts on interval
graphs to optimality. Manuscript, 2017a.
T. Bacci and S. Nicoloso. On the benchmark instances for the bin packing with conflicts,
2017b. arXiv:1706.03526 [math.CO].
B. S. Baker and E. G. Coffman. Mutual exclusion scheduling. Theoretical Computer
Science, 162:225–243, 1996.
C. Basnet and J. Wilson. Heuristics for determining the number of warehouses for storing
non-compatible products. International Transactions in Operations Research, 12:527–
538, 2005.
A. Bettinelli, V. Cacchiani, and E. Malaguti. Bounds and algorithms for the knapsack
problem with conflict graph. Technical Report OR-14-16, DEIS, University of Bologna,
July 2014.
H. L. Bodlaender and K. Jansen. Restrictions of graphs partition problem. Part I. Theoretical Computer Science, 148:93–109, 1995.
F. Brandão and J. P. Pedroso. Bin packing and related problems: General arc-flow
formulation with graph compression. Computers & Operations Research, 69:56–67,
2016.

16

R. Capua, Y. Frota, T. Vidal, and L. S. Ochi. Um algoritmo heurı̀stico para o problema
de bin packing com conflitos. Manuscript, 2015.
N. Christofides, A. Mingozzi, and P. Toth. Loading problems. In N. Christofides, A. Mingozzi, P. Toth, and C. Sandi, editors, Combinatorial Optimization, pages 339–369.
Wiley, Chichester, UK, 1979.
V. Chvátal and P. L. Hammer. Set-packing and threshold graphs. Technical Report Rept.
CORR 73-21, University of Waterloo, 1973.
F. Clautiaux, A. Khanafer, S. Hanafi, and E. Talbi. Le problème bi-objectif de bin-packing
avec conflits. Manuscript, 2011.
D. Cornaz, F. Furini, and E. Malaguti. Solving vertex coloring problems as maximum
weight stable set problems. Discrete Applied Mathematics, 217:151 – 162, 2017.
M. Delorme, M. Iori, and S. Martello. Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research, 255:
1–20, 2016.
S. Elhedhli, L. Li, M. Gzara, and J. Naoum-Sawaya. A Branch-and-Price algorithm for
the bin packing problem with conflicts. INFORMS Journal on Computing, 23:404–415,
2011.
L. Epstein and A. Levin. On bin packing with conflicts. SIAM Journal on Optimization,
19:1270–1298, 2008.
E. Falkenauer. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics,
2:5–30, 1996.
F. Gardi. Mutual exclusion scheduling with interval graphs or related classes, part i.
Discrete Applied Mathematics, 157:19–35, 2009.
M. R. Garey and D. S. Johnson. Strong NP-completeness results: motivation, examples,
and emplications. Journal ACM, 25:499–508, 1978.
M. Gendreau, G. Laporte, and F. Semet. Heuristics and lower bounds for the bin packing
problem with conflicts. Computers & Operations Research, 31:347–358, 2004.
I. P. Gent. Heuristic solution of open bin packing problems. Journal of Heuristics, 3:
299–304, 1998.
M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, 1980.
T. Gschwind and S. Irnich. Dual inequalities for stabilized column generation revisited.
INFORMS Journal on Computing, 28(1):175–194, 2016.
J. N. D. Gupta and J. C. Ho. A new heuristic algorithm for the one-dimensional binpacking problem. Production Planning & Control., 10(6):598–603, 1999.
R. Gupta, S. K. Bose, S. Sundarrajan, M. Chebiyam, and A. Chakrabarti. A two stage
heuristic algorithm for solving the server consolidation problem with item-item and
bin-item incompatibility constraints. In Proceedings of the 2008 IEEE International
Conference on Services Computing - Volume 2, pages 39–46. IEEE Computer Society,
2008.
17

K. Jansen and S. Oehring. Approximation algorithms for time constrained scheduling.
Information and Computation, 132(2):85 – 108, 1997.
D. S. Johnson. Fast algorithms for bin packing. Journal of Computer and System Sciences,
8:272–314, 1974.
C. Joncour. Problèmes de placement 2D et application à l’ordonnancement: modélisation
par la théorie des graphes et approches de programmation mathématique. PhD thesis,
Université de Bordeaux I, July 2010. Number 4173.
C. Joncour, S. Michel, R. Sadykov, D. Sverdlov, and F. Vanderbeck. Column generation
based primal heuristics. Electronic Notes in Discrete Mathematics, 36:695–702, 2010.
S. B. Jouida, A. Ouni, and S. Krichen. A multi-start tabu search based algorithm for solving the warehousing problem with conflict. In H. A. Le Thi, T. Pham Dinh, and N. T.
Nguyen, editors, Modelling, Computation and Optimization in Information Systems and
Management Sciences: Proceedings of the 3rd International Conference on Modelling,
Computation and Optimization in Information Systems and Management Sciences MCO 2015 - Part II, pages 117–128. Springer International Publishing, 2015.
J. Justicz, E. R. Scheinerman, and P. M. Winkler. Random intervals. American Mathematical Monthly, 97:881–889, 1990.
R. Kalfakakou, S. Katsavounis, and K. Tsouros. Minimum number of warehouses for
storing simultaneously compatible products. International Journal of Production Economics, 81-82:559–564, 2003.
A. Khanafer. Algorithmes pour des problèmes de bin packing mono- et multi-objectif. PhD
thesis, Université Lille1, 2010. Number 40363.
A. Khanafer, F. Clautiaux, and E. Talbi. New lower bounds for bin packing problems
with conflicts. European Journal of Operational Research, 206(2):281–288, 2010.
A. Khanafer, F. Clautiaux, S. Hanafi, and E. Talbi. The min-conflict packing problem.
Computers & Operations Research, 39:2122–2132, 2012a.
A. Khanafer, F. Clautiaux, and E. Talbi. Tree-decomposition based heuristics for the twodimensional bin packing problem with conflicts. Computers & Operations Research, 39:
54–63, 2012b.
D. Kowalczyk and R. Leus. An exact algorithm for parallel machine scheduling with
conflicts. Journal of Scheduling, 2016. DOI: 10.1007/s10951-016-0482-0.
M. Maiza and C. Guéret. A new lower bound for bin packing problem with general
conflicts graph. In 1st Doctoriales STIC’09, Université de M’sila, Algérie, 2009.
M. Maiza and M. S. Radjef. Heuristics for solving the bin-packing problem with conflicts.
Applied Mathematical Sciences, 5:1739 – 1752, 2011.
S. Martello and P. Toth. Lower bounds and reduction procedures for the bin packing
problem. Discrete Applied Mathematics, 28:59–70, 1990.
F. A. E. Muritiba. Algorithms and Models For Combinatorial Optimization Problems.
PhD thesis, Alma Mater Studiorum Università di Bologna, 2010.
18

F. A. E. Muritiba, M. Iori, E. Malaguti, and P. Toth. Algorithms for the bin packing
problem with conflicts. In XIII Workshop on Combinatorial Optimization, 2009.
F. A. E. Muritiba, M. Iori, E. Malaguti, and P. Toth. Algorithms for the bin packing
problem with conflicts. INFORMS Journal on Computing, 22(3):401–415, 2010.
Y.S. Myung. On the clique partitioning problem in weighted interval graphs. Theoretical
Computer Science, 396:290 – 293, 2008.
R. Sadykov and F. Vanderbeck. Bin packing with conflicts: a generic Branch-and-Price
algorithm. INFORMS Journal on Computing, 25(2):244–255, 2013.
I. Vasileios. Random interval graphs. Master’s thesis, University of Essex, 2005.
Y. Yuan, Y. Li, and Y. Wang. An improved aco algorithm for the bin packing problem with
conflicts based on graph coloring model. 21th International Conference on Management
Science & Engineering, Helsinki, Finland, 2014.

19

