A note on a two dimensional knapsack problem with unloading constraints
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 47 (2013) no. 4, p. 315-324

In this paper we address the two-dimensional knapsack problem with unloading constraints: we have a bin B, and a list L of n rectangular items, each item with a class value in {1,...,C}. The problem is to pack a subset of L into B, maximizing the total profit of packed items, where the packing must satisfy the unloading constraint: while removing one item a, items with higher class values can not block a. We present a (4 + ϵ)-approximation algorithm when the bin is a square. We also present (3 + ϵ)-approximation algorithms for two special cases of this problem.

DOI : https://doi.org/10.1051/ita/2013037
Classification:  68W25,  05B40,  90C27
Keywords: knapsack problem, approximation algorithms, unloading/loading constraints
@article{ITA_2013__47_4_315_0,
     author = {Mois\'es da Silveira, Jefferson Luiz and Xavier, Eduardo Candido and Miyazawa, Fl\'avio Keidi},
     title = {A note on a two dimensional knapsack problem with unloading constraints},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     publisher = {EDP-Sciences},
     volume = {47},
     number = {4},
     year = {2013},
     pages = {315-324},
     doi = {10.1051/ita/2013037},
     mrnumber = {3132294},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2013__47_4_315_0}
}
Moisés da Silveira, Jefferson Luiz; Xavier, Eduardo Candido; Miyazawa, Flávio Keidi. A note on a two dimensional knapsack problem with unloading constraints. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 47 (2013) no. 4, pp. 315-324. doi : 10.1051/ita/2013037. http://www.numdam.org/item/ITA_2013__47_4_315_0/

[1] A. Caprara and M. Monaci, On the two-dimensional knapsack problem. Oper. Res. Lett. 32 (2004) 5-14. | Zbl 1056.90115

[2] E.G. Coffman Jr., M.R. Garey, D.S. Johnson and R.E. Tarjan, Performance bounds for level-oriented two dimensional packing algorithms. SIAM J. Comput. 9 (1980) 808-826. | MR 592769 | Zbl 0447.68079

[3] J.L.S. Da Silveira, E.C. Xavier and F.K. Miyazawa, Two dimensional knapsack with unloading constraints, in VI Latin American Algorithms, Graphs and Optimization Symposium (LAGOS 2011), Electronic Notes in Discrete Math. (2011) 1-4. | Zbl 1268.90074

[4] J.L.M. Da Silveira, F.K. Miyazawa and E.C. Xavier, Heuristics for the strip packing problem with unloading constraints. Comput. Oper. Res. 40 (2013) 991-1003. | MR 3017799

[5] B.L.P. De Azevedo, P.H. Hokama, F.K. Miyazawa and E.C. Xavier, A branch-and-cut approach for the vehicle routing problem with two-dimensional loading constraints, in Simpósio Brasileiro de Pesquisa Operacional - SBPO, Porto Seguro, Brazil (2009).

[6] 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 (2007) 4-18. | MR 2375146 | Zbl 1146.90012

[7] R. Harren, Approximating the orthogonal knapsack problem for hypercubesi in ICALP (1), vol. 4051 of Lect. Notes Comput. Sci. (2006) 238-249. | MR 2305530 | Zbl 1223.90052

[8] R. Harren and R. Van Stee, Absolute approximation ratios for packing rectangles into bins. J. Sched. (2010). | MR 2896971 | Zbl 1280.68295

[9] O.H. Ibarra and C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22 (1975) 463-468. | MR 378463 | Zbl 0345.90049

[10] M. Iori, J-J. S-González and D. Vigo, An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transport. Sci. 41 (2007) 253-264.

[11] K. Jansen and L. Prädel, How to maximize the total area of rectangles packed into a rectangle. Technical Report 0908. Christian-Albrechts-Universität zu kiel, Italy (2009).

[12] K. Jansen and R. Solis-Oba, A polynomial time approximation scheme for the square packing problem, in Proc. of the Integer Programming and Combinatorial Optimization, vol. 5035, in Lect. Note Comput. Sci. Springer Berlin, Heidelberg (2008) 184-198. | MR 2481714 | Zbl 1143.90399

[13] K. Jansen and G. Zhang, On rectangle packing: maximizing benefits, in Proc. of the 15th ACM-SIAM Symposium on Discrete Algorithms. Society for Industial and Applied Mathematics, Philadephia, PA, USA (2004) 204-213. | MR 2291055

[14] L. Junqueira, R. Morabito and D. Yamashita, Abordagens para problemas de carregamento de contêiners com considerações de múltiplos destinos. Gestão & Produção. 18 (2011).

[15] L. Junqueira, R. Morabito and D.S. Yamashita, Mip-based approaches for the container loading problem with multi-drop constraints. Ann. Oper. Res. 199 (2012) 51-75. | MR 2971805 | Zbl 1251.90324

[16] E.E. Zachariadis, C.T. Kiranoudis and C.D. Tarantilis, A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. Eur. J. Oper. Res. 195 (2009) 729-743. | Zbl 1155.90331