Exact and approximate size reduction for the bin packing problem with conflicts

Abstract

The current paper focuses on the design of size reduction procedures for large-scale Bin Packing Problem with Conflicts (BPPC). The NP-hard complexity of the problem makes size reduction a valuable preprocessing step for the resolution process. Based on some newly established theorems, we provide a set of three relevant procedures for optimal and approximate size reductions. An optimal (respectively, approximate) size reduction of a BPPC instance stands for an optimal (respectively, approximate) placement of a subset of items into a particular bin. The first procedure generalizes Martello and Toth's dominance criterion, initially developed for the Bin Packing Problem (BPP). The other two procedures are designed to deal with special graph structures. Examples are used throughout this work to exhibit the operational mechanism of these reduction procedures. The related numerical results demonstrate the efficiency of the elaborated dominance criteria and illustrate the computational time complexity of the size reduction procedures for special graph structures.

Keywords

combinatorial optimization bin packing problem with conflicts size reduction dominance criteria heuristics

1. Introduction

Let V be a set of n items, and W their associated positive weights {w₁, w₂, …, w_n}. These items are to be packed in identical bins, each with a maximum capacity of Q. In the present paper, the objective of the BPPC is to place all items into as few bins as possible while ensuring that no bin's capacity is surpassed and the items filled in each bin are non-conflicting. A conflict between items (i and j) is represented by an edge (i, j) ∈ E in the problem-associated graph G = (V, E). The BPPC is classified as an NP-hard problem.¹ Indeed, it is a generalization of two other strongly NP-hard problems: the BPP and the vertex coloring (VCP).² The BPP (respectively, the VCP) is a special case of the BPPC if E = ∅︀ (respectively if all items’ weights are equal to zero). The studied problem was formulated in¹ as a binary integer program (BIP).

Let indices i and j represent items in the set {1, 2, …n}, and let the index k represent a bin in the set of possible bins {1, 2, …n}.

