Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction and Problem Positioning

The purpose of this paper, is to investigate the problem of determining the minimal possible cost generated by the use of heterogeneous warehouses required in a supply chain to store given items, where some of the items are in conflicting with each other, and cannot be stored together in the same warehouse. We say with compatible items the items that can be stored simultaneously in the same warehouse, otherwise they are called incompatible items. This problem occur in a number of industrial and transportation contexts within a supply chain where generally we prospect to ask the best transfer cost of diverse available products. For example, a manufacturing company has to ship n customer orders from its factory to a distribution center. All shipments are carried out by leased trucks and several truck sizes are available with different leasing costs. Besides, some customer orders cannot be stored simultaneously in the same truck for reasons of deterioration or to avoid fire danger. The problem is to determine the least-cost fleet mix and size for shipping all the orders with the respect of compatibility constraint. It is convenient to associate with the problem a conflict graph \(G=(V;E)\), where an edge \((i;i^{\prime })\in E\) exists if and only if items i and \(i^{\prime }\) are the incompatible items. This problem which we called in what follows the Variable Sized Bin-Packing Problem with Conflicts (VSBPPC) is strongly NP-hard since it generalizes both the Variable Sized Bin Packing Problem (VSBPP) in which all items are mutually compatible, and the Vertex Coloring Problem (VCP) in which all items weights take value 0. Also, it is clear that the particular case where we consider only one type of warehouses (i.e. all warehouses are identical) turns out to be the studied one-dimensional Bin Packing Problem with Conflicts (BPPC).

Although the VSBPPC is NP-hard with important real world application, few works which it investigate are outlined. Indeed, only the online version of this problem has been addressed by [1] and [2] whose the goal was to pack all items into a set of bins with a minimum total size. In this version, a set of unpacked items is defined at the beginning of the assignment and heterogeneous bins arrive one by one. Before arriving of such a bin, authors proposed and analyzed the asymptotic competitive ratio of algorithms need to decide on which items to pack into the existing bin. Whereas, in this paper we address the offline version of the VSBPPC which can be showed as a common problem with many other combinatorial problems such as the BPPC, VSBPP and VCP where we considered them as a particular cases of described problem. So, these problems has been extensively investigated in numerous papers and therefore we restrict our reviewing to the papers which are used heuristics approaches that we will base to solve a problem in the remainder of this paper.

For solving the VSBPP, it is worth to note that [3] proposed and analyzed two variants of the well-known first-fit decreasing and best-fit decreasing algorithms. They show that these algorithms give a solution which is less than \(\frac{3}{2}c_{opt}+1\) for the general case where \(c_{opt}\) refers to the value of an optimal cost solution. Haouari and Serairi [4] proposed four constructive greedy heuristics based on iteratively solving a subset-sum problem, together with a set-covering based heuristic and a genetic based algorithm. Performances of their proposition are analyzed on a large set of randomly generated test instances with up to seven bin-type and 2000 items. Among the proposed greedy heuristics, the best compromise between solution quality and running time is obtained by the named SSP3 heuristic. In [5], the same authors proposed six different lower bounds for the VSBPP where the number of bins for each bin-type is limited, as well as an exact algorithm. They show that the particular case with all size items larger than a third the largest bin capacity can be restated and solved in polynomial-time as a maximum-weight matching problem in a non-bipartite graph. Introducing the conflict constraints, it is noteworthy to studies the propriety of the conflicts graph, but most problem are also NP-hard for the arbitrary conflicts graph, particularly the VCP and the maximal clique search problem. These last problems are extensively discussed in the literature. Johnson [6] described an efficient polynomial greedy heuristic to determine the largest clique set. This heuristic method initializes the clique with the vertex of maximum degree in the graph and then adds successive vertices each of which has edges with all the vertices already included in the clique. At each iteration, vertices are considered according to a decreasing degree order. Thereafter, this greedy heuristic was widely applied to solve numerous related problems such as the BPPC where the main heuristic approaches resolution available in the literature are those given in [7, 8], in which authors surveyed previous results in the literature, presented new lower and upper bounds, and introduced benchmark instances.

