Algorithms for Packing Problems
Abstract
We study several packing problems that are NP-hard. We assume the hypothesis that P ≠ NP and in this case there are no efficient (polynomial time complexity) exact algorithms to solve these problems. Given that, we present several approximation algorithms (efficient algorithms that produces solutions with quality guarantee) for some packing problems that have practical applications. These algorithms are the best known for the corresponding problems. We also present linear programming based heuristics using a column generation technique for some two dimensional packing problems. The computational experiments indicate that these algorithms obtain very good solutions and are suitable for solving real-world instances.
References
Cintra, G. F. (2004). Algoritmos para problemas de corte de guilhotina bidimensional. PhD thesis, Instituto de Matemática e Estatística, São Paulo.
Cintra, G. F., Miyazawa, F. K., Wakabayashi, Y., and Xavier, E. C. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, accepted.
Cintra, G. F., Miyazawa, F. K., Wakabayashi, Y., and Xavier, E. C. A note on the approximability of cutting stock problems. European Journal of Operational Research, to appear, DOI: 10.1016/j.ejor.2005.09.053.
Cintra, G. F. and Wakabayashi, Y. (2004). Dynamic programming and column generation based approaches for two-dimensional guillotine cutting problems. In Proceedings of WEA 2004: Workshop on Efficient and Experimental Algorithms, volume 3059 of Lecture Notes in Computer Science, pages 175–190.
Dawande, M., Kalagnanam, J., and Sethuranam, J. (1998). Variable sized bin packing with color constraints. Technical report, IBM, T.J. Watson Research Center, NY.
Dawande, M., Kalagnanam, J., and Sethuranam, J. (2001). Variable sized bin packing with color constraints. In Proceedings of the 1th Brazilian Symposium on Graph Algorithms and Combinatorics, volume 7 of Electronic Notes in Discrete Mathematics.
Ferreira, J. S., Neves, M. A., and Fonseca e Castro, P. (1990). A two-phase roll cutting problem. European J. Operational Research, 44:185–196.
Golubchik, L., Khanna, S., Khuller, S., Thurimella, R., and Zhu, A. (2000). Approximation algorithms for data placement on parallel disks. In Proceedings of SODA, pages 223–232.
Hochbaum, D. S. and Shmoys, D. B. (1987). Using dual approximation algorithms for schedulling problems: practical and theoretical results. Journal of the ACM, 34(1):144–162.
Hoto, R., Arenales, M., and Maculan, N. The one dimensional compartmentalized cutting stock problem: a case study. To appear in European Journal of Operational Research.
Kashyap, S. R. and Khuller, S. (2003). Algorithms for non-uniform size data placement on parallel disks. In Proceedings of FSTTCS, volume 2914 of Lecture Notes in Computer Science, pages 265–276.
Marques, F. P. and Arenales, M. The constrained compartmentalized knapsack problem. To appear in Computer & Operations Research.
Shachnai, H. and Tamir, T. (2001a). On two class-constrained versions of the multiple knapsack problem. Algorithmica, 29:442–467.
Shachnai, H. and Tamir, T. (2001b). Polynomial time approximation schemes for class-constrained packing problems. Journal of Scheduling, 4(6):313–338.
Shachnai, H. and Tamir, T. (2004). Tight bounds for online class-constrained packing. Theoretical Computer Science, 321(1):103–123.
Xavier, E. C. (2006). Algoritmos para Problemas de Empacotamento. PhD thesis, Universidade Estadual de Campinas. [link].
Xavier, E. C. and Miyazawa, F. K. A one-dimensional bin packing problem with shelf divisions. To appear in Discrete Applied Mathematics (Elsevier).
Xavier, E. C. and Miyazawa, F. K. (2005). A one-dimensional bin packing problem with shelf divisions. In 2nd Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2005), volume 19 of Electronic Notes in Discrete Mathematics.
Xavier, E. C. and Miyazawa, F. K. (2006a). Approximation schemes for knapsack problems with shelf divisions. Theoretical Computer Sciense, 352(1-3):71–84.
Xavier, E. C. and Miyazawa, F. K. (2006b). The class constrained bin packing problem with applications to video-on-demand. In Proceedings of the 12th Annual International Computing and Combinatorics Conference (COCOON’06), volume 4112 of Lecture Notes in Computer Science, pages 439–448.
Cintra, G. F., Miyazawa, F. K., Wakabayashi, Y., and Xavier, E. C. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, accepted.
Cintra, G. F., Miyazawa, F. K., Wakabayashi, Y., and Xavier, E. C. A note on the approximability of cutting stock problems. European Journal of Operational Research, to appear, DOI: 10.1016/j.ejor.2005.09.053.
Cintra, G. F. and Wakabayashi, Y. (2004). Dynamic programming and column generation based approaches for two-dimensional guillotine cutting problems. In Proceedings of WEA 2004: Workshop on Efficient and Experimental Algorithms, volume 3059 of Lecture Notes in Computer Science, pages 175–190.
Dawande, M., Kalagnanam, J., and Sethuranam, J. (1998). Variable sized bin packing with color constraints. Technical report, IBM, T.J. Watson Research Center, NY.
Dawande, M., Kalagnanam, J., and Sethuranam, J. (2001). Variable sized bin packing with color constraints. In Proceedings of the 1th Brazilian Symposium on Graph Algorithms and Combinatorics, volume 7 of Electronic Notes in Discrete Mathematics.
Ferreira, J. S., Neves, M. A., and Fonseca e Castro, P. (1990). A two-phase roll cutting problem. European J. Operational Research, 44:185–196.
Golubchik, L., Khanna, S., Khuller, S., Thurimella, R., and Zhu, A. (2000). Approximation algorithms for data placement on parallel disks. In Proceedings of SODA, pages 223–232.
Hochbaum, D. S. and Shmoys, D. B. (1987). Using dual approximation algorithms for schedulling problems: practical and theoretical results. Journal of the ACM, 34(1):144–162.
Hoto, R., Arenales, M., and Maculan, N. The one dimensional compartmentalized cutting stock problem: a case study. To appear in European Journal of Operational Research.
Kashyap, S. R. and Khuller, S. (2003). Algorithms for non-uniform size data placement on parallel disks. In Proceedings of FSTTCS, volume 2914 of Lecture Notes in Computer Science, pages 265–276.
Marques, F. P. and Arenales, M. The constrained compartmentalized knapsack problem. To appear in Computer & Operations Research.
Shachnai, H. and Tamir, T. (2001a). On two class-constrained versions of the multiple knapsack problem. Algorithmica, 29:442–467.
Shachnai, H. and Tamir, T. (2001b). Polynomial time approximation schemes for class-constrained packing problems. Journal of Scheduling, 4(6):313–338.
Shachnai, H. and Tamir, T. (2004). Tight bounds for online class-constrained packing. Theoretical Computer Science, 321(1):103–123.
Xavier, E. C. (2006). Algoritmos para Problemas de Empacotamento. PhD thesis, Universidade Estadual de Campinas. [link].
Xavier, E. C. and Miyazawa, F. K. A one-dimensional bin packing problem with shelf divisions. To appear in Discrete Applied Mathematics (Elsevier).
Xavier, E. C. and Miyazawa, F. K. (2005). A one-dimensional bin packing problem with shelf divisions. In 2nd Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2005), volume 19 of Electronic Notes in Discrete Mathematics.
Xavier, E. C. and Miyazawa, F. K. (2006a). Approximation schemes for knapsack problems with shelf divisions. Theoretical Computer Sciense, 352(1-3):71–84.
Xavier, E. C. and Miyazawa, F. K. (2006b). The class constrained bin packing problem with applications to video-on-demand. In Proceedings of the 12th Annual International Computing and Combinatorics Conference (COCOON’06), volume 4112 of Lecture Notes in Computer Science, pages 439–448.
Published
2007-06-30
How to Cite
XAVIER, E. C.; MIYAZAWA, F. K..
Algorithms for Packing Problems. In: THESIS AND DISSERTATION CONTEST (CTD), 20. , 2007, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 1966-1973.
ISSN 2763-8820.
