Solving the two-dimensional packing problem with m-M calculus
DOI:
https://doi.org/10.2298/YJOR1101093SKeywords:
Non-linear optimization, m-M calculus, two dimensional packingAbstract
This paper considers the two dimensional rectangular packing problem. The mathematical formulation is based on the optimization of a non-linear function with piecewise linear constraints with a small number of real variables. The presented method of m-M calculus finds all optimal solutions on small instances. Computational performance is good on smaller instances.References
Baldacci, R., and Boschetti, M.A., “A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem,” European Journal of Operational Research, 183 (3) (2007) 1230-1248.
Beasley, J.E., “An exact two-dimensional non-guillotine cutting tree search procedure,” Operations Research, 33 (1985) 49–64.
Binkley, K.J., and Hagiwara, M., “Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners' heuristic,” European Journal of Operational Research, 183 (3) (2007) 1230-1248.
Christofides, N., and Hadjiconstantinou, E., “An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts,” European Journal of Operational Research, 83 (1995) 21–38.
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, 191 (1) (2008) 59-83.
Coffman, E.G., Jr., and Lueker, G.S., Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, Chichester, 1992.
Coffman, E.G., Jr., and Shor, P.W., “Average-case analysis of cutting and packing in two dimensions,” European Journal of Operational Research, 44 (1990) 134–144.
Correa, J.R., “Near-optimal solutions to two-dimensional bin packing with 90 degree rotations,” Electronic Notes in Discrete Mathematics, 18 (2004) 89-95.
Diegert, C., “Practical automatic placement for standard-cell integrated circuit,” American Journal of Mathematical and Management Sciences, 8 (34) (1988) 309–328.
Dowsland, K.A., and Dowsland, W.B., “Packing problems,” European Journal of Operational Research, 56 (1992) 2–14.
Dyckhoff, H., Finke, U., Cutting and Packing in Production and Distribution, Physica Verlag, Heidelberg, 1992.
Dyckhoff, H., Scheithauer, G., and Terno J., “Cutting and packing (C&P),” in: M., Dell’Amico, F., Maffioli, S., Martello, (eds.), Annotated Bibliographies in Combinatorial Optimization, Wiley, Chichester, 1997, 393–413.
Epstein, L., Levin, A., and Van Stee, R., “Two-dimensional packing with conflicts,” Acta Informatica, 45 (3) (2008) 155-175.
Gonzalves, J.F., and Resende, M.G.C., “A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem,” Journal of Combinatorial Optimization, (2010) 1-22 Article in Press.
Hadjiconstantinou, E., and Christofides N., “An optimal algorithm for general orthogonal 2-D cutting problems,” Technical report MS-91/2, Imperial College, London, UK.
Harwig, J.M., Barnes, J.W., and Moore, J.T., “An adaptive tabu search approach for 2-dimensional orthogonal packing problems,” Military Operations Research, 11 (2) (2006) 5-26.
Hochbaum, D.S., and Maass, W., “Approximation schemes for covering and packing problems in image processing and VLSI,” Journal of the Association for Computing Machinery, 32 (1) (1985) 130–136.
Kim, J., Moon, B.-R., “A hybrid genetic algorithm for a variant of two-dimensional packing problem,” Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009, 287-292.
Leung J., Tam, T., Wong, C.S., Young, G., and Chin, F., “Packing squares into square,” Journal of Parallel and Distributed Computing, 10 (1990) 271–275.
Lodi, A., Martello, S., and Monaci, M., “Two-dimensional packing problems: A survey,” European Journal of Operational Research, 141 (2002) 241–252.
Lu, S., Lu, Y., Zha, J., and Lu, S., “Cross-entropy method for two-dimensional packing problem with rectangle pieces,” Beijing Jiaotong Daxue Xuebao/Journal of Beijing Jiaotong University, 33 (2) (2009) 39-43.
Ortmann, F.G., Ntene, N., van and Vuuren, J.H., “New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems,” European Journal of Operational Research, 203 (2) (2010) 306-315.
Prešić, S.B., “A survey of the m-M calculus,” Yugoslav Journal of Operations Research, 8 (1) (1998) 137-168.
Savić, A., “Packing and cutting problems,” Master thesis, Faculty of Mathematics, University of Belgrade, 2000.
Toro, E.M., Garcs, A., and Ruiz, H., “Two dimensional packing problem using a hybrid constructive algorithm of variable neighborhood search and simulated annealing,” Revista Facultad de Ingenieria, 46 (2008) 119-131.
Wu, Y.L., Huang, W., Lau, S., Wong, C.K., and Young, G.H., “An effective quasi-human based heuristic for solving the rectangle packing problem,” European Journal of Operational Research, 141 (2002) 341–358.
Downloads
Published
Issue
Section
License
Copyright (c) 2011 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