Based on these cited works, this paper aimed at providing new lower and upper bounds for the VSBPPC. So, it is organized as follows: in the next section (Sect. 2) we provide the description and the mathematical formulation of our problem. Then, we present in the followed section (Sect. 3) our new lower bounds based on both the computation of the maximal clique set and the relaxation scheme of the mathematical formulation. Finally, we close this paper in Sect. 4 with concluding remarks.

2 Problem Description and Formulation

The VSBPPC is formally defined as follows; Given a set V of n items of sizes \(w_{1},w_{2},\ldots ,w_{n}\) with

$$\begin{aligned} w_{1}\geqslant w_{2}\geqslant \cdot \cdot \cdot \geqslant w_{n}, \end{aligned}$$

where we it associate an undirected graph named as a conflict graph \(G=(V;E)\) such that \((i,i^{\prime })\in E\) when the two items i and \(i^{\prime }\) of V are incompatible items. Likewise, given m different bin-types (Categories of warehouses), each bin-type j \((j=1,\ldots ,m)\) includes an infinite number of identical bins (bins are warehouses), each having a capacity \(W_{j}\) and a fixed cost \(c_{j}\) with

$$\begin{aligned} W_{1}\leqslant W_{2}\leqslant \cdot \cdot \cdot \leqslant W_{m} \end{aligned}$$

and

$$\begin{aligned} c_{1}\leqslant c_{2}\leqslant \cdot \cdot \cdot \leqslant c_{m}. \end{aligned}$$

The VSBPPC problem consists in assigning each items from V into one bin while ensuring that no bin contains incompatible items and the cumulated size in each bin does not exceed its capacity and the total cost of the needed bins is minimized. Without loss of generality, we assume that the data is deterministic and presented in off-line mode and that the largest item can be assigned at least to one type of bins \(\left( w_{1}\leqslant W_{m}\right) \). Note that if \(c_{j}>c_{j^{\prime }}\) for \(1\leqslant j<j^{\prime }\leqslant m\) then bin-type j is dominated and should therefore not be considered.

The VSBPPC can be formulated as an integer linear program (ILP). Let \( x_{ij_{k}}\) be a binary variable equal to 1 if and only if item i is assigned to bin k of bin-type j and 0 otherwise, and let \(y_{j_{k}}\) be a binary variable equal to 1 if and only if bin k of bin-type j is used, 0 otherwise. The formulation is then

$$\begin{aligned} \min \sum \limits _{j=1}^{m}\sum \limits _{k=1}^{n}c_{j}y_{j_{k}}, \end{aligned}$$
(1)
$$\begin{aligned} \text {s.t.} \ \ \sum \limits _{j=1}^{m}\sum \limits _{k=1}^{n}x_{ij_{k}}=1,i=1,\ldots ,n, \end{aligned}$$
(2)
$$\begin{aligned} \sum \limits _{i=1}^{n}w_{i}x_{ij_{k}}\le W_{j}y_{j_{k}},j=1,\ldots ,m,\text { } k=1,\ldots ,n, \end{aligned}$$
(3)
$$\begin{aligned} x_{ij_{k}}+x_{i^{\prime }j_{k}}\leqslant 1,(i,i^{\prime })\in E\quad j=1,\ldots ,m,\text { }k=1,\ldots ,n, \end{aligned}$$
(4)
$$\begin{aligned} x_{ij_{k}}\in \{0,1\},i=1,\ldots ,n\quad j=1,\ldots ,m,\text { }k=1,\ldots ,n, \end{aligned}$$
(5)
$$\begin{aligned} y_{j_{k}}\in \{0,1\},j=1,\ldots ,m\text {, }k=1,\ldots ,n. \end{aligned}$$
(6)

