Bin Packing Problem with Conflicts on interval graphs

Definition

The Bin Packing Problem with Conflicts (BPPC) on interval graphs is defined as follows: given an interval graph G = (V, E) (called conflict graph), a nonnegative integer weight w_i for each vertex i of G, and a nonnegative integer B, find a partition of V into the minimum number of subsets, such that the sum of the weights of the vertices assigned to a same subset is less than or equal to B and two vertices connected by an edge do not belong to the same subset.

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 interval I_p = ( x_p, y_p ) of the real line, and two vertices p,q ∈ V are connected by edge iff the corresponding intervals intersect, i.e. x_p < y_q and x_q < y_p.

Figure 1 presents an instance of BPPC and its optimum solution. A set of 12 weighted intervals is given (a) and the corresponding interval graph is showed (b), where the indices of the intervals are indicated with black numbers and the weights with red numbers. By setting B = 100, the nodes of an optimum solution have the same colour if they belong to the same subset (c).

CTW 2020 instances

The set of instances used for CTW2020 is available here (for details about file format see readme.txt)

Test Instances

The name of each instance is in the format "X_n_d_count.txt", where X ∈ {TI, TT, TS, TM} denotes the type of the instance (for more details see here), n is the number of nodes/intervals, d is the edge density class (d = 0, 2, 8, 10, ..., 90 means edge density ≈ 0%, 2%, 8%, 10%, ..., 90%) and count is the identification number from 1 to 100. A detailed description of the data set and computational results of some heuristic and exact procedures on these instances are available here.

All the instances are available in the following format:

hello

n : number of intervals

x_i : left endpoint of interval i

y_i : right endpoint of interval i

w_i : weight of interval i

hello

Download

- TI: instances with interval conflict graph and weights in [20;100]  (n∈{120,250,500,1000})

- TT: instances with threshold conflict graph and weights in [20;100]  (n∈{120,250,500,1000})

- TS: instances with threshold conflict graph and weights in [500;2500]  (n∈{120,250,500,1000})

- TM: instances of classes 1, 2, 3, 4 presented in "F. A. E. Muritiba, M. Iori, A. Malaguti, and P. Toth. Algorithms for the bin packing problem with conflicts. INFORMS Journal on Computing, 22(3):401–415, 2010" in our format (the instances in the original format are available here)