A note on a two dimensional knapsack problem with unloading constraints

Jefferson Luiz Moisés da Silveira; Eduardo Candido Xavier; Flávio Keidi Miyazawa

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2013)

  • Volume: 47, Issue: 4, page 315-324
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Moisés da Silveira, Jefferson Luiz, Xavier, Eduardo Candido, and 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 47.4 (2013): 315-324. <http://eudml.org/doc/273036>.

@article{MoisésdaSilveira2013,
abstract = {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.},
author = {Moisés da Silveira, Jefferson Luiz, Xavier, Eduardo Candido, Miyazawa, Flávio Keidi},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {knapsack problem; approximation algorithms; unloading/loading constraints},
language = {eng},
number = {4},
pages = {315-324},
publisher = {EDP-Sciences},
title = {A note on a two dimensional knapsack problem with unloading constraints},
url = {http://eudml.org/doc/273036},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Moisés da Silveira, Jefferson Luiz
AU - Xavier, Eduardo Candido
AU - Miyazawa, Flávio Keidi
TI - A note on a two dimensional knapsack problem with unloading constraints
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 4
SP - 315
EP - 324
AB - 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.
LA - eng
KW - knapsack problem; approximation algorithms; unloading/loading constraints
UR - http://eudml.org/doc/273036
ER -

References

top
  1. [1] A. Caprara and M. Monaci, On the two-dimensional knapsack problem. Oper. Res. Lett.32 (2004) 5–14. Zbl1056.90115
  2. [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. Zbl0447.68079MR592769
  3. [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. Zbl1268.90074
  4. [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. MR3017799
  5. [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. [6] M. Gendreau, M. Iori, G. Laporte and S. Martello, A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks51 (2007) 4–18. Zbl1146.90012MR2375146
  7. [7] R. Harren, Approximating the orthogonal knapsack problem for hypercubesi in ICALP (1), vol. 4051 of Lect. Notes Comput. Sci. (2006) 238–249. Zbl1223.90052MR2305530
  8. [8] R. Harren and R. van Stee, Absolute approximation ratios for packing rectangles into bins. J. Sched. (2010). Zbl1280.68295MR2896971
  9. [9] O.H. Ibarra and C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM22 (1975) 463–468. Zbl0345.90049MR378463
  10. [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. [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. [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. Zbl1143.90399MR2481714
  13. [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. Zbl1317.68280MR2291055
  14. [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. [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. Zbl1251.90324MR2971805
  16. [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. Zbl1155.90331

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.