The objective function to be minimized (1) represents the cost of the bins used to pack all items. Constraint (2) ensures that each item i has to be packed. Constraint (3) indicates that the amount packed in each bin does not exceed the capacity of this bin, whereas, constraint (4) make sure that each incompatible pair \((i,i^{\prime })\) of items does not assigned to the same bin. Finally, constraints (5) and (6) restrict decision variables to be binary. Note that the above ILP without constraint (4) is the well formulation of the VSBPP without conflict.

In the remaining of the paper we will use the definition of extended conflict graph \(G^{\prime }(V,E^{\prime })\) where

$$\begin{aligned} E^{\prime }=E\cup \left\{ (i,i^{\prime }):i,i^{\prime }\in V \text{ and } w_{i}+w_{i^{\prime }}>W_{m}\right\} . \end{aligned}$$

3 Lower Bounds

We have developed two lower bounds \(L_{1}\) and \(L_{2}\) for the VSBPPC in order to provide the means to measure the solution quality of the various procedure and also to be used as performance criterion of the heuristics developed in the next section. Obtained through the resolution of the relaxed mathematical formulation, these lower bounds are based on the principle of relaxing the constraint (5) which ensures that each item should be entirely—not in fractional way—assigned to such a bin. The similarly principle has been adopted on splitting-based lower bound of [5] for the VSBPP without conflicts—denoted in what follows \(L_{0}\)-. This last bound is based on the resolution of the relaxation problem (7)–(9) where authors consider the set S of large items in which each item should be fit alone, only in the largest bin. Therefore one bin is initialized for each item in this set, and only the remaining items in \( V\setminus S\) are assigned in a fractional way to the residual capacity of initialized bins and possibly to other new bins.

$$\begin{aligned} L_{0}=\min \sum _{j=1}^{m}c_{j}x_{j}+qc_{m} \end{aligned}$$
(7)

s.t.

$$\begin{aligned} \sum _{j=1}^{m}W_{j}x_{j}\geqslant & {} \sum _{i=q+1}^{m}w_{i}-\min \left( qW_{m}-\sum _{i=1}^{q}w_{i},\sum _{i=p}^{m}w_{i}\right) \end{aligned}$$
(8)
$$\begin{aligned} x_{j}\in & {} \mathbb {N};\text { }j=1,\ldots ,m, \end{aligned}$$
(9)

\(x_{j}\), q and p are respectively, the number of bins of type j, the largest index of item such that \(w_{q}>\max \left( W_{m-1},\frac{W_{m}}{2} \right) \), and the smallest index of item such that \(w_{q}+w_{p}\leqslant W_{m}\).

The VSBPPC can be shown as a particular case of the VSBPP in which the corresponding conflicts graph is the discrete graph \(D_{n}\) of order n ( G(V, E) with \(E=\emptyset \); Graph without edges in which all the items are mutually compatible). Therefore, any lower bound for the VSBPP without conflicts is also a valid lower bound for the problem with conflicts. Indeed, if the total cost of packing of such an instance without a conflicts constraint is defined then it is trivial to constant that by addition of restrictions on the packing process, this initial cost increases or, in the worst cases, remains unchanged. Then we have

$$\begin{aligned} L_{0}=L(D_{n})\leqslant L(G), \end{aligned}$$
(10)

where L(G) is any lower bound for the VSBPPC with conflicts graph G.

Now, consider the case where the conflicts graph is a complete graph \((K_{n}) \) of n items in which each item should be loaded into a distinct bin (A complete graph is defined here as a graph in which every pair of items is mutually incompatible). Under the assumption imposed on this paper (\( W_{1}<W_{2}<\cdot \cdot \cdot <W_{m}\) and \(c_{1}<c_{2}<\cdot \cdot \cdot <c_{m}\)), each item should be loaded in the smallest possible (i.e. cheapest) bin that fits. Then the problem becomes to finding for each item the smallest index of bin-type that which can fit and therefore the optimal cost solution \(c_{opt}(K_{n})\) that is also the VSBPPC lower bound for a complete conflicts graph \(L(K_{n})\) can be given in O(n) time as follows.

Define \(q_{j}(j=1,\ldots ,m)\) be the largest index of item i such as \( W_{j-1}<w_{i}\leqslant W_{j}\) with \(W_{0}=0\).