\begin{aligned} y_{k} = {\begin{array}{cc} 1 & If the bin k is used \\ 0 & otherwise \end{array} \end{aligned}

\begin{aligned} x_{i k} = {\begin{array}{cc} 1 & If item i is assigned to bin k \\ 0 & otherwise \end{array} \end{aligned}

\begin{aligned} M i n i m i s e \sum_{k = 1}^{n} y_{k} \end{aligned}

(1)

\begin{aligned} S u b j e c t t o \\ \sum_{k = 1}^{n} x_{i k} = 1 \forall i = 1, \dots, n \end{aligned}

(2)

\begin{aligned} \sum_{i = 1}^{n} w_{i} x_{i k} \leq Q . y_{k} \forall k = 1, \dots ., n \end{aligned}

(3)

\begin{aligned} x_{i k} + x_{j k} \leq y_{k} \forall (i, j) \in E, k = 1, \dots ., n \end{aligned}

(4)

\begin{aligned} x_{i k} \in {0, 1} \forall i, k = 1, \dots, n \end{aligned}

(5)

\begin{aligned} y_{k} \in {0, 1} \forall k = 1, \dots, n \end{aligned}

(6)

The objective function (1) of the BIP aims to minimize the required number of bins. Constraints (2) and (3) guarantee, respectively, that each item is assigned to only one bin and that the total weight of items placed in bin k does not exceed its capacity Q. The set (4) of restrictions avoids combining conflicting items in a single bin. The remaining constraints define the types of decision variables.

BPPC finds applications in multiple areas, including exam scheduling,³ where the room capacities (representing bins) must be respected, and no student (representing items) can be scheduled for more than one exam at the same time (representing conflicts between items). The problem also arises in tasks-to-processor assignments,⁴ involving allocating tasks to processors while respecting conflict constraints, where certain tasks cannot run on the same processor due to dependencies or resource conflicts. The objective here is to minimize the number of processors employed. Another application is found in managing warehousing and vehicle loads for incompatible products,^5,6,7 where some of them cannot be stored and transported together due to safety (flammable and explosive items) or quality concerns (contamination risks, temperature sensitivity, chemical reactions, etc.). This has led to a set of conflict constraints, ensuring that certain products are not placed in the same warehouse or vehicle. Therefore, we need to determine the minimum number of required warehouses and vehicles. The BPPC emerges also in the field of cloud computing.⁸ Here, the challenge is to assign processes to server machines, considering that none of two processes from the same service is placed on the same server.

The key contributions of the current work include: (i) the generalization of a dominance criterion to be applied to the BPPC, (ii) the development of a polynomial-time algorithm to reduce problem instances with an associated conflict-free subgraphs, and (iii) the construction of an approximate procedure to address problem instances with an associated conflicting subgraphs.

The remainder of this paper is organized as follows. Section 2 reviews the related work. In section 3, we adapt a dominance criterion initially proposed for the BPP to effectively address potential conflicts among items. Section 4 is dedicated to developing a theorem and its corresponding procedure, utilizing conflict-free subgraphs to reduce the size of the problem. Section 5 builds on the results from the previous section to handle subgraphs with partial conflicts. The conclusion and possible future research directions are presented in the final section.

2. Literature review

The BPPC was first considered in⁹ within the context of a time-constrained scheduling problem. The authors developed multiple approximation algorithms to solve a set of special cases. In,¹ approximate methods that are based on the First-Fit Decreasing (FFD) rule, graph coloring, and clique computations are developed to solve our studied problem. Furthermore, a lower bound (LB) for the BPPC is derived using a transportation-based formulation.¹⁰ derived new bounds that are later employed in a branch and price (B&P) algorithm to address the BPPC. The authors in¹⁰ introduced improvements in the clique-based LB developed in¹ by enlarging the conflict clique via a non-increasing degree order. The resulting clique is generally more extensive than the one determined by Johnson's algorithm.¹¹ Likewise,² proposed an improved set of LBs based on dual-feasible functions and data-dependent dual-feasible functions. The authors in¹² applied the B&P algorithm to investigate the BPPC and claimed that its efficiency is due to the efficiency of maximal clique valid inequalities associated with the conflict constraints. Besides, they stated that their algorithm outperforms the one described in.¹⁰ Similarly,¹³ proposed a B&P algorithm where a dynamic programming algorithm will perform the pricing if the graph associated with items’ conflicts is an interval graph. Otherwise, the pricing will be performed via a branch and bound algorithm if the graph structure is not recognized. An ant colony optimization algorithm followed by an adapted version of the FFD algorithm was applied in.¹⁴ The authors in¹⁵ used graph compression and a new formulation based on the arc flow to consider the BPPC. They highlighted its superiority in solving several challenging cutting and packing problem instances within a relatively short time. A multi-start tabu search algorithm was used in⁶ to tackle a warehousing problem modeled as a BPPC.¹⁶ presented a new heuristic powered by multiple neighborhood structures and speeded up by fast evaluative procedures to measure each move's quality.¹⁷ used the jellyfish metaheuristic and adopted special solution representations to deal with the BPPC.¹⁸ designed algorithms for special graph structures and determined their absolute approximation ratios. Ekici¹⁹ investigated the BPPC where items can be fragmented, and demonstrated that the studied problem is NP-hard. Moreover, he proves that packing oversized items that are exceeding bin capacity does not necessarily yield an optimal solution, which may seem counterintuitive. Based on this remark, a LB determining procedure and a heuristic algorithm for solving the problem are proposed. Ekici²⁰ focused on a variant of the previously studied problem in which the capacities and costs of the bins are not necessarily the same. The goal here is to minimize the cost of packing all items. In addition, he presented a new LB for the problem and proposed an efficient novel heuristic. He further explored the BPPC in²¹ by proposing a new tight LB and provided a successful local search routine combined with a large neighborhood search algorithm to solve the problem.²² addressed the BPPC and proposed LBs for the optimal cost of placing all items into bins. On examining the 2-dimensional variant of the BPPC,²³ put forward approximate algorithms based on the tree-decomposition paradigm. Fleszar²⁴ investigated a variant of the BPPC where each item can be partitioned between two or more bins and developed a new mixed integer linear program (MILP) formulation for the problem, identifying it as a generalized transportation problem. In addition, he elaborated new heuristics to fill the bins based on the MILP solution of subproblems.²⁵ examined the three-dimensional BPP of variable size with compatible categories, where the bins are boxes and certain categories of items cannot be packed with items from other categories. The authors begin with an initial solution generated by the FFD algorithm, which is subsequently enhanced using simulated annealing and genetic algorithms.²⁶ focused on the generalized BPP with incompatible categories where some items are not mandatory to deliver. An efficient adaptive large neighborhood search is provided and tested against BPP with compatible categories and its generalized variant. A closely related problem is addressed in,²⁷ where there are a fixed number of available bins, so as to minimize the total number of conflicts detected in all used bins. In addition to investigating the mono-objective problem,²⁷ explored another multi-objective variant to balance the number of conflicts and that of the used bins. Another related problem examined in²⁸ is the two-dimensional BPP in which a minimum safe distance is required to separate incompatible items. The authors in²⁸ formulated the problem as an integer linear program and proposed a multi-start genetic algorithm.

The size reduction for the BPPC refers to subtracting a subset of items and their associated conflicts from the problem instance under consideration immediately after their assignment to some bins as part of an optimal/approximate solution. The dominance criteria generally lead to a reduction in search space. They are mainly used as a preprocessing step before problem-solving^29–31 or for deriving an approximate solution.^32–37 In addition, the dominance criteria can help obtain better LBs or accelerate the search for an optimal solution.^31,38–41

Size reduction is crucial for effectively solving problems with a BPP structure. A well-known size reduction procedure, referred to as MTRP, was developed by Martello and Toth.²⁹ It enables optimal assignments of subsets of items to bins while improving the problem lower bound. By relying on weight ordering, the size reduction procedures are developed in⁴² to help reduce the classroom assignment problem for exam timetabling. Later,⁴³ formulated the problem outlined in⁴² as an oversized BPP and applied further reductions based again on weight ordering and dominance criterion. Recently, a new variant of size reduction has been adopted to deal with healthcare-related problems with a bin packing structure.⁴⁴ The developed size reduction procedure enables finding the optimal solution to the patient-to-nurse assignment problem in a neonatal intensive care unit in Tunisian hospitals.

To the best of our knowledge, the only research addressing size reduction for BPPC is the work by Khanafer et al.² By applying a size reduction procedure initially designed for the knapsack problem, they established lower bounds for the two-dimensional BPPC by accurately determining the reserved space needed for item heights and widths. Moreover, they extended the approach introduced by Carlier et al.,¹¹ utilizing cliques in the graph to model conflicts between items.

3. The modified Martello and Toth dominance criterion for the BPPC

3.1. The Martello and Toth dominance criterion for the BPPC

The MTRP for the BPP can be used to approximately solve the BPPC. Indeed, given two distinct sets of items F₁ and F₂ that are feasible with respect to capacity and conflicts; if there exists a partition P = {P₁, …, P_l} of F₂ and a subset of items:{i₁…, i_l} of F₁ such that $\sum_{k \in P_{h}} w_{k} \leq w_{i_{h}} f o r h = 1, \dots, l$ , then it is considered most probable that F₁ would dominate F₂. We use the term most probable since the MTRP is exclusively designed to fit the BPP, with regard to which set of conflict constraints is not considered.

3.2. The new dominance criterion

This section introduces a novel dominance criterion theorem, enabling the reduction of the BPPC size under certain conditions. We define exact reduction as arranging a subset of items within a bin so that it leads to at least one optimal solution. The bin associated with this arrangement is fixed and selected as part of that optimal solution. Subsequently, the items and the bin they are contained in are removed from any further consideration.

Definition 1:
Given a positive integer Q denoting the capacity of the bin and a set of items C_i conflicting with the item i. A set of items F is called feasible if and only if: 1)
$\sum_{i \in F} w_{i} \leq Q$
2)
$\underset{i \in F}{\cup} C_{i} \cap F = ϕ$
The first constraint ensures that the cumulative weight of the items in set F remains within the limits of the bin's capacity. The second constraint ensures that there is no conflict between items in F.
Definition 2:
Given two feasible sets of items F₁ and F₂ (see Definition 1). We have that F₁ dominates F₂ if the overall number of bins utilized within the optimal solution, by assigning items in F₁ to a bin B₁ (noted, B₁= F₁), is less than or equal to the one obtained by assigning items in F₂ to the bin B₁ (noted, B₁= F₂).
Theorem 1:
Let F₁ and F₂ be two feasible sets of items (see Definition 1). If F₂ can be split into partitions {P₁,…, P _l } and the items in F₁= {i₁,…, i _l } satisfy
$\begin{matrix} 1) \sum_{k \in P_{h}} w_{k} \leq w_{i_{h}} f o r h = 1, \dots, l \\ 2) \underset{k \in P_{h}}{\cup} C_{k} \subseteq C_{i_{h}} f o r h = 1, \dots, l \end{matrix}} t h e n F_{1} d o m i n a t e s F_{2}$

