×

A clique covering MIP model for the irregular strip packing problem. (English) Zbl 1391.90391

Summary: The irregular strip packing problem consists in the cutting of a set of two-dimensional pieces from an object of fixed width using the minimum possible length. Despite its economic importance for many industries, few exact studies have addressed this problem. Recently, a mixed integer programming model in which pieces are placed on a grid has been proposed. Although the model has proved the optimality for some large instances, it has a large number of non-overlap constraints, which grows quickly according to the discretization resolution and number of distinct pieces. This paper proposes a clique covering model to reduce the number of constraints and improve the linear relaxation. The model has outperformed the previous model in most evaluated instances and obtained an optimal solution for instances with up to 25 pieces (22 distinct pieces) subject to grid discretization.

MSC:

90B80 Discrete location and assignment
90C27 Combinatorial optimization
05C85 Graph algorithms (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
90C11 Mixed integer programming

Software:

TOPOS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fowler, R. J.; Paterson, M. S.; Tanimoto, S. L., Optimal packing and covering in the plane are NP-complete, Inf Process Lett, 12, 3, 133-137, (1981) · Zbl 0469.68053
[2] Nielsen, B. K.; Odgaard, A., Fast neighborhood search for the nesting problem, Sci Report, (2003), University of Copenhagen
[3] Bennell, J. A.; Oliveira, J. F., The geometry of nesting problems: a tutorial, Eur J Oper Res, 184, 2, 397-415, (2008) · Zbl 1136.90030
[4] Wäscher, G.; Haußner, H.; Schumann, H., An improved typology of cutting and packing problems, Eur J Oper Res, 183, 3, 1109-1130, (2007) · Zbl 1278.90347
[5] Dowsland, K. A.; Dowsland, W. B., Solution approaches to irregular nesting problems, Eur J Oper Res, 84, 3, 506-521, (1995) · Zbl 0918.90116
[6] Bennell, J. A.; Oliveira, J. F., A tutorial in irregular shape packing problems, J Oper Res Soc, 60, S1, S93-S105, (2009) · Zbl 1168.90300
[7] Oliveira, J. F.; Gomes, A. M.; Ferreira, J. S., Topos - a new constructive algorithm for nesting problems, OR-Spektrum, 22, 2, 263-284, (2000) · Zbl 0970.90123
[8] Dowsland, K. A.; Vaid, S.; Dowsland, W. B., An algorithm for polygon placement using a bottom-left strategy, Eur J Oper Res, 141, 2, 371-381, (2002) · Zbl 1081.90609
[9] Burke, E.; Hellier, R.; Kendall, G.; Whitwell, G., A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem, Oper Res, 54, 3, 587-601, (2006) · Zbl 1167.90623
[10] Burke, E. K.; Hellier, R. S.R.; Kendall, G.; Whitwell, G., Irregular packing using the line and arc no-fit polygon, Oper Res, 58, 4-part-1, 948-970, (2010) · Zbl 1228.90092
[11] Bennell, J. A.; Dowsland, K. A., Hybridising tabu search with optimisation techniques for irregular stock cutting, Manage Sci, 47, 8, 1160-1172, (2001)
[12] Gomes, A. M.; Oliveira, J. F., Solving irregular strip packing problems by hybridising simulated annealing and linear programming, Eur J Oper Res, 171, 3, 811-829, (2006) · Zbl 1116.90088
[13] Egeblad, J.; Nielsen, B. K.; Odgaard, A., Fast neighborhood search for two- and three-dimensional nesting problems, Eur J Oper Res, 183, 3, 1249-1266, (2007) · Zbl 1135.90386
[14] Umetani, S.; Yagiura, M.; Imahori, S.; Imamichi, T.; Nonobe, K.; Ibaraki, T., Solving the irregular strip packing problem via guided local search for overlap minimization, Int Trans Oper Res, 16, 6, 661-683, (2009) · Zbl 1179.90293
[15] Imamichi, T.; Yagiura, M.; Nagamochi, H., An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem, Discrete Optim, 6, 4, 345-361, (2009) · Zbl 1179.90285
[16] Bennell, J. A.; Song, X., A beam search implementation for the irregular shape packing problem, J Heuristics, 16, 2, 167-188, (2010) · Zbl 1190.90154
[17] Leung, S. C.; Lin, Y.; Zhang, D., Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem, Comput Oper Res, 39, 3, 678-686, (2012) · Zbl 1251.90244
[18] Sato, A. K.; Martins, T. C.; Tsuzuki, M. S.G., An algorithm for the strip packing problem using collision free region and exact Fitting placement, Comput Aided Des, 44, 8, 766-777, (2012)
[19] Elkeran, A., A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering, Eur J Oper Res, 231, 3, 757-769, (2013) · Zbl 1317.90163
[20] Pinheiro, P. R.; Amaro Júnior, B.; Saraiva, R. D., A random-key genetic algorithm for solving the nesting problem, Int J Comput Integr Manuf, 29, 11, 1159-1165, (2016)
[21] Ribeiro, C.; Carravilla, M. A.; Oliveira, J. F., Applying constraint logic programming to the resolution of nesting problems, Pesquisa Operacional, 19, 2, 239-247, (1999)
[22] Carravilla, M. A.; Ribeiro, C.; Oliveira, J. F., Solving nesting problems with non-convex polygons by constraint logic programming, Int Trans Oper Res, 10, 6, 651-663, (2003) · Zbl 1094.68533
[23] Fischetti, M.; Luzzi, I., Mixed-integer programming models for nesting problems, J Heuristics, 15, 3, 201-226, (2009) · Zbl 1172.90495
[24] Daniels, K.; Li, Z.; Milenkovic, V. J., Multiple containment methods, Tech. Rep, (1994), Center for Research in Computing Technology, Harvard University
[25] Li, Z., Compaction algorithms for non-convex polygons and their applications. Ph.D. thesis, (1994), Harvard University, Cambridge, MA
[26] Álvarez-Valdés, R.; Martínez, A.; Tamarit, J., A branch and bound algorithm for cutting and packing irregularly shaped pieces, Int J Prod Econ, 145, 2, 463-477, (2013)
[27] Toledo, F. M.; Carravilla, M. A.; Ribeiro, C.; Oliveira, J. F.; Gomes, A. M., The dotted-board model: a new MIP model for nesting irregular shapes, Int J Prod Econ, 145, 2, 478-487, (2013)
[28] Orlin, J., Contentment in graph theory: covering graphs with cliques, Indagationes Mathematicae (Proc), 80, 5, 406-424, (1977) · Zbl 0374.05041
[29] Kou, L. T.; Stockmeyer, L. J.; Wong, C. K., Covering edges by cliques with regard to keyword conflicts and intersection graphs, Commun ACM, 21, 2, 135-139, (1978) · Zbl 0367.68035
[30] Erdős, P.; Goodman, A. W.; Pósa, L., The representation of a graph by set intersections, Can J Math, 18, 106-112, (1966) · Zbl 0137.43202
[31] Pullman, N. J., Clique coverings of graphs - a survey, (Casse, L. R.A., Combinatorial Mathematics X, Lecture Notes in Mathematics, 1036, (1983), Springer Berlin Heidelberg Berlin), 72-85
[32] Monson, S. D.; Pullman, N. J.; Rees, R., A survey of clique and biclique coverings and factorizations of (0, 1)-matrices, Bull ICA, 14, 17-86, (1995) · Zbl 0832.05088
[33] Roberts, F. S., Applications of edge coverings by cliques, Discrete Appl Math, 10, 1, 93-109, (1985) · Zbl 0558.05046
[34] Rodrigues M.O., Fast constructive and improvement heuristics for edge clique covering. (working paper) 2016;.
[35] Karp, R., Reducibility among combinatorial problems, (Miller, R.; Thatcher, J.; Bohlinger, J., Complexity of Computer Computations, (1972), Springer US New York), 85-103
[36] Pardalos, P. M.; Mavridou, T.; Xue, J., The graph coloring problem: a bibliographic survey, (Du, D.-Z.; Pardalos, P., Handbook of Combinatorial Optimization, 2, (1998), Kluwer Academic Publishers Boston), 331-395 · Zbl 0944.05050
[37] Malaguti, E.; Toth, P., A survey on vertex coloring problems, Int Trans Oper Res, 17, 1, 1-34, (2010) · Zbl 1223.05079
[38] Galinier, P.; Hertz, A., A survey of local search methods for graph coloring, Comput Oper Res, 33, 9, 2547-2562, (2006) · Zbl 1086.90060
[39] Leighton, F. T., A graph coloring algorithm for large scheduling problems, J Res Natl Bur Stand (1934), 84, 6, 489-506, (1979) · Zbl 0437.68021
[40] Oliveira, J.; Ferreira, J., Algorithms for nesting problems, (Vidal, R., Applied Simulated Annealing, Lecture Notes in Economics and Mathematical Systems, 396, (1993), Springer Berlin Heidelberg Berlin), 255-273
[41] Błażewicz, J.; Hawryluk, P.; Walkowiak, R., Using a tabu search approach for solving the two-dimensional irregular cutting problem, Ann Oper Res, 41, 4, 313-325, (1993) · Zbl 0771.90082
[42] Dowsland, K. A.; Dowsland, W. B.; Bennell, J. A., Jostling for position: local improvement for irregular cutting patterns, J Oper Res Soc, 49, 6, 647-658, (1998) · Zbl 1131.90440
[43] Ratanapan, K.; Dagli, C. H., An object-based evolutionary algorithm for solving rectangular piece nesting problems, Systems, Man, and Cybernetics, 1997. Computational Cybernetics and Simulation., 1997 IEEE International Conference on, 2, 989-994, (1997)
[44] Fujita, K.; Akagi, S.; Hirokawa, N., Hybrid approach for optimal nesting using a genetic algorithm and a local minimization algorithm, Proceedings of the 19th Annual ASME Design Automation Conference, 1, 477-484, (1993)
[45] Hopper, E., Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods, (2000), University of Wales. Cardiff, Ph.D. thesis
[46] Jakobs, S., On genetic algorithms for the packing of polygons, Eur J Oper Res, 88, 1, 165-181, (1996) · Zbl 0913.90229
[47] Rebennack, S.; Reinelt, G.; Pardalos, P. M., A tutorial on branch and cut algorithms for the maximum stable set problem, Int Trans Oper Res, 19, 1-2, 161-199, (2012) · Zbl 1270.90092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.