$$\begin{aligned} L(K_{n})=c_{opt}(K_{n})=\sum _{j=1}^{m}c_{j}\left( q_{j}-q_{j-1}\right) \text{ with } q_{0}=0. \end{aligned}$$
(11)

By definition, the value \((q_{j}-q_{j-1})\) is the number of items with size \( w_{i}\) in \([W_{j-1},W_{j}]\). The cost obtained by formula (11) represents an optimal solution for the problem (1)–(6) where the constraints (4) is instantiated for each items pair. Obviously, this optimal cost solution is an upper bound for the VSBPPC in which we cannot be increases when we have to relaxing or to remove some instances of this constraint, which is the case of the VSBPPC with no complete conflicts graph. Then from formulas (10) and (11), we have

$$\begin{aligned} L_{0}=L(D_{n})\leqslant L(G)\leqslant L(K_{n})=c_{opt}(K_{n}). \end{aligned}$$
(12)

Here again, we derive our lower bounds for the VSBPPC for the general conflicts graph. The main principle of our proposition can be summarized in the three following steps:

  1. 1.

    Find the maximal clique set \(V_K\) from the conflicts graph;

  2. 2.

    Initialize one bin for each item of \(V_K\);

  3. 3.

    Assign the items of \(V \setminus V_K\) into the initialized bins in fractional way and possibly into new bins without considering the conflicts.

The two last steps will be carried out by solving the relaxed mathematical formulation and both lower bounds \(L_1\) and \(L_2\) execute the same procedure to solve this mathematical model. The main difference between these two propositions lies in how to obtain the maximal clique set (Step 1). Indeed, finding the maximal clique set \(V_K\) is also an NP-hard problem. In \(L_1\) this set is determined by application of Johnson’s [6] greedy heuristic directly on the extended conflicts graph \(G^{\prime }(V,E^{\prime })\). Whilst in \(L_2\), it is obtained through Muritiba’s improvement computation [8] where authors compute the large clique set on the initial conflicts graph G(V; E) using Johnson’s greedy heuristic and remove this set from the graph G, then from the obtained partial graph, they updating the set E to \(E^{\prime }\) and enlarge the initial clique by added items from this new partial extended conflicts graph using constantly Johnson’s greedy heuristic. In [8], authors indicate that this strategy leads to larger cliques set than those obtained by applying the Johnson’s algorithm directly on the extended conflicts graph.

Now, consider the following notation:

  • \(V_K\): a set of a maximal clique from the extended conflict graph \(G^{\prime }(V,E^{\prime })\);

  • \(\overline{V}_K\): a complement set of \(V_K\) in V (\(\overline{V}_K = V \setminus V_K\));

  • \(\overline{s}=\sum _{i \in \overline{V}_K} w_i\) be the total items size of the set \(\overline{V}_K\).

Obviously, each item from \(V_K\) should be assigned into a distinct bin that can fits and consequently we have to initialize \(|V_K|\) bins at least. Let \( j^{*}\) be the smallest index of bin-type that can receive the smallest item of the clique set (\(W_{j^{*}} \geqslant \underset{i \in V_K}{\min }(w_i)\)), and consider the partition of \(V_K\) into the subsets \(V_h\) as follows:

$$\begin{aligned} V_h= \left\{ i\in V_K : W_{h-1} < w_i \leqslant W_h \right\} \text{ for } h=j^{*},\ldots ,m. \end{aligned}$$

Clearly, each item i from \(V_{h}\) \((h=j^{*},\ldots ,m.)\) should be assigned alone into one bin from a selected bin-type j \(j\in [h,m]\) . Let \(y_{hj}\) be the number of bins of type j \((j=h,\ldots ,m)\) that are used for packing the items of subset \(V_{h}\). Then, we have

$$\begin{aligned} \sum _{j=h}^{m}y_{hj}=|V_{h}| \text{ for } h=j^{*},\ldots ,m \end{aligned}$$
(13)

