We address the two-dimensional bin packing problem with fixed orientation. This problem requires packing a set of small rectangular items into a minimum number of standard two-dimensional bins. It is a notoriously intractable combinatorial optimization problem and has numerous applications in packing and cutting. The contribution of this paper is twofold. First, we propose a comprehensive theoretical analysis of lower bounds and we elucidate dominance relationships. We show that a previously presented dominance result is incorrect. Second, we present the results of an extensive computational study that was carried out, on a large set of 500 benchmark instances, to assess the empirical performance of the lower bounds. We found that the so-called Carlier-Clautiaux-Moukrim lower bounds exhibits an excellent relative performance and yields the tightest value for all of the benchmark instances.
Accepté le :
DOI : 10.1051/ro/2017019
Mots-clés : Two-dimensional bin packing, lower bounds, dual feasible functions, dominance results
@article{RO_2018__52_2_391_0,
author = {Serairi, Mehdi and Haouari, Mohamed},
title = {A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {391--414},
publisher = {EDP-Sciences},
volume = {52},
number = {2},
year = {2018},
doi = {10.1051/ro/2017019},
zbl = {1405.90027},
mrnumber = {3880534},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2017019/}
}
TY - JOUR AU - Serairi, Mehdi AU - Haouari, Mohamed TI - A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2018 SP - 391 EP - 414 VL - 52 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2017019/ DO - 10.1051/ro/2017019 LA - en ID - RO_2018__52_2_391_0 ER -
%0 Journal Article %A Serairi, Mehdi %A Haouari, Mohamed %T A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2018 %P 391-414 %V 52 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2017019/ %R 10.1051/ro/2017019 %G en %F RO_2018__52_2_391_0
Serairi, Mehdi; Haouari, Mohamed. A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 2, pp. 391-414. doi : 10.1051/ro/2017019. http://www.numdam.org/articles/10.1051/ro/2017019/
[1] , , and , Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem. Eur. J. Oper. Res. 233 (2015) 43–63 | DOI | MR | Zbl
[2] and , Two-dimensional finite bin packing algorithms. J. Oper. Res. Soc. 38 (1987) 423–429 | DOI | Zbl
[3] and , A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces. Inter. Trans. Oper. Res. 16 (2009) 685–713 | DOI | Zbl
[4] , New lower bounds for the three-dimensional finite bin packing problem. Discrete Appl. Math. 140 (2004) 241–258 | DOI | MR | Zbl
[5] and , An exact algorithm for the two-dimensional strip-packing problem. Oper. Res. 58 (2010) 1774–1791 | DOI | MR | Zbl
[6] and , The two-dimensional finite bin packing problem, Part I: New lower bounds for the oriented case. 4OR (2003) 27–42 | MR | Zbl
[7] , and , An approximation scheme for the two-stage, two-dimensional knapsack problem. Discrete Optimiz. 7 (2010) 114–124 | DOI | MR | Zbl
[8] and , Bidimensional packing by bilinear programming. Math. Progr. 118 (2009) 75–108 | DOI | MR | Zbl
[9] , and , New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation. Comput. Oper. Res. 34 (2007a) 2223–2250 | DOI | Zbl
[10] and , Computing redundant resources for the resource constrained project scheduling problem. Europ. J. Oper. Res. 176 (2007b) 1452–1463 | DOI | MR | Zbl
[11] , , and , Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. Europ. J. Oper. Res. 191 (2008) 61–85 | DOI | Zbl
[12] , , , A new exact method for the two-dimensional bin-packing problem with fixed orientation. Oper. Res. Lett. 35 (2007a) 357–364 | DOI | MR | Zbl
[13] , and , A new exact method for the two-dimensional orthogonal packing problem. Europ. J. Oper. Res. 183 (2007b) 1196–1211 | DOI | MR | Zbl
[14] , and , A survey of dual-feasible and superadditive functions. Ann. Oper. Res. 179 (2010) 317–342 | DOI | MR | Zbl
[15] , and , Combinatorial Benders’ cuts for the strip packing problem. Oper. Res. 62 (2014) 643–661 | DOI | MR | Zbl
[16] , and , Sequential heuristic for the two-dimensional bin-packing problem. Europ. J. Oper. Res. 240 (2015) 43–53 | DOI | MR | Zbl
[17] and , Optimal scheduling of tasks on identical parallel processors. ORSA J. Comput. 7 (1995) 191–200 | DOI | Zbl
[18] and , Heuristic approaches for the two- and three-dimensional knapsack packing problem. Comput. Oper. Res. 36 (2009) 1026–1049 | DOI | MR | Zbl
[19] and , New classes of fast lower bounds for bin packing problems. Math. Program. 60 (2001) 311–329 | MR
[20] and , A general framework for bounds for higher-dimensional orthogonal packing problems. Math. Methods Oper. Res. 60 (2004) 311–329 | DOI | MR | Zbl
[21] , and , An exact algorithm for higher-dimensional orthogonal packing. Oper. Res. 55 (2007) 569–587 | DOI | MR | Zbl
[22] , , and , Ant colony optimization for the two-dimensional loading vehicle routing problem. Comput. Oper. Res. 36 (2009) 655–673 | DOI | Zbl
[23] , , and , A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51 (2008) 4–18 | DOI | MR | Zbl
[24] and , An exact algorithm for general, orthogonal, two-dimensional knapsack problem. Europ. J. Oper. Res. 83 (1995) 39–56 | DOI | Zbl
[25] , , , and , A hybrid heuristic algorithm for the 2D variable-sized bin packing problem, Europ. J. Operat. Res. 238 (2014) 95–103 | DOI | MR
[26] , , , and , Exact algorithms for the two-dimensional strip packing problem with and without rotations. Europ. J. Oper. Res. 198 (2009) 73–83 | DOI | MR | Zbl
[27] and , Routing problems with loading constraints. TOP 18 (2010) 4–27 | DOI | MR | Zbl
[28] , Near-Optimal Bin Packing Algorithms. Ph.D. thesis, Massachusetts Institute of Technology (1973) | MR
[29] , and , Two-dimensional packing problems: A survey. Europ. J. Oper. Res. 141 (2002a) 241–252 | DOI | MR | Zbl
[30] , and , Recent advances on two-dimensional bin packing problems. Discrete Appl. Math. 123 (2002b) 379–396 | DOI | MR | Zbl
[31] , and , An exact approach to the strip-packing problem. INFORMS J. Comput. 15 (2003) 310–319 | DOI | MR | Zbl
[32] , , Models and algorithms for packing rectangles into the smallest square. Comput. Oper. Res. 63 (2015) 161–171 | DOI | MR | Zbl
[33] and , Knapsack problems: Algorithms and computer implementations. John Wiley and Sons, Chichester (1990) | MR | Zbl
[34] and , Exact solution of the two-dimensional finite bin packing problem. Manag. Sci. 44 (1998) 388–399 | DOI | Zbl
[35] and , Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS J. Comput. 19 (2007) 36–51 | DOI | MR | Zbl
[36] , , and , A block-based layer building approach for the 2D guillotine strip packing problem. Europ. J. Operat. Res. 239 (2014) 58–69 | DOI | Zbl
[37] , , and , A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints. Eur. J. Oper. Res. 243 (2015) 798–814 | DOI | Zbl
[38] , and , A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. Europ. J. Oper. Res. 195 (2009) 729–743 | DOI | Zbl
Cité par Sources :
