Exact solution techniques for two-dimensional cutting and packing. (English) Zbl 1487.90556
Summary: We survey the main formulations and solution methods for two-dimensional orthogonal cutting and packing problems, where both items and bins are rectangles. We focus on exact methods and relaxations for the four main problems from the literature: finding a packing with minimum height, packing the items into the minimum number of bins, finding a packing of maximum value, and determining the existence of a feasible packing.
MSC:
| 90C27 | Combinatorial optimization |
| 90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |
References:
| [1] | Alvarez-Valdés, R.; Parajón, A.; Tamarit, J., A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems, Computers & Operations Research, 29, 7, 925-947 (2002) · Zbl 0995.90075 |
| [2] | Alvarez-Valdes, R.; Parreño, F.; Tamarit, J., A branch-and-cut algorithm for the pallet loading problem, Computers & Operations Research, 32, 11, 3007-3029 (2005) · Zbl 1071.90046 |
| [3] | Alvarez-Valdes, R.; Parreño, F.; Tamarit, J., A tabu search algorithm for a two-dimensional non-guillotine cutting problem, European Journal of Operational Research, 183, 3, 1167-1182 (2007) · Zbl 1138.90430 |
| [4] | Alvarez-Valdes, R.; Parreño, F.; Tamarit, J., Reactive GRASP for the strip-packing problem, Computers & Operations Research, 35, 4, 1065-1083 (2008) · Zbl 1179.90269 |
| [5] | Alvarez-Valdes, R.; Parreño, F.; Tamarit, J., A branch and bound algorithm for the strip packing problem, OR Spectrum, 31, 2, 431-459 (2009) · Zbl 1160.90696 |
| [6] | Alves, C.; Clautiaux, F.; Valério de Carvalho, J.; Rietz, J., Dual-feasible functions for integer programming and combinatorial optimization (2016), Springer International Publishing: Springer International Publishing Cham · Zbl 1354.90101 |
| [7] | Amor, H. B.; Desrosiers, J.; Valério de Carvalho, J., Dual-optimal inequalities for stabilized column generation, Operations Research, 54, 3, 454-463 (2006) · Zbl 1167.90529 |
| [8] | Arahori, Y.; Imamichi, T.; Nagamochi, H., An exact strip packing algorithm based on canonical forms, Computers & Operations Research, 39, 12, 2991-3011 (2012) · Zbl 1349.90704 |
| [9] | Baker, B.; Coffman Jr., E.; Rivest, R., Orthogonal packing in two dimensions, SIAM Journal on Computing, 9, 4, 846-855 (1980) · Zbl 0447.68080 |
| [10] | Baldacci, R.; Boschetti, M., A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem, European Journal of Operational Research, 183, 3, 1136-1149 (2007) · Zbl 1138.90433 |
| [11] | Balogh, J.; Békési, J.; Dósa, G.; Epstein, L.; Levin, A., Lower bounds for several online variants of bin packing, Proceedings of the revised selected papers 15th international workshop approximation and online algorithms, WAOA 2017, 102-117 (2018), Springer Verlag · Zbl 1436.68401 |
| [12] | Beasley, J., Algorithms for unconstrained two-dimensional guillotine cutting, Journal of the Operational Research Society, 36, 4, 297-306 (1985) · Zbl 0589.90040 |
| [13] | Beasley, J., An exact two-dimensional non-guillotine cutting tree search procedure, Operations Research, 33, 1 (1985) · Zbl 0569.90038 |
| [14] | Beasley, J., Or-library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 11, 1069-1072 (1990) |
| [15] | Bekrar, A.; Kacem, I.; Chu, C.; Sadfi, C., An improved heuristic and an exact algorithm for the 2D strip and bin packing problem, International Journal of Product Development, 10, 1-3, 217-240 (2010) |
| [16] | Belov, G.; Kartak, V. M.; Rohling, H.; Scheithauer, G., One-dimensional relaxations and LP bounds for orthogonal packing, International Transactions in Operational Research, 16, 6, 745-766 (2009) · Zbl 1179.90273 |
| [17] | Belov, G.; Kartak, V. M.; Rohling, H.; Scheithauer, G., Conservative scales in packing problems, OR Spectrum, 35, 2, 505-542 (2013) · Zbl 1263.90069 |
| [18] | Belov, G.; Rohling, H., LP bounds in an interval-graph algorithm for orthogonal-packing feasibility, Operations Research, 61, 2, 483-497 (2013) · Zbl 1267.90118 |
| [19] | Belov, G.; Scheithauer, G., A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting, European Journal of Operational Research, 171, 1, 85-106 (2006) · Zbl 1091.90080 |
| [20] | Benders, J., Partitioning procedures for solving mixed variables programming problems, Numerische Mathematik, 4, 1, 238-252 (1962) · Zbl 0109.38302 |
| [21] | Bennell, J.; Oliveira, J., The geometry of nesting problems: A tutorial, European Journal of Operational Research, 184, 2, 397-415 (2008) · Zbl 1136.90030 |
| [22] | Bennell, J.; Oliveira, J., A tutorial in irregular shape packing problems, Journal of the Operational Research Society, 60, supp 1, S93-S105 (2009) · Zbl 1168.90300 |
| [23] | Bennell, J. A.; Oliveira, J.; Wäscher, G., Cutting and packing, International Journal of Production Economics, 145, 2, 449-450 (2013) |
| [24] | Berkey, J. O.; Wang, P. Y., Two dimensional finite bin packing algorithms, Journal of the Operational Research Society, 38, 423-429 (1987) · Zbl 0611.90079 |
| [25] | Bettinelli, A.; Ceselli, A.; Righini, G., A branch-and-price algorithm for the two-dimensional level strip packing problem, 4OR, 6, 4, 361-374 (2008) · Zbl 1168.90577 |
| [26] | Bezerra, V.; Leao, A.; Oliveira, J.; Santos, M., Models for the two-dimensional level strip packing problem - a review and a computational evaluation, Journal of the Operational Research Society, 71, 4, 606-627 (2020) |
| [27] | Borgulya, I., A parallel hyper-heuristic approach for the two-dimensional rectangular strip-packing problem, Journal of computing and information technology, 22, 4, 251-265 (2014) |
| [28] | Bortfeldt, A.; Wäscher, G., Constraints in container loading - A state-of-the-art review, European Journal of Operational Research, 229, 1, 1-20 (2013) · Zbl 1317.90172 |
| [29] | Boschetti, M.; Hadjiconstantinou, E.; Mingozzi, A., New upper bounds for the two-dimensional othogonal non guillotine cutting stock problem, IMA Journal of Management Mathematics, 13, 2, 95-119 (2002) · Zbl 1097.90546 |
| [30] | Boschetti, M.; Mingozzi, A., The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case, 4OR, 1, 1, 27-42 (2003) · Zbl 1062.90051 |
| [31] | Boschetti, M.; Mingozzi, A., The two-dimensional finite bin packing problem. Part II: New lower and upper bounds, 4OR, 1, 2, 135-147 (2003) · Zbl 1097.90033 |
| [32] | Boschetti, M.; Montaletti, L., An exact algorithm for the two-dimensional strip-packing problem, Operations Research, 58, 6, 1774-1791 (2010) · Zbl 1228.90090 |
| [33] | Burke, E.; Hyde, M.; Kendall, G., A squeaky wheel optimisation methodology for two-dimensional strip packing, Computers & Operations Research, 38, 7, 1035-1044 (2011) · Zbl 1205.90240 |
| [34] | Burke, E.; Kendall, G.; Whitwell, G., A new placement heuristic for the orthogonal stock-cutting problem, Operations Research, 52, 4, 655-671 (2004) · Zbl 1165.90690 |
| [35] | Burke, E. K.; Hyde, M.; Kendall, G.; Woodward, J., A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics, IEEE Transactions on Evolutionary Computation, 14, 6, 942-958 (2010) |
| [36] | Caprara, A.; Monaci, M., On the two-dimensional knapsack problem, Operations Research Letters, 32, 1, 5-14 (2004) · Zbl 1056.90115 |
| [37] | Caprara, A.; Monaci, M., Bidimensional packing by bilinear programming, Mathematical Programming, 118, 1, 75-108 (2009) · Zbl 1169.90428 |
| [38] | Castro, P.; Grossmann, I., From time representation in scheduling to the solution of strip packing problems, Computers & Chemical Engineering, 44, 45-57 (2012) |
| [39] | Castro, P.; Oliveira, J., Scheduling inspired models for two-dimensional packing problems, European Journal of Operational Research, 215, 1, 45-56 (2011) · Zbl 1242.90108 |
| [40] | Chazelle, B., The bottom-left bin-packing heuristic: An efficient implementation, IEEE Transactions on Computers, C-32, 8, 697-707 (1983) · Zbl 0526.68065 |
| [41] | Chen, C.; Lee, S.; Shen, Q., An analytical model for the container loading problem, European Journal of Operational Research, 80, 1, 68-76 (1995) · Zbl 0927.90087 |
| [42] | Christensen, H. I.; Khan, A.; Pokutta, S.; Tetali, P., Approximation and online algorithms for multidimensional bin packing: A survey, Computer Science Review, 24, 63-79 (2017) · Zbl 1398.68007 |
| [43] | Christofides, N.; Hadjiconstantinou, E., An exact algorithm for orthogonal 2-d cutting problems using guillotine cuts, European Journal of Operational Research, 83, 1, 21-38 (1995) · Zbl 0903.90134 |
| [44] | Christofides, N.; Mingozzi, A.; Toth, P., State-space relaxation procedures for the computation of bounds to routing problems, Networks, 11, 2, 145-164 (1981) · Zbl 0458.90071 |
| [45] | Christofides, N.; Whitlock, C., An algorithm for two-dimensional cutting problems, Operations Research, 25, 1, 30-44 (1977) · Zbl 0369.90059 |
| [46] | Cintra, G.; Miyazawa, F.; Wakabayashi, Y.; Xavier, E., Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation, European Journal of Operational Research, 191, 1, 61-85 (2008) · Zbl 1146.90499 |
| [47] | Clautiaux, F.; Alves, C.; Valério de Carvalho, J., A survey of dual-feasible and superadditive functions, Annals of Operations Research, 179, 1, 317-342 (2010) · Zbl 1229.90155 |
| [48] | Clautiaux, F.; Carlier, J.; Moukrim, A., A new exact method for the two-dimensional orthogonal packing problem, European Journal of Operational Research, 183, 3, 1196-1211 (2007) · Zbl 1135.90045 |
| [49] | Clautiaux, F.; Carlier, J.; Moukrim, A., New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation, Computers & Operations Research, 34, 8, 2223-2250 (2007) · Zbl 1144.90465 |
| [50] | Clautiaux, F.; Jouglet, A.; Carlier, J.; Moukrim, A., A new constraint programming approach for the orthogonal packing problem, Computers & Operations Research, 35, 3, 944-959 (2008) · Zbl 1278.90147 |
| [51] | Clautiaux, F.; Jouglet, A.; Moukrim, A., A new graph-theoretical model for k-dimensional guillotine-cutting problems, (McGeoch, C. C., Experimental algorithms (2008), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 43-54 |
| [52] | Clautiaux, F.; Sadykov, R.; Vanderbeck, F.; Viaud, Q., Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem, Discrete Optimization, 29, 18-44 (2018) · Zbl 1506.90219 |
| [53] | Codato, G.; Fischetti, M., Combinatorial Benders’ cuts for mixed-integer linear programming, Operations Research, 54, 4, 756-766 (2006) · Zbl 1167.90601 |
| [54] | Coffman Jr., E.; Csirik, J.; Galambos, G.; Martello, S.; Vigo, D., Bin packing approximation algorithms: Survey and classification, Handbook of combinatorial optimization, 455-531 (2013), Springer: Springer New York, NY |
| [55] | Costa, G.; Delorme, M.; Iori, M.; Malaguti, E.; Martello, S., Training software for orthogonal packing problems, Computers & Industrial Engineering, 111, 139-147 (2017) |
| [56] | Côté, J.-F.; Dell’Amico, M.; Iori, M., Combinatorial Benders’ cuts for the strip packing problem, Operations Research, 62, 3, 643-661 (2014) · Zbl 1302.90173 |
| [57] | Côté, J.-F.; Gendreau, M.; Potvin, J.-Y., An exact algorithm for the two-dimensional orthogonal packing problem with unloading constraints, Operations Research, 62, 5, 1126-1141 (2014) · Zbl 1327.90254 |
| [58] | Côté, J.-F.; Iori, M., The meet-in-the-middle principle for cutting and packing problems, INFORMS Journal on Computing, 30, 4, 646-661 (2018) · Zbl 1528.90211 |
| [59] | Crainic, T.; Perboli, G.; Tadei, R., Recent advances in multi-dimensional packing problems, (Volosencu, C., New technologies - trends, innovations and research (2012), IntechOpen: IntechOpen Rijeka), 91-110 |
| [60] | Cui, Y.; Zhao, Z., Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns, European Journal of Operational Research, 231, 2, 288-298 (2013) · Zbl 1317.90326 |
| [61] | Cui, Y.-P.; Zhou, Y.; Cui, Y., Triple-solution approach for the strip packing problem with two-staged patterns, Journal of Combinatorial Optimization, 34, 2, 588-604 (2017) · Zbl 1381.90070 |
| [62] | Cung, V.-D.; Hifi, M.; Le Cun, B., Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm, International Transactions in Operational Research, 7, 3, 185-210 (2000) |
| [63] | Dantzig, G., Discrete variable extremum problems, Operations Research, 5, 2, 266-277 (1957) · Zbl 1414.90353 |
| [64] | Dell’Amico, M.; Martello, S., Optimal scheduling of tasks on identical parallel processors, ORSA Journal on Computing, 7, 2, 191-200 (1995) · Zbl 0859.90081 |
| [65] | Delorme, M.; Iori, M.; Martello, S., Bin packing and cutting stock problems: Mathematical models and exact algorithms, European Journal of Operational Research, 255, 1, 1-20 (2016) · Zbl 1346.90700 |
| [66] | Delorme, M.; Iori, M.; Martello, S., Logic based Benders’ decomposition for orthogonal stock cutting problems, Computers & Operations Research, 78, 290-298 (2017) · Zbl 1391.90514 |
| [67] | Delorme, M.; Iori, M.; Martello, S., BPPLIB: a library for bin packing and cutting stock problems, Optimization Letters, 12, 2, 235-250 (2018) · Zbl 1401.90183 |
| [68] | Dolatabadi, M.; Lodi, A.; Monaci, M., Exact algorithms for the two-dimensional guillotine knapsack, Computers & Operations Research, 39, 1, 48-53 (2012) · Zbl 1251.90237 |
| [69] | Dowsland, K. A.; Dowsland, W. B., Solution approaches to irregular nesting problems, European Journal of Operational Research, 84, 506-521 (1995) · Zbl 0918.90116 |
| [70] | Dyckhoff, H., A new linear programming approach to the cutting stock problem, Operations Research, 29, 6, 1092-1104 (1981) · Zbl 0474.90059 |
| [71] | Dyckhoff, H., A typology of cutting and packing problems, European Journal of Operational Research, 44, 2, 145-159 (1990) · Zbl 0684.90076 |
| [72] | Fekete, S.; Schepers, J., New classes of fast lower bounds for bin packing problems, Mathematical Programming, 91, 1, 11-31 (2001) · Zbl 1051.90020 |
| [73] | Fekete, S.; Schepers, J., A combinatorial characterization of higher-dimensional orthogonal packing, Mathematics of Operations Research, 29, 2, 353-368 (2004) · Zbl 1082.90095 |
| [74] | Fekete, S.; Schepers, J., A general framework for bounds for higher-dimensional orthogonal packing problems, Mathematical Methods of Operations Research, 60, 2, 311-329 (2004) · Zbl 1076.90049 |
| [75] | Fekete, S.; Schepers, J.; van der Veen, J., An exact algorithm for higher-dimensional orthogonal packing, Operations Research, 55, 3, 569-587 (2007) · Zbl 1167.90483 |
| [76] | Ferreira, E.; Oliveira, J., Fekete and Schepers’ graph-based algorithm for the two-dimensional orthogonal packing problem revisited, (A., B.; J., H.; H., K.; G., P.; R., S., Intelligent decision support (2008), Gabler: Gabler Wiesbaden), 15-31 |
| [77] | Fleszar, K., An exact algorithm for the two-dimensional stage-unrestricted guillotine cutting/packing decision problem, INFORMS Journal on Computing, 28, 4, 703-720 (2016) · Zbl 1355.90080 |
| [78] | Friedow, I.; Scheithauer, G., Using contiguous 2D-feasible 1D cutting patterns for the 2D strip packing problem, Proceedings of the Operations research proceedings 2015, 71-77 (2017), Springer International Publishing · Zbl 1375.90249 |
| [79] | Friesen, D.; Langston, M., Variable sized bin packing, SIAM Journal on Computing, 15, 1, 222-230 (1986) · Zbl 0589.68036 |
| [80] | Furini, F.; Malaguti, E., Models for the two-dimensional two-stage cutting stock problem with multiple stock size, Computers & Operations Research, 40, 8, 1953-1962 (2013) · Zbl 1348.90487 |
| [81] | Furini, F.; Malaguti, E.; Durán, R.; Persiani, A.; Toth, P., A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size, European Journal of Operational Research, 218, 1, 251-260 (2012) · Zbl 1244.90191 |
| [82] | Furini, F.; Malaguti, E.; Thomopulos, D., Modeling two-dimensional guillotine cutting problems via integer programming, INFORMS Journal on Computing, 28, 4, 736-751 (2016) · Zbl 1355.90081 |
| [83] | Gálvez, W.; Grandoni, F.; Heydrich, S.; Ingala, S.; Khan, A.; Wiese, A., Approximating geometric knapsack via l-packings, Proceedings of the 2017 IEEE 58th annual symposium on foundations of computer science (FOCS), 260-271 (2017) |
| [84] | Garey, M.; Johnson, D., Computers and intractability: A guide to the theory of NP-completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0411.68039 |
| [85] | Gendreau, M.; Iori, M.; Laporte, G.; Martello, S., A tabu search algorithm for a routing and container loading problem, Transportation Science, 40, 3, 342-350 (2006) |
| [86] | Gendreau, M.; Iori, M.; Laporte, G.; Martello, S., A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints, Networks, 51, 1, 4-18 (2008) · Zbl 1146.90012 |
| [87] | Geoffrion, A., Generalized Benders decomposition, Journal of Optimization Theory and Applications, 10, 4, 237-260 (1972) · Zbl 0229.90024 |
| [88] | Gilmore, P. C.; Gomory, R. E., Multistage cutting stock problems of two and more dimensions, Operations Research, 13, 1, 94-120 (1965) · Zbl 0128.39601 |
| [89] | Gonçalves, J.; Resende, M., A biased random key genetic algorithm for 2D and 3D bin packing problems, International Journal of Production Economics, 145, 2, 500-510 (2013) |
| [90] | Grandcolas, S.; Pinto, C., A sat encoding for multi-dimensional packing problems, (Lodi, A.; Milano, M.; Toth, P., Integration of ai and or techniques in constraint programming for combinatorial optimization problems (2010), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 141-146 · Zbl 1285.90048 |
| [91] | Hadjiconstantinou, E.; Christofides, N., An exact algorithm for general, orthogonal, two-dimensional knapsack problems, European Journal of Operational Research, 83, 1, 39-56 (1995) · Zbl 0903.90124 |
| [92] | Hadjiconstantinou, E.; Iori, M., A hybrid genetic algorithm for the two-dimensional single large object placement problem, European Journal of Operational Research, 183, 3, 1150-1166 (2007) · Zbl 1146.90481 |
| [93] | Han, X.; Iwama, K.; Ye, D.; Zhang, G., Approximate strip packing: Revisited, Information and Computation, 249, 110-120 (2016) · Zbl 1345.68275 |
| [94] | Henning, S.; Jansen, K.; Rau, M.; Schmarje, L., Complexity and inapproximability results for parallel task scheduling and strip packing, Theory of Computing Systems, 64, 120-140 (2020) · Zbl 1477.68119 |
| [95] | Herz, J., Recursive computational procedure for two-dimensional stock cutting, IBM Journal of Research and Development, 16, 5, 462-469 (1972) · Zbl 0265.90057 |
| [96] | Hifi, M., An improvement of Viswanathan and Bagchi’s exact algorithm for constrained two-dimensional cutting stock, Computers & Operations Research, 24, 8, 727-736 (1997) · Zbl 0914.90225 |
| [97] | Hooker, J.; Ottosson, G., Logic-based Benders decomposition, Mathematical Programming, 96, 1, 33-60 (2003) · Zbl 1023.90082 |
| [98] | Imahori, S.; Yagiura, M., The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio, Computers & Operations Research, 37, 2, 325-333 (2010) · Zbl 1175.90429 |
| [99] | Iori, M.; Martello, S., Routing problems with loading constraints, TOP, 18, 1, 4-27 (2010) · Zbl 1279.90146 |
| [100] | Iori, M.; Martello, S., An annotated bibliography of combined routing and loading problems, Yugoslav Journal of Operations Research, 23, 3, 311-326 (2013) · Zbl 1313.90026 |
| [101] | Iori, M.; Martello, S.; Monaci, M., Metaheuristic algorithms for the strip packing problem, Optimization and Industry: New Frontiers, 159-179 (2003), Springer US · Zbl 1051.90030 |
| [102] | Iori, M.; Salazar González, J.; Vigo, D., An exact approach for the vehicle routing problem with two-dimensional loading constraints, Transportation Science, 41, 2, 253-264 (2007) |
| [103] | Jakobs, S., On genetic algorithms for the packing of polygons, European Journal of Operational Research, 88, 1, 165-181 (1996) · Zbl 0913.90229 |
| [104] | Jansen, K.; Rau, M., Closing the gap for pseudo-polynomial strip packing, Proceedings of the paper presented at ESA 2019, Munich) (2019) · Zbl 07525499 |
| [105] | Johnson, D. S., Near-optimal bin packing algorithms (1973), MIT: MIT Cambridge, MA, Ph.D. thesis. |
| [106] | Joncour, C.; Pêcher, A., Consecutive ones matrices for multi-dimensional orthogonal packing problems, Electronic Notes in Discrete Mathematics, 36, 327-334 (2010) · Zbl 1237.90198 |
| [107] | Joncour, C.; Pêcher, A.; Valicov, P., MPQ-trees for the orthogonal packing problem, Electronic Notes in Discrete Mathematics, 11, 423-429 (2012) · Zbl 1237.90003 |
| [108] | Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack problems (2004), Springer, Berlin, Germany · Zbl 1103.90003 |
| [109] | Kenmochi, M.; Imamichi, T.; Nonobe, K.; Yagiura, M.; Nagamochi, H., Exact algorithms for the two-dimensional strip packing problem with and without rotations, European Journal of Operational Research, 198, 1, 73-83 (2009) · Zbl 1163.90803 |
| [110] | Kierkosz, I.; Luczak, M., A hybrid evolutionary algorithm for the two-dimensional packing problem, Central European Journal of Operations Research, 22, 4, 729-753 (2014) · Zbl 1339.90337 |
| [111] | Korf, R.; Moffitt, M.; Pollack, M., Optimal rectangle packing, Annals of Operations Research, 179, 1, 261-295 (2010) · Zbl 1201.90172 |
| [112] | Kwon, B.; Lee, G., Spatial scheduling for large assembly blocks in shipbuilding, Computers & Industrial Engineering, 89, 203-212 (2015) |
| [113] | Leao, A.; Toledo, F.; Oliveira, J.; Carravilla, M.; Alvarez-Valdés, R., Irregular packing problems: A review of mathematical models, European Journal of Operational Research, 282, 3, 803-822 (2020) · Zbl 1431.90133 |
| [114] | Lesh, N.; Marks, J.; McMahon, A.; Mitzenmacher, M., Exhaustive approaches to 2D rectangular perfect packings, Information Processing Letters, 90, 1, 7-14 (2004) · Zbl 1170.90523 |
| [115] | Lodi, A.; Martello, S.; Monaci, M., Two-dimensional packing problems: A survey, European Journal of Operational Research, 141, 2, 241-252 (2002) · Zbl 1081.90576 |
| [116] | Lodi, A.; Martello, S.; Monaci, M.; Cicconetti, C.; Lenzini, L.; Mingozzi, E.; Eklund, C.; Moilanen, J., Efficient two-dimensional packing algorithms for mobile WiMAX, Management Science, 57, 12, 2130-2144 (2011) |
| [117] | Lodi, A.; Martello, S.; Monaci, M.; Vigo, D., Two-dimensional bin packing problems, (Paschos, V. T., Paradigms of combinatorial optimization: Problems and new approaches (2014), John Wiley & Sons, Ltd: John Wiley & Sons, Ltd Hoboken, NJ, USA), 107-129 · Zbl 1204.90085 |
| [118] | Lodi, A.; Martello, S.; Vigo, D., Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS Journal on Computing, 11, 4, 345-357 (1999) · Zbl 1034.90500 |
| [119] | Lodi, A.; Martello, S.; Vigo, D., Recent advances on two-dimensional bin packing problems, Discrete Applied Mathematics, 123, 1, 379-396 (2002) · Zbl 1022.90020 |
| [120] | Lodi, A.; Martello, S.; Vigo, D., Models and bounds for two-dimensional level packing problems, Journal of Combinatorial Optimization, 8, 3, 363-379 (2004) · Zbl 1084.90031 |
| [121] | Lodi, A.; Martello, S.; Vigo, D., TSpack: a unified tabu search code for multi-dimensional bin packing problems, Annals of Operations Research, 131, 1-4, 203-213 (2004) · Zbl 1066.90142 |
| [122] | Lodi, A.; Monaci, M., Integer linear programming models for 2-staged two-dimensional knapsack problems, Mathematical Programming, 94, 2, 257-278 (2003) · Zbl 1030.90064 |
| [123] | Macedo, R.; Alves, C.; Valério de Carvalho, J., Arc-flow model for the two-dimensional guillotine cutting stock problem, Computers & Operations Research, 37, 6, 991-1001 (2010) · Zbl 1178.90292 |
| [124] | Martello, S., Knapsack, packing and cutting, INFOR, 32, 4, 217-218 (1994) · Zbl 0806.00019 |
| [125] | Martello, S., Two-dimensional packing problems in telecommunications, Pesquisa Operacional, 34, 1, 31-38 (2014) |
| [126] | Martello, S.; Monaci, M., Models and algorithms for packing rectangles into the smallest square, Computers & Operations Research, 63, 161-171 (2015) · Zbl 1349.68321 |
| [127] | Martello, S.; Monaci, M.; Vigo, D., An exact approach to the strip-packing problem, INFORMS Journal on Computing, 15, 3, 310-319 (2003) · Zbl 1238.90116 |
| [128] | Martello, S.; Toth, P., Lower bounds and reduction procedures for the bin packing problem, Discrete Applied Mathematics, 28, 1, 59-70 (1990) · Zbl 0704.90074 |
| [129] | (free download at http://www.or.deis.unibo.it/knapsack.html) |
| [130] | Martello, S.; Vigo, D., Exact solution of the two-dimensional finite bin packing problem, Management Science, 44, 3, 388-399 (1998) · Zbl 0989.90114 |
| [131] | Martin, M.; Birgin, E.; Lobato, R.; Morabito, R.; Munari, P., Models for the two-dimensional rectangular single large placement problem with guillotine cuts and constrained pattern, International Transactions in Operational Research, 27, 2, 767-793 (2020) · Zbl 07767413 |
| [132] | Martin, M.; Morabito, R.; Munari, P., A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem, Computers & Operations Research, 115, 104851 (2020) · Zbl 1458.90553 |
| [133] | Matayoshi, M., The 2D strip packing problem: A new approach with verification by EA, Proceedings of the 2010 IEEE international conference on systems, man and cybernetics, 2492-2499 (2010) |
| [134] | Melega, G.; Araujo, S.; Jans, R., Classification and literature review of integrated lot-sizing and cutting stock problems, European Journal of Operational Research, 271, 1, 1-19 (2018) · Zbl 1403.90038 |
| [135] | Messaoud, S.; Chu, C.; Espinouse, M.-L., Characterization and modelling of guillotine constraints, European Journal of Operational Research, 191, 1, 112-126 (2008) · Zbl 1145.90057 |
| [136] | Mesyagutov, M.; Mukhacheva, E.; Belov, G.; Scheithauer, G., Packing of one-dimensional bins with contiguous selection of identical items: An exact method of optimal solution, Automation and Remote Control, 72, 1, 141-159 (2011) · Zbl 1233.90242 |
| [137] | Mesyagutov, M.; Scheithauer, G.; Belov, G., LP bounds in various constraint programming approaches for orthogonal packing, Computers & Operations Research, 39, 10, 2425-2438 (2012) · Zbl 1251.90331 |
| [138] | Monaci, M.; Toth, P., A set-covering-based heuristic approach for bin-packing problems, INFORMS Journal on Computing, 18, 1, 71-85 (2006) · Zbl 1241.90191 |
| [139] | Morabito, R.; Arenales, M., Staged and constrained two-dimensional guillotine cutting problems: An AND/OR-graph approach, European Journal of Operational Research, 94, 3, 548-560 (1996) · Zbl 0947.90537 |
| [140] | Morabito, R.; Pureza, V., Heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem, Annals of Operations Research, 179, 297-315 (2010) · Zbl 1201.90174 |
| [141] | Mrad, M., An arc flow-based optimization approach for the two-stage guillotine strip cutting problem, Journal of the Operational Research Society, 66, 11, 1850-1859 (2015) |
| [142] | Mrad, M.; Meftahi, I.; Haouari, M., A branch-and-price algorithm for the two-stage guillotine cutting stock problem, The Journal of the Operational Research Society, 64, 5, 629-637 (2013) |
| [143] | Nesello, V.; Delorme, M.; Iori, M.; Subramanian, A., Mathematical models and decomposition algorithms for makespan minimization in plastic rolls production, Journal of the Operational Research Society, 69, 3, 326-339 (2018) |
| [144] | Ntene, N.; van Vuuren, J., A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem, Discrete Optimization, 6, 2, 174-188 (2009) · Zbl 1159.90527 |
| [145] | Oliveira, J.; Júnior, A. N.; Silva, E.; Carravilla, M., A survey on heuristics for the two-dimensional rectangular strip packing problem, Pesquisa Operacional, 36, 2, 197-226 (2016) |
| [146] | Oliveira, J.; Wäscher, G., Cutting and packing, European Journal of Operational Research, 183, 3, 1106-1108 (2007) |
| [147] | Onodera, H.; Taniguchi, Y.; Tamaru, K., Branch-and-bound placement for building block layout, Proceedings of the 28th ACM/IEEE design automation conference, 433-439 (1991) |
| [148] | Ortmann, F.; van Vuuren, J., Modified strip packing heuristics for the rectangular variable-sized bin packing problem, ORiON, 26, 1, 21-44 (2010) |
| [149] | Parreño, F.; Alvarez-Valdes, R.; Oliveira, J.; Tamarit, J., A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing, Annals of Operations Research, 179, 1, 203-220 (2010) · Zbl 1201.90176 |
| [150] | Pisinger, D.; Sigurd, M., The two-dimensional bin packing problem with variable bin sizes and costs, Discrete Optimization, 2, 2, 154-167 (2005) · Zbl 1077.90057 |
| [151] | Pisinger, D.; Sigurd, M., Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem, INFORMS Journal on Computing, 19, 1, 36-51 (2007) · Zbl 1241.90118 |
| [152] | Pollaris, H.; Braekers, K.; Caris, A.; Janssens, G.; Limbourg, S., Vehicle routing problems with loading constraints: State-of-the-art and future directions, OR Spectrum, 37, 2, 297-330 (2015) · Zbl 1311.90032 |
| [153] | Puchinger, J.; Raidl, G., Models and algorithms for three-stage two-dimensional bin packing, European Journal of Operational Research, 183, 3, 1304-1327 (2007) · Zbl 1135.90029 |
| [154] | Queiroz, T.; Hokama, P.; Schouery, R.; Miyazawa, F., Two-dimensional disjunctively constrained knapsack problem: Heuristic and exact approaches, Computers & Industrial Engineering, 105, 313-328 (2017) |
| [155] | Queiroz, T.; Miyazawa, F., Order and static stability into the strip packing problem, Annals of Operations Research, 223, 1, 137-154 (2014) · Zbl 1306.90124 |
| [156] | Rao, M., On the cutting stock problem, Journal of the Computer Society of India, 7, 35-39 (1976) |
| [157] | Rietz, J.; Alves, C.; Valério de Carvalho, J., Theoretical investigations on maximal dual feasible functions, Operations Research Letters, 38, 3, 174-178 (2010) · Zbl 1192.90127 |
| [158] | Rietz, J.; Alves, C.; Valério de Carvalho, J., Worst-case analysis of maximal dual feasible functions, Optimization Letters, 6, 8, 1-19 (2011) |
| [159] | Rietz, J.; Alves, C.; Valério de Carvalho, J., On the extremality of maximal dual feasible functions, Operations Research Letters, 40, 1, 25-30 (2012) · Zbl 1242.90202 |
| [160] | Russo, M.; Boccia, M.; Sforza, A.; Sterle, C., Constrained two-dimensional guillotine cutting problem: upper-bound review and categorization, International Transactions in Operational Research, 27, 2, 794-834 (2020) · Zbl 07767414 |
| [161] | Russo, M.; Sforza, A.; Sterle, C., An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems, Computers & Operations Research, 50, 97-114 (2014) · Zbl 1348.90554 |
| [162] | Scheithauer, G., Equivalence and dominance for problems of optimal packing of rectangles, Ricerca Operativa, 83, 3-34 (1997) |
| [163] | Scheithauer, G., Introduction to cutting and packing optimization (2018), Springer International Publishing · Zbl 1391.90002 |
| [164] | Serairi, M.; Haouari, M., A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem, RAIRO-Operations Research, 52, 2, 391-414 (2018) · Zbl 1405.90027 |
| [165] | Silva, E.; Alvelos, F.; Valério de Carvalho, J., An integer programming model for two- and three-stage two-dimensional cutting stock problems, European Journal of Operational Research, 205, 3, 699-708 (2010) · Zbl 1188.90181 |
| [166] | Silva, E.; Oliveira, J.; Wäscher, G., 2DCPackGen: A problem generator for two-dimensional rectangular cutting and packing problems, European Journal of Operational Research, 237, 3, 846-856 (2014) · Zbl 1338.90355 |
| [167] | Silva, E.; Oliveira, J.; Wäscher, G., The pallet loading problem: a review of solution methods and computational experiments, International Transactions in Operational Research, 23, 1-2, 147-172 (2016) · Zbl 1338.90354 |
| [168] | Soh, T.; Inoue, K.; Tamura, N.; Banbara, M.; Nabeshima, H., A sat-based method for solving the two-dimensional strip packing problem, Fundamenta Informaticae, 102, 3-4, 467-487 (2010) · Zbl 1214.68374 |
| [169] | Strecker, T.; Hennig, L., Automatic layouting of personalized newspaper pages, (Fleischmann, B.; Borgwardt, K.-H.; Klein, R.; Tuma, A., Proceedings of the Operations research proceedings 2008 (2009), Springer: Springer Berlin, Heidelberg), 469-474 · Zbl 1209.90258 |
| [170] | Terno, J.; Lindemann, R.; Scheithauer, G., Zuschnittprobleme and ihre praktische lösung, Technical Report (1987), Verlag Harry Deutsch, Thun und FrankfurtMain · Zbl 0657.65089 |
| [171] | Valério de Carvalho, J., Exact solution of bin-packing problems using column generation and branch-and-bound, Annals of Operations Research, 86, 0, 629-659 (1999) · Zbl 0922.90113 |
| [172] | Valério de Carvalho, J., LP models for bin packing and cutting stock problems, European Journal of Operational Research, 141, 2, 253-273 (2002) · Zbl 1059.90095 |
| [173] | Valério de Carvalho, J., Using extra dual cuts to accelerate column generation, INFORMS Journal on Computing, 17, 2, 175-182 (2005) · Zbl 1239.90089 |
| [174] | Vanderbeck, F., A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem, Management Science, 47, 6, 864-879 (2001) · Zbl 1232.90326 |
| [175] | Velasco, A.; Uchoa, E., Improved state space relaxation for constrained two-dimensional guillotine cutting problems, European Journal of Operational Research, 272, 1, 106-120 (2019) · Zbl 1403.90589 |
| [176] | Viswanathan, K.; Bagchi, A., Best-first search methods for constrained two-dimensional cutting stock problems, Operations Research, 41, 4, 768-776 (1993) · Zbl 0782.90076 |
| [177] | Wäscher, G.; Haußner, H.; Schumann, H., An improved typology of cutting and packing problems, European Journal of Operational Research, 183, 3, 1109-1130 (2007) · Zbl 1278.90347 |
| [178] | Wei, L.; Oon, W.-C.; Zhu, W.; Lim, A., A skyline heuristic for the 2D rectangular packing and strip packing problems, European Journal of Operational Research, 215, 2, 337-346 (2011) · Zbl 1237.90213 |
| [179] | Wei, L.; Qin, H.; Cheang, B.; Xu, X., An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem, International Transactions in Operational Research, 23, 1-2, 65-92 (2016) · Zbl 1338.90357 |
| [180] | Xu, Z.; Lee, C.-Y., New lower bound and exact method for the continuous berth allocation problem, Operations Research, 66, 3, 778-798 (2018) · Zbl 1443.90197 |
| [181] | Yanasse, H.; Katsurayama, D., Checkerboard pattern: proposals for its generation, International Transactions in Operational Research, 12, 1, 21-45 (2005) · Zbl 1060.90066 |
| [182] | Yanasse, H.; Katsurayama, D., An enumeration scheme to generate constrained exact checkerboard patterns, Computers & Operations Research, 35, 6, 2114-2128 (2008) · Zbl 1152.90583 |
| [183] | Yu, G.; Mao, Y.; Xiao, J., A new lower bound for online strip packing, European Journal of Operational Research, 250, 3, 754-759 (2016) · Zbl 1346.90724 |
| [184] | Yu, G.; Mao, Y.; Xiao, J., A new upper bound for the online square packing problem in a strip, Journal of Combinatorial Optimization, 33, 4, 1411-1420 (2017) · Zbl 1376.90055 |
| [185] | Yu, G.; Mao, Y.; Xiao, J., New upper bounds for online strip packing, Discrete Optimization, 23, 20-32 (2017) · Zbl 1387.90231 |
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.