Also, the assignment of any item from \(V_{h}\) into one bin of a given bin-type j (\(j\in [h,m]\)) generates a residual capacity \(\widetilde{ W}_{hj}\) that it is at most equal to \(W_{j}-min_{i\in V_{h}}w_{i}\). In the calculation of our lower bound, the residual capacity will be occupied with the items of \(\overline{V}_{K}\) without considering the conflicts in this last subset. Hence, for every bin-type j and for a given subset \(V_{h}\), the maximum value of \(\widetilde{W}_{hj}\) can be obtained by solving the following subset sum problem (SSP)

$$\begin{aligned} \widetilde{W}_{hj}=\text{ Max }\sum _{i\in \overline{V}_{K}}w_{i}z_{i} \end{aligned}$$
(14)

s.t.

$$\begin{aligned} \sum _{i\in \overline{V}_{K}}w_{i}z_{i}\leqslant W_{j}-\underset{i\in V_{h}}{ \min }w_{i} \end{aligned}$$
(15)
$$\begin{aligned} z_{i}\in \{0,1\},i\in \overline{V}_{K} \end{aligned}$$
(16)

Both lower bounds consist in the resolution of the VSBPPC by relaxing the integrality constraints in which we assume that only items from \(\overline{V} _K\) might be split. For that, define an integer variable \(\overline{y}_j\) as the number of added bins of type j used for complete the packing of the items of \(\overline{V}_K\) set. Then, we have to solve the following mathematical programming formulation

$$\begin{aligned} LB=\text{ Min }\left( \sum _{j=1}^{m}c_{j}\overline{y}_{j}+\sum _{h=j^{*}}^{m}\sum _{j=h}^{m}c_{j}y_{hj}\right) \end{aligned}$$
(17)

s.t.

$$\begin{aligned} \sum _{j=h}^{m}y_{hj}=|V_{h}| h=j^{*},\ldots ,m \end{aligned}$$
(18)
$$\begin{aligned} \sum _{j=1}^{m}W_{j}\overline{y}_{j}+\sum _{h=j^{*}}^{m}\sum _{j=h}^{m}W_{j}y_{hj}\geqslant \sum _{i\in V}w_{i} \end{aligned}$$
(19)
$$\begin{aligned} \sum _{j=1}^{m}W_{j}\overline{y}_{j}+\sum _{h=j^{*}}^{m}\sum _{j=h}^{m} \widetilde{W}_{hj}y_{hj}\geqslant \sum _{i\in \overline{V}_{K}}w_{i} \end{aligned}$$
(20)
$$\begin{aligned} \overline{y}_{j}\in \mathbb {N},j=1,\ldots ,m \end{aligned}$$
(21)
$$\begin{aligned} y_{hj}\in \mathbb {N},h=j^{*},\ldots ,m j=h,\ldots ,m. \end{aligned}$$
(22)

The objective function (17) is to minimize the total cost of required bins (both the additional bins that are added for complete the packing of items from \(\overline{V}_K\) and the bins used for the packing of items from the maximal clique set \(V_K\)). Constraint (18) is derived from formula (13) ensure that each item of the maximal clique set \(V_K\) is packed into a distinct bin. Constraint (19) ensures that the total capacity of used bins enables to pack all the items. Constraint (20) informs that the residual capacities generated by the packing of the maximal clique items together with the capacity of additional bins are enable to pack the set of items from \(\overline{V}_K\). Whilst, formulas (21) and (22) represent the integrality constraints.

4 Conclusion

The variable sized bin-packing problem with conflicts is an NP-hard combinatorial problem often encountered in the practical field; it generalizes both the bin-packing problem with heterogeneous bins and the vertex coloring problem, both well known and notoriously difficult. In this paper, we have addressed the offline version of this problem, where we have proposed two variant of lower bound based on the combination of the clique computation and the constraint relaxing formulation.

Finally, considering the practical relevance of discussed problem and the fact that the offline version of this problem has not been excessively addressed in the literature, this work can be considered as a comparison basis for the future works.