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.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017019
Classification : 90-08
Mots-clés : Two-dimensional bin packing, lower bounds, dual feasible functions, dominance results
Serairi, Mehdi 1 ; Haouari, Mohamed 1

1 
@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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ro/2017019/

[1] C. Alves, J. Valério De Carvalho, F. Clautiaux and J. Rietz, 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] J.O. Berkey and P.Y. Wang, Two-dimensional finite bin packing algorithms. J. Oper. Res. Soc. 38 (1987) 423–429 | DOI | Zbl

[3] A. Bortfeldt and T. Winter, A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces. Inter. Trans. Oper. Res. 16 (2009) 685–713 | DOI | Zbl

[4] M.A. Boschetti, New lower bounds for the three-dimensional finite bin packing problem. Discrete Appl. Math. 140 (2004) 241–258 | DOI | MR | Zbl

[5] M.A. Boschetti and L. Montaletti, An exact algorithm for the two-dimensional strip-packing problem. Oper. Res. 58 (2010) 1774–1791 | DOI | MR | Zbl

[6] M.A. Boschetti and A. Mingozzi, The two-dimensional finite bin packing problem, Part I: New lower bounds for the oriented case. 4OR (2003) 27–42 | MR | Zbl

[7] A. Caprara, A. Lodi and M. Monaci, An approximation scheme for the two-stage, two-dimensional knapsack problem. Discrete Optimiz. 7 (2010) 114–124 | DOI | MR | Zbl

[8] A. Caprara and M. Monaci, Bidimensional packing by bilinear programming. Math. Progr. 118 (2009) 75–108 | DOI | MR | Zbl

[9] J. Carlier, F. Clautiaux and A. Moukrim, 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] J. Carlier and E. Néron, Computing redundant resources for the resource constrained project scheduling problem. Europ. J. Oper. Res. 176 (2007b) 1452–1463 | DOI | MR | Zbl

[11] G.F. Cintra, F.K. Miyazawa, Y. Wakabayashi and E.C. Xavier, 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] F. Clautiaux, J. Carlier, A. Moukrim, 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] F. Clautiaux, J. Carlier and A. Moukrim, A new exact method for the two-dimensional orthogonal packing problem. Europ. J. Oper. Res. 183 (2007b) 1196–1211 | DOI | MR | Zbl

[14] F. Clautiaux, C. Alves and J. Valerio De Carvalho, A survey of dual-feasible and superadditive functions. Ann. Oper. Res. 179 (2010) 317–342 | DOI | MR | Zbl

[15] J.F. Côté, M. Dell’Amico and M. Iori, Combinatorial Benders’ cuts for the strip packing problem. Oper. Res. 62 (2014) 643–661 | DOI | MR | Zbl

[16] Y.P. Cui,Y. Cui and T. Tang, Sequential heuristic for the two-dimensional bin-packing problem. Europ. J. Oper. Res. 240 (2015) 43–53 | DOI | MR | Zbl

[17] M. Dell’Amico and S. Martello, Optimal scheduling of tasks on identical parallel processors. ORSA J. Comput. 7 (1995) 191–200 | DOI | Zbl

[18] J. Egeblad and D. Pisinger, Heuristic approaches for the two- and three-dimensional knapsack packing problem. Comput. Oper. Res. 36 (2009) 1026–1049 | DOI | MR | Zbl

[19] S. Fekete and J. Schepers, New classes of fast lower bounds for bin packing problems. Math. Program. 60 (2001) 311–329 | MR

[20] S. Fekete and J. Schepers, A general framework for bounds for higher-dimensional orthogonal packing problems. Math. Methods Oper. Res. 60 (2004) 311–329 | DOI | MR | Zbl

[21] S. Fekete, J. Schepers and J.C. Van Der Veen, An exact algorithm for higher-dimensional orthogonal packing. Oper. Res. 55 (2007) 569–587 | DOI | MR | Zbl

[22] G. Fuellerer, K.F. Doerner, R.F. Hartl and M. Iori, Ant colony optimization for the two-dimensional loading vehicle routing problem. Comput. Oper. Res. 36 (2009) 655–673 | DOI | Zbl

[23] M. Gendreau, M. Iori, G. Laporte and S. Martello, A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51 (2008) 4–18 | DOI | MR | Zbl

[24] E. Hadjiconstantinou and N. Christofides, An exact algorithm for general, orthogonal, two-dimensional knapsack problem. Europ. J. Oper. Res. 83 (1995) 39–56 | DOI | Zbl

[25] S. Hong, D. Zhang, H.C. Lau, X. Zeng and Y. Sic, A hybrid heuristic algorithm for the 2D variable-sized bin packing problem, Europ. J. Operat. Res. 238 (2014) 95–103 | DOI | MR

[26] M. Kenmochi, T. Imamichi, K. Nonobe, M. Yagiura and H. Nagamochi, 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] M. Iori and S. Martello, Routing problems with loading constraints. TOP 18 (2010) 4–27 | DOI | MR | Zbl

[28] D.S. Johnson, Near-Optimal Bin Packing Algorithms. Ph.D. thesis, Massachusetts Institute of Technology (1973) | MR

[29] A. Lodi, S. Martello and M. Monaci, Two-dimensional packing problems: A survey. Europ. J. Oper. Res. 141 (2002a) 241–252 | DOI | MR | Zbl

[30] A. Lodi, S. Martello and D. Vigo, Recent advances on two-dimensional bin packing problems. Discrete Appl. Math. 123 (2002b) 379–396 | DOI | MR | Zbl

[31] S. Martello, M. Monaci and D. Vigo, An exact approach to the strip-packing problem. INFORMS J. Comput. 15 (2003) 310–319 | DOI | MR | Zbl

[32] S. Martello, M. Monaci, Models and algorithms for packing rectangles into the smallest square. Comput. Oper. Res. 63 (2015) 161–171 | DOI | MR | Zbl

[33] S. Martello and P. Toth, Knapsack problems: Algorithms and computer implementations. John Wiley and Sons, Chichester (1990) | MR | Zbl

[34] S. Martello and D. Vigo, Exact solution of the two-dimensional finite bin packing problem. Manag. Sci. 44 (1998) 388–399 | DOI | Zbl

[35] D. Pisinger and M.M. Sigurd, 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] L. Wei, T. Tian, W. Zhu and A. Lim, A block-based layer building approach for the 2D guillotine strip packing problem. Europ. J. Operat. Res. 239 (2014) 58–69 | DOI | Zbl

[37] L. Wei, Z. Zhang, D. Zhang and A. Lim, 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] E.E. Zachariadis, C.D. Tarantilis and C.T. Kiranoudis, 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 :