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.
JansenK. An approximation scheme for bin packing with conflicts. Journal of Combinatorial Optimization1999; 3: 363–377.
5.
BasnetCWilsonJ. Heuristics for determining the number of warehouses for storing non-compatible products. Int Trans Operational Res2005; 12: 527–538.
6.
Ben JouidaSKrichenS. A DSS based on optimizer tools and MTS meta-heuristic for the warehousing problem with conflicts. Information Processing Letters2018; 135: 14–21.
7.
ChristofidesNMingoziATothP. Combinatorial optimization. London: John Wiley and Sons, 1979.
8.
MassonRVidalTMichalletJ, et al.An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems. Expert Systems with Applications2013; 40: 5266–5275.
9.
JansenKÖhringS. Approximation algorithms for time constrained scheduling. Information and Computation1997; 132: 85–108.
10.
MuritibaAEFIoriMMalagutiE,et al.Algorithms for the bin packing problem with conflicts. INFORMS Journal on Computing2010; 22: 401–415.
11.
JohnsonDS. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences1974; 9: 256–278.
12.
ElhedhliSLiLGzaraM,et al.A branch-and-price algorithm for the bin packing problem with conflicts. INFORMS Journal on Computing2011; 23: 404–415.
13.
SadykovRVanderbeckF. Bin packing with conflicts: a generic branch-and-price algorithm. INFORMS Journal on Computing2013; 25: 244–255.
14.
YuanYLiYWangY. 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ãoFPedrosoJP. Bin packing and related problems: general arc-flow formulation with graph compression. Computers & Operations Research2016; 69: 56–67.
16.
CapuaRFrotaYOchiLS,et al.A study on exponential-size neighborhoods for the bin packing problem with conflicts. J Heuristics2018; 24: 667–695.
17.
El-AshmawiWHSalahABekhitM, et al.An adaptive jellyfish search algorithm for packing items with conflict. Mathematics2023; 11: 3219.
18.
HuangZZhangADósaG, et al.Improved approximation algorithms for bin packing with conflicts. Int J Found Comput Sci2023; 0: 1–16. https://doi.org/10.1142/S0129054122460054.
19.
EkiciA. Bin packing problem with conflicts and item fragmentation. Computers & Operations Research2021; 126: 105113.
20.
EkiciA. Variable-sized bin packing problem with conflicts and item fragmentation. Computers & Industrial Engineering2022; 163: 107844.
21.
EkiciA. A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts. European Journal of Operational Research2023; 308: 1007–1020.
22.
MaizaMSaid RadjefMSaisL. Efficient lower bounds for packing problems in heterogeneous bins with conflicts constraint. In: AnastassiouGADumanO (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.
KhanaferAClautiauxFTalbiE-G. Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts. Computers & Operations Research2012; 39: 54–63.
24.
FleszarK. A MILP model and two heuristics for the bin packing problem with conflicts and item fragmentation. European Journal of Operational Research2022; 303: 37–53.
25.
TsaoY-CTaiJ-YVuT-L,et al.Multiple bin-size bin packing problem considering incompatible product categories. Expert Systems with Applications2024; 247: 123340.
26.
RodriguesGDACunhaCBGuarino NetoL,et al.An adaptive large neighborhood search metaheuristic for the generalized bin packing problem with incompatible categories. Computers & Industrial Engineering2023; 185: 109586.
Hamdi-DhaouiKLabadieNYalaouiA. Algorithms for the two dimensional bin packing problem with partial conflicts. RAIRO-Oper Res2012; 46: 41–62.
29.
MartelloSTothP. Lower bounds and reduction procedures for the bin packing problem. Discrete Applied Mathematics1990; 28: 59–70.
30.
DyerMEWalkerJ. Dominance in multi-dimensional multiple-choice knapsack problems. Asia-Pacific Journal of Operational Research1998; 15: 159.
31.
AndonovRPoirriezVRajopadhyeS. Unbounded knapsack problem: dynamic programming revisited. European Journal of Operational Research2000; 123: 394–407.
32.
AlvimACFRibeiroCCGloverF,et al.A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics2004; 10: 205–229.
33.
LewisR. A general-purpose hill-climbing method for order independent minimum grouping problems: a case study in graph colouring and bin packing. Computers & Operations Research2009; 36: 2295–2310.
34.
Fanjul-PeyroLRuizR. Size-reduction heuristics for the unrelated parallel machines scheduling problem. Computers & Operations Research2011; 38: 301–309.
35.
MartelloSTothP. An upper bound for the zero-one knapsack problem and a branch and bound algorithm. European Journal of Operational Research1977; 1: 169–175.
36.
MartelloSTothP. An exact algorithm for large unbounded knapsack problems. Operations Research Letters1990; 9: 15–20.
37.
FukunagaAS. A branch-and-bound algorithm for hard multiple knapsack problems. Ann Oper Res2011; 184: 97–119.
38.
AnY-JKimY-DChoiS-W. Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times. Computers & Operations Research2016; 71: 127–136.
39.
DammakAElloumiAKamounH. Classroom assignment for exam timetabling. Advances in Engineering Software2006; 37: 659–666.
MarzoukMKamounH. Nurse to patient assignment through an analogy with the bin packing problem: case of a Tunisian hospital. Journal of the Operational Research Society2021; 72: 1808–1821.
42.
CaccettaLAlameenMAbdul-NibyM. An improved clarke and wright algorithm to solve the capacitated vehicle routing problem. Eng Technol Appl Sci Res2013; 3: 413–415.
43.
Abdul-NibyMAlameenMSalhiehA,et al.Improved genetic and simulating annealing algorithms to solve the traveling salesman problem using constraint programming. Eng Technol Appl Sci Res2016; 6: 927–930.
44.
KumarΤMSinghΝA. Environmental economic dispatch with the use of particle swarm optimization technique based on space reduction strategy. Eng Technol Appl Sci Res2019; 9: 4605–4611.