Proof:
we are considering any feasible solution, where B₁= F₂, we can derive an alternative feasible solution with an equal or smaller number of bins by exchanging each partition P_h in F₂ with an item i_h in F₁ (i.e., B₁= F₁). The interchange is feasible since both constraints related to bin capacity (1) and items’ conflicts (2) are satisfied. Therefore, F₁ dominates F₂.

Given that the VCP, as previously discussed, is a special case of BPPC, the relevance of this size reduction procedure becomes even more significant. Specifically, the first condition of theorem 1 will always hold for VCP, since the item's weights are zero in such cases. This means that the developed theorem optimizes the BPPC and offers a new method for reducing the size of another NP-hard problem: the VCP.
3.3. The second criterion of Theorem 1 is sufficient but not necessary

3.3.1. A BPPC instance where both criteria of Theorem 1 are satisfied

Here, we present a BPPC instance where Q = 95, n = 9 (the corresponding indices are indicated in the upper left corner of each item's rectangle), with associated weights (appearing in bold inside each rectangle) and conflicts (represented by edges connecting two rectangles) are shown in Figure 1.

Figure 1.

Instance 1 of a BPPC with nine items and their conflicts that need to be packed into the minimum number of bins.

A possible solution to the above problem instance (Figure 1) is illustrated in Figure 2. Before delving into size reduction and dominance considerations, we must first confirm that the corresponding bins meet the feasibility criteria in terms of both capacity limitations and item conflicts. Given that each item in {4, 6, 8} is conflicting with each item in {5, 7, 9} and since we are looking for the dominating bin containing at least one item from the set {4, 6, 8}, we can conclude by applying theorem 1 that the bin B₁ ={4, 6, 8} dominates any bin containing a feasible subset of items {1, 2, 3, 4, 6, 8}. As a result of Theorem 1, B₁ can be reduced with all embedded items. Indeed, the first criterion of Theorem 1 is satisfied since each partition P₁= {1}, P₂= {2}, P₃= {3} can be associated respectively with items i₁= {4}, i₂= {6}, i₃= {8}, given that $\sum_{k \in P_{h}} w_{k} \leq w_{i_{h}} f o r h = 1, 2, 3$ . As required by the second criterion, each set of conflicts C₁, C_2, and C₃ are included in the set of conflicts C₄, C₆, and C₈, respectively. The dominance criteria are not applicable for the remaining items 5, 7, and 9 since they conflict with the items in B₁. It is worth mentioning that the solution illustrated in Figure 2 proves to be optimal. In addition, the optimal solution illustrated in Figure 2 showed that the sets of non-conflicting items {4, 6, 8}, {3, 9}, {2, 7} and {1, 5} are packed in the four bins B₁, B₂, B₃ and B₄ respectively.

Figure 2.

The optimal solution of instance 1 where four bins are used to pack the nine items.

3.3.2. A BPPC instance where only the first criterion of Theorem 1 is satisfied

Figure 3 represents the optimal solution of a new instance (instance 2). It consists of the same problem instance discussed in Figure 1, but now it includes an additional item (item 10) and a different set of conflicts (represented by edges connecting two rectangles). In this optimal solution, the set of items {6, 7}, {4, 5}, {1, 2, 3, 10}, {8, 9} are assigned to the four bins B₁, B₂, B₃ and B₄ respectively.

Figure 3.

Optimal solution to instance 2, using four bins to pack ten items while respecting conflicts.

Assume that we apply the reduction procedure considering only the first criterion of Theorem 1 while disregarding the second. In this case, bin B₁ will be reduced, as it dominates all other possible bins. Since item i = 10 is conflicting with items in {5, 7, 9}. Consequently, it can only be packed with the remaining items: {1, 2, 3, 4, 6, 8}, as indicated in Figure 3.

Regarding the BPP, Martello and Toth²⁹ state that if a feasible set of items F, including item i, dominates any other feasible set of items, including item i, then the set F representing a bin will be part of an optimal solution. Hence, the bin containing item i = 10 and items {4, 6, 8} would dominate all other bins containing item i = 10. As a result of the conflict constraints, the remaining items must be placed in at least four additional bins. Consequently, the overall number of utilized bins rises to five. Figure 4 shows, through the considered instance, that the only application of the first criterion can prevent from reaching the optimal number of used bins (four as in Figure 3). Note that applying only the first criterion of Theorem 1 will not necessarily remove the set of all optimal solutions. Therefore, the minimum number of bins used will not necessarily increase.

Figure 4.

From instance 2, the bin B₁ containing items {4, 6, 8, 10} is reduced by applying only criterion 1 of theorem 1.

Figure 5 illustrates an optimal solution of a third instance (instance 3) where Q = 95 and n = 10. This shows that all items are packed in four bins with the following assignment B₁= {7, 6}; B₂= {4, 5}; B₃= {1, 2, 3, 10}; B₄= {8, 9}.

Figure 5.

Optimal solution to instance 3, using four bins to pack ten items while respecting conflicts.

By applying only the first criterion of Theorem 1 (the second is not satisfied), we found another optimal solution having the same number of used bins with the following assignment: B₁= {3, 9}; B₂= {2, 7}; B₃= {5, 1}; B₄= {4, 6, 8, 10} (see Figure 6). This indicates that the second criterion is sufficient but not necessary for an exact reduction.

Figure 6.

Another optimal solution to instance 3, using four bins to pack ten items while respecting conflicts.

3.4. The modified MTRP procedure for the BPPC

The following procedure, which aims at reducing the size of the problem, is based on Theorem 1:

Two main issues need to be highlighted when considering reducing the BPPC through Theorem 1:

Procedure 1 might not be efficiently implemented in an acceptable computational time, as it examines all possible reductions. A relaxed version could, therefore, be adopted to limit the number of items included in each bin to three at most. While satisfying the first criterion of Theorem 1, the second criterion could be very restrictive and stand as an obstacle to the problem size reduction. To settle this issue, we have recourse to approximate size by partially relaxing the above criterion, which we dub a “q-approximate reduction”. It consists of accepting that, at most q conflicts of those appearing in $\underset{k \in P_{h}}{\cup} C_{k}$ are not included in $C_{i_{h}}$ for each h = 1… l. Thus, it is clear that two scenarios are possible when applying a q-approximate reduction, namely:

The optimal solution is discarded (additional bins are necessary): This case is illustrated in Figure 4, wherein the set $\underset{k \in P_{h}}{\cup} C_{k}$ associated with each partition P₁= {1}, P₂= {2}, P₃= {3} is not included in the set $C_{i_{h}} = ϕ$ associated with items i₁= 4, i₂= 6, i₃= 8, respectively. In this case, applying a 3-approximate reduction will lead to a non-optimal solution.

The optimal solution is not discarded: Figure 6 illustrates the inverse case, wherein the optimal solution is still reachable even when applying a 3-approximate reduction.

4. Size reduction based on conflict-free subgraphs

This section will show that, in specific circumstances, the BPPC instance has the potential to be reduced in polynomial time.

Theorem 2:
For each item i, find the subset of items ${\bar{C}}_{i}$ that do not conflict with item i. If all items in {i}∪ ${\bar{C}}_{i}$ are non-conflicting, and their total weight remains within the bin capacity Q, then it is possible to reduce the problem size by packing all items in {i}∪ ${\bar{C}}_{i}$ within the same bin as a part of an optimal BPPC solution.
Proof:
Assume an instance of a BPPC where for some item i ∈ V, the vertices induced by {i}∪ ${\bar{C}}_{i}$ , form a stable set, and $\sum_{k \in (i ⋃ {\bar{C}}_{i})} w_{k} \leq Q$ . If in an optimal solution, an item j ∈ ${\bar{C}}_{i}$ is placed in a bin B_k that does not contain item i, we can obtain another optimal solution by moving item j to the bin containing item i, as it is feasible by hypothesis, with respect to both capacity and conflict constraints. The minimum number of the used bins remains unchanged, as the new solution only differs from the original optimal solution by placing item j in the bin containing item i, where, according to the hypothesis ( $\sum_{k \in (i ⋃ {\bar{C}}_{i})} w_{k} \leq Q$ ), sufficient space exists for item j.

Example:

Let V = {1, 2, …9} be a set of items to be packed in bins with capacity Q = 150. The set of conflicts and weights associated with all items are illustrated in Figure 7.
Figure 7.
A BPPC instance where the set of items {1, 6, 7, 8, 9} are packed within the same bin as part of an optimal solution.

Since the item {1} and those in ${\bar{C}}_{1}$ = {6, 7, 8, 9} are non-conflicting, and their total weight (equal to 140) is less than or equal to Q, then the items {1, 6, 7, 8, 9} are packed together within the same bin as part of an optimal BPPC solution. Observe this set of items enclosed by a dashed line in Figure 7.

Based on Theorem 2, a resultant procedure labeled ICFR (Item Conflict Free Reduction) is detailed as follows:

The ICFR procedure (in line 7) strives to retrieve the non-conflicting items in NC_i with item i in G’, including item i. If the items included in NC_i are non-conflicting and the sum of all their weights remains below the limit of the bin's capacity Q, we can place them all into a single bin. Based on Theorem 2, this latter bin will be part of an optimal solution. Due to the conflict constraints, no additional items can be inserted into this new bin. Besides, if any item j ∈ NC_i is not packed into this bin, an additional one may be required in a non-optimal solution. The first loop (line 5) takes at most n iterations to consider all items. Searching the set NC_i and checking that all contained items are non-conflicting (lines 7 and 8) is O(n²). A new problem instance arises when we successfully reduce the problem size (lines 9 and 10). Therefore, the counter i will be initialized (line 11). Due to the polynomial complexity of ICFR (O(n⁴)), executing this procedure before starting any approximate reduction is beneficial.
5. Size reduction based on subgraphs with conflicts

In the above section, we studied the case where all items in NC_i are non-conflicting. In this section, we proceed to consider the other case wherein some items in NC_i are conflicting.

Theorem 3
For each item i ∈ V within the G = (V, E), find the set of items ${\bar{C}}_{i}$ that have no conflicts with item i. Suppose now that there are some conflicts between items in ${\bar{C}}_{i}$ . Let NC_i= {i}∪ ${\bar{C}}_{i}$ and let F_i ⊂ NC_i be any stable set of non-conflicting items containing the item i. If the cumulative weight of items in any set F_i does not surpass the bin's capacity Q, then there is a bin in an optimal solution containing one of these feasible sets of items F_i.
Proof:
Since each set of items F_i, associated with each stable set containing item i, are non-conflicting and their total weight does not exceed Q, then each set F_i of items can be placed within a bin. The fact of not assigning an item j in the set F_i to a bin is not beneficial. Otherwise, item j may require an additional bin for packing, which results in increasing the number of bins employed. Given that we cannot withdraw any item (i.e., there is no benefit in doing so), nor can we include any additional item in the set F_i (due to conflict constraints), there is no other efficient feasible set of items other than those associated with all stable sets F_i. Consequently, one of these possibilities will be in an optimal assignment.

Based on Theorem 3, a resulting approximate size reduction procedure called SWCR (subgraph with conflict reduction) is developed. The SWCR procedure begins with identifying items that have no conflict with item i and including item i, noted as NC_i (line 7). Once determined, it creates a graph G_i, as a subgraph of G’, induced by the set of vertices in NC_i (line 8). If some items in the set NC_i are conflicting, each connected component of G_i reflects the existence of conflicts between some (and not necessarily all) items associated with it. The procedure searches for all connected components of G_i (line 9). By looking for the chromatic number (approximately) associated with each connected component (line 11), we attempt to partition the set of items induced by this component into stable sets or, equivalently, into sets of non-conflicting items. We select a single stable set from each connected component of the graph G_i. These stable sets are then merged to form a single set of non-conflicting items (line 12). Given the large number of possible stable set combinations, we set a maximum of t_i iterations. We proceed with selecting the combination (of stable sets F_i) associated with the maximum cumulative weight within the capacity limit Q. We assign the items associated with this combination of stable sets to a new bin $B_{i}^{m a x}$ . The latter (i.e., items included in $B_{i}^{m a x}$ ), are removed from the associated BPPC graph as an approximate size reduction (line 14). The reduced problem is forwarded to the ICFR procedure to look for any further possible exact reductions (line 15).

Example:

Consider a set V = {1, 2, …9} of items to be packed in bins with capacity Q = 100. The item's associated weights and conflicts are illustrated in Figure 8. Note that there exist only three feasible sets of items likely to be packed with the item i = 1, which are: {1, 6, 9}, {1, 7, 9} and {1, 8, 9}. Hence, at least one optimal solution will likely include one of these three subsets that are packed into a single bin.

Figure 8.
Size reduction of a BPPC instance, including conflicts in the subgraph induced by items {1, 6, 7, 8, 9}.

As indicated in Figure 8, for i = 1, the set NC₁ that is enclosed by a dashed line is {1, 6, 7, 8, 9}.

The subgraph G₁ induced by the set NC₁ are illustrated in Figure 9. The components of G₁ are: $N_{1}^{1} = {1}$ , $N_{1}^{2} = {6, 7, 8}$ and $N_{1}^{3} = {9}$ .
$χ (N_{1}^{1}) = 1$ , $S_{1, 1} = {S_{1, 1}^{1}} = {1};$

$χ (N_{1}^{2}) = 3$ , $S_{1, 2} = {S_{1, 2}^{1}, S_{1, 2}^{2}, S_{1, 2}^{3}}$ , where $S_{1, 2}^{1} = {6}, S_{1, 2}^{2} = {7}, S_{1, 2}^{3} = {8};$

$χ (N_{1}^{3}) = 1$ , $S_{1, 3} = {S_{1, 3}^{1}} = {9};$

Figure 9.
The subgraph G₁ showing conflicts between items {6, 7, 8}.

Based on the SWCR procedure, we will determine the bin with the highest weight including the item i = 1. The set of efficient eligible bins are:

B₁= {1, 6, 9} with a total weight of 40 + 30 + 28 = 98, B₂= {1, 7, 9} with a total weight of 40 + 25 + 28 = 93 and B₃= {1, 8, 9} with a total weight of 40 + 20 + 28 = 88. Since the weight of all these bins does not exceed the bin capacity Q = 100 and the bin B₁ has the highest weight, consequently $B_{1}^{m a x} = B_{1}$ (see ligne 13 in SWCR). The items contained in $B_{1}^{m a x}$ are now subtracted from G’, and the problem size is reduced. The obtained graph will now contain the following set of items {2, 3, 4, 5, 7, 8} with their associated conflicts (see Figure 10).

Figure 10.
Graph G’ obtained after the first iteration of SWCR where the bin $B_{1}^{m a x} = 1, 6, 9$ is reduced from the initial graph.

For i = 2 (and after excluding items reduced in the first iteration), the set NC₂= {2, 4, 5, 8} and its induced subgraph G₂ are depicted in Figure 11. Since the items included in NC₂ are non-conflicting with each other, and as: $W_{N C_{2}} = \sum_{j \in N C_{2}} w_{j} \leq Q$ , then, by applying the ICFR procedure (line 15), the items {2, 4, 5, 8} will be loaded into one bin as a second size reduction and then subtracted from G’.

Figure 11.
The subgraph induced by the set NC₂= {2, 4, 5, 8} is packed in the same bin as a reduction from the actual graph.

For i = 3, the set NC₃= {3, 7} and its associated induced subgraph G₃ resulting from the previous iteration are illustrated in Figure 12. In fact, as the conflict and capacity constraints are satisfied, we have recourse to the ICFR procedure, and the items {3, 7} are loaded into one bin as a last size-reduction phase.

Figure 12.
The last subgraph induced by the set NC₃= {3, 7} is packed in the same bin as a reduction from the actual graph.

Given that the LB L₁ = $⌈ \frac{\sum_{i \in V} w_{i}}{Q} ⌉ = 3$ , then, the size-reduction-based solution: B₁: {1, 6, 9}; B₂: {2, 4, 5, 8}; B₃: {3,7} ends up being an optimal solution to the addressed BPPC instance.
6. Conclusion

The size-reduction problem-solving technique is essential in addressing combinatorial optimization problems as it may substantially reduce the size of the problem instance under consideration. In addition, it displays a lower bound improvement capability and is even apt to solve certain problem instances entirely. In the present paper, we extend the dominance criterion proposed in,²⁹ initially designed to address the BPP, to tackle the generalized case, wherein conflicts between packed items are considered. In addition, we developed two theorems related to subgraphs with and without conflicts and proposed exact and approximate size-reduction procedures. It is noteworthy, however, that the proposed reduction procedures are usually insufficient to solve any BPPC instance. Throughout the problem-solving process, the size reduction procedure is successful in some iterations, yet unfeasible in others.

It is worth noting that most research on the BPPC has focused directly on finding an optimal solution. However, the feasible solution space for this combinatorial optimization problem is typically too large to reach the optimum within an acceptable time frame. Very few studies have tackled the size reduction of this NP-hard problem as a preprocessing step before attempting its resolution. Our work aims to bridge this gap by introducing procedures that reduce the problem's scale without eliminating all optimal solutions. The effectiveness of these new procedures is established through theorems with rigorous mathematical proofs. On this basis, the current study could be extended to address size reduction for other related NP-hard problems. In fact, while size reduction alone cannot generally solve the entire problem, its effectiveness can be significantly enhanced when hybridized with approximate methods, particularly metaheuristics, as noted by.¹⁷ Additionally, integrating size reduction with exact methods (e.g., branch and bound or branch and cut) is expected to drastically reduce the number of nodes to be explored, which ultimately helps in decreasing the required computational time. Furthermore, while the current approach reduces only one bin per iteration, future studies could aim to develop methods that eliminate multiple bins simultaneously, thereby accelerating the search for an optimal solution.

Footnotes

Acknowledgments

The authors extend their appreciation to the Deanship of Scientific Research at Northern Border University, Arar, KSA for funding this research work “through the project number “NBU-FFR-2024-2234-02”. They also sincerely thank the anonymous reviewers for their valuable and constructive comments, which have substantially improved the quality of the paper.

ORCID iD

Wassim Zahrouni

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

References

Gendreau

Laporte

Semet

. Heuristics and lower bounds for the bin packing problem with conflicts. Computers & Operations Research 2004; 31: 347–358.

Khanafer

Clautiaux

Talbi

E-G

. New lower bounds for bin packing problems with conflicts. European Journal of Operational Research 2010; 206: 281–288.

Laporte

Desroches

. Examination timetabling by computer. Computers & Operations Research 1984; 11: 351–360.

Jansen

. An approximation scheme for bin packing with conflicts. Journal of Combinatorial Optimization 1999; 3: 363–377.

Basnet

Wilson

. Heuristics for determining the number of warehouses for storing non-compatible products. Int Trans Operational Res 2005; 12: 527–538.

Ben Jouida

Krichen

. A DSS based on optimizer tools and MTS meta-heuristic for the warehousing problem with conflicts. Information Processing Letters 2018; 135: 14–21.

Christofides

Mingozi

Toth

. Combinatorial optimization. London: John Wiley and Sons, 1979.

Masson

Vidal

Michallet

, et al. An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems. Expert Systems with Applications 2013; 40: 5266–5275.

Jansen

Öhring

. Approximation algorithms for time constrained scheduling. Information and Computation 1997; 132: 85–108.

10.

Muritiba

AEF

Iori

Malaguti

, et al. Algorithms for the bin packing problem with conflicts. INFORMS Journal on Computing 2010; 22: 401–415.

11.

Johnson

. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 1974; 9: 256–278.

12.

Elhedhli

Gzara

, et al. A branch-and-price algorithm for the bin packing problem with conflicts. INFORMS Journal on Computing 2011; 23: 404–415.

13.

Sadykov

Vanderbeck

. Bin packing with conflicts: a generic branch-and-price algorithm. INFORMS Journal on Computing 2013; 25: 244–255.

14.

Yuan

Wang

. An improved ACO algorithm for the bin packing problem with conflicts based on graph coloring model. In: 2014 International conference on management science & engineering 21th annual conference proceedings. Helsinki: IEEE, 2014, pp.3–9. https://doi.org/10.1109/ICMSE.2014.6930200.

15.

Brandão

Pedroso

. Bin packing and related problems: general arc-flow formulation with graph compression. Computers & Operations Research 2016; 69: 56–67.

16.

Capua

Frota

Ochi

, et al. A study on exponential-size neighborhoods for the bin packing problem with conflicts. J Heuristics 2018; 24: 667–695.

17.

El-Ashmawi

Salah

Bekhit

, et al. An adaptive jellyfish search algorithm for packing items with conflict. Mathematics 2023; 11: 3219.

18.

Huang

Zhang

Dósa

, et al. Improved approximation algorithms for bin packing with conflicts. Int J Found Comput Sci 2023; 0: 1–16. https://doi.org/10.1142/S0129054122460054.

19.

Ekici

. Bin packing problem with conflicts and item fragmentation. Computers & Operations Research 2021; 126: 105113.

20.

Ekici

. Variable-sized bin packing problem with conflicts and item fragmentation. Computers & Industrial Engineering 2022; 163: 107844.

21.

Ekici

. A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts. European Journal of Operational Research 2023; 308: 1007–1020.

22.

Maiza

Said Radjef

Sais

. Efficient lower bounds for packing problems in heterogeneous bins with conflicts constraint. In: Anastassiou

Duman

(eds) Intelligent mathematics II: applied mathematics and approximation theory, vol. 441. Cham: Springer International Publishing, 2016, pp.263–270. https://doi.org/10.1007/978-3-319-30322-2_18.

23.

Khanafer

Clautiaux

Talbi

E-G

. Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts. Computers & Operations Research 2012; 39: 54–63.

24.

Fleszar

. A MILP model and two heuristics for the bin packing problem with conflicts and item fragmentation. European Journal of Operational Research 2022; 303: 37–53.

25.

Tsao

Y-C

Tai

J-Y

T-L

, et al. Multiple bin-size bin packing problem considering incompatible product categories. Expert Systems with Applications 2024; 247: 123340.

26.

Rodrigues

GDA

Cunha

Guarino Neto

, et al. An adaptive large neighborhood search metaheuristic for the generalized bin packing problem with incompatible categories. Computers & Industrial Engineering 2023; 185: 109586.

27.

Khanafer

Clautiaux

Hanafi

, et al. The min-conflict packing problem. Computers & Operations Research 2012; 39: 2122–2132.

28.

Hamdi-Dhaoui

Labadie

Yalaoui

. Algorithms for the two dimensional bin packing problem with partial conflicts. RAIRO-Oper Res 2012; 46: 41–62.

29.

Martello

Toth

. Lower bounds and reduction procedures for the bin packing problem. Discrete Applied Mathematics 1990; 28: 59–70.

30.

Dyer

Walker

. Dominance in multi-dimensional multiple-choice knapsack problems. Asia-Pacific Journal of Operational Research 1998; 15: 159.

31.

Andonov

Poirriez

Rajopadhye

. Unbounded knapsack problem: dynamic programming revisited. European Journal of Operational Research 2000; 123: 394–407.

32.

Alvim

ACF

Ribeiro

Glover

, et al. A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics 2004; 10: 205–229.

33.

Lewis

. A general-purpose hill-climbing method for order independent minimum grouping problems: a case study in graph colouring and bin packing. Computers & Operations Research 2009; 36: 2295–2310.

34.

Fanjul-Peyro

Ruiz

. Size-reduction heuristics for the unrelated parallel machines scheduling problem. Computers & Operations Research 2011; 38: 301–309.

35.

Martello

Toth

. An upper bound for the zero-one knapsack problem and a branch and bound algorithm. European Journal of Operational Research 1977; 1: 169–175.

36.

Martello

Toth

. An exact algorithm for large unbounded knapsack problems. Operations Research Letters 1990; 9: 15–20.

37.

Fukunaga

. A branch-and-bound algorithm for hard multiple knapsack problems. Ann Oper Res 2011; 184: 97–119.

38.

Y-J

Kim

Y-D

Choi

S-W

. Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times. Computers & Operations Research 2016; 71: 127–136.

39.

Dammak

Elloumi

Kamoun

. Classroom assignment for exam timetabling. Advances in Engineering Software 2006; 37: 659–666.

40.

Elloumi

Kamoun

Jarboui

, et al. The classroom assignment problem: complexity, size reduction and heuristics. Applied Soft Computing 2014; 14: 677–686.

41.

Marzouk

Kamoun

. Nurse to patient assignment through an analogy with the bin packing problem: case of a Tunisian hospital. Journal of the Operational Research Society 2021; 72: 1808–1821.

42.

Caccetta

Alameen

Abdul-Niby

. An improved clarke and wright algorithm to solve the capacitated vehicle routing problem. Eng Technol Appl Sci Res 2013; 3: 413–415.

43.

Abdul-Niby

Alameen

Salhieh

, et al. Improved genetic and simulating annealing algorithms to solve the traveling salesman problem using constraint programming. Eng Technol Appl Sci Res 2016; 6: 927–930.

44.

Kumar

ΤM

Singh

ΝA

. Environmental economic dispatch with the use of particle swarm optimization technique based on space reduction strategy. Eng Technol Appl Sci Res 2019; 9: 4605–4611.