Unconstrained two-dimensional knapsack problem
##plugins.themes.bootstrap3.article.details##
Cutting and packing problems are common in operations research, due to their big spectrum of application in the industry and its highly mathematical and computational complexity for the academy. In this study we present the unconstrained twodimensional cutting stock problem of rectangular items, with and without weights associated to the items, bearing in mind the possibility to rotate items at 90°, and with guillotine cuts (also known as unconstrained two-dimensional guillotineable single knapsack problem). For this problem, we describe the mathematical model recognized by the academic community. We develop an appropriate encoding of the problem so it is possible to work on it using metaheuristic hybrid algorithm particle swarm optimization and simulated annealing. To check the efficiency of this methodology, case studies were taken from specialized literature, where the presented solution method could be analyzed and compared with current problems. The results obtained had an excellent quality and had never been reported.
Unconstrained two-dimensional knapsack problema, particle swarm optimization, simulated annealingMochila bidimensional irrestricta, cúmulo de partículas, recocido simulado
BEN, S.; CHU, C. y ESPINOUSE, M. L. Characterization and modelling of guillotine constraints. European Journal of Operational Research, 2008, vol. 191, pp. 112-126.
CHRISTOFIDES, N. y WHITLOCK, C. An algorithm for two-dimensional cutting problems. Operations Research, 1977, vol. 25, pp. 30-44.
CUI, Y. An exact algorithm for generating homogenous T-shape cutting patterns. Computers & Operations Research, 2007, vol. 34, pp. 1107-1120.
GALLEGO, R.; ESCOBAR, A. H. y ROMERO, R. A. Programación lineal entera. Pereira: Universidad Tecnológica de Pereira, 2007.
GALLEGO, R.; ESCOBAR, A. H. y TORO, E. M. Técnicas metaheurísticas de optimización. Pereira: Universidad Tecnológica de Pereira, 2008.
G, Y.-G. y KANG, M.-K. A new upper bound for unconstrained two-dimensional cutting and packing. Journal of the Operational Research Society, 2002, vol. 53, pp. 587-591.
G, Y.-G.; KANG, M.-K. y SEONG, J. A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems. Operations Research Letters, 2003, vol. 31, pp. 301-307.
GILMORE, P. C. y GOMORY, R. E. Multistage cutting problems of two and more dimensions. Operations Research, 1965, vol. 13, pp. 94-120.
GILMORE, P. C. y GOMORY, R. E. The theory and computation of knapsack functions. Operational Research, 1966, vol. 14, pp. 1045-1074.
HERZ, J. C. A recursive computing procedure for two-dimensional stock cutting. IBM Journal of Research and Development, 1972, vol. 16, pp. 462-469.
HIFI, M. Exact algorithms for the guillotine strip cutting/packing problem. Computers & Operations Research, 1998, vol. 25, pp. 925-940.
HIFI, M. Exact algorithms for large-scale unconstrained two and three staged cutting problems. Computational Optimization and Applications, 2001, vol. 18, pp. 63-88.
HIFI, M. Problem instances for the 2D Cutting/Packing Problems [web en línea], 1997.
HIFI, M y ZISSIMOPOULOS, V. A recursive exact algorithm for weighted two-dimensional cutting. European Journal of Operational Research, 1996, vol. 91, pp. 553-564.
TORO, E.; GARCÉS, A. y RUIZ, H. Solución al problema de empaquetamiento bidimensional usando un algoritmo híbrido constructivo de búsqueda en vecindad variable y recocido simulado. Revista Facultad de Ingeniería de la Universidad de Antioquia, 2008, vol. 46, pp. 119-131.
WONG, D. F.; LEONG, H. W. y LIU, C. L. Simulated annealing for VLSI design. New York: Kluwer Academic Publishers, 1988.
ZHI-HUI, Z.; JUN, Z.; YUN, L. y HENRY, S. Adaptive Particle swarm optimization. IEEE Transactions on Systems, Man and Cybernetics, 2009, vol. 39, pp. 1362-1381.