{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:48:40Z","timestamp":1761598120435,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T00:00:00Z","timestamp":1569283200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T00:00:00Z","timestamp":1569283200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"crossref","award":["308312\/2016-3"],"award-info":[{"award-number":["308312\/2016-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005285","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de Goi\u00e1s","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005285","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s10288-019-00419-9","type":"journal-article","created":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T08:03:08Z","timestamp":1569312188000},"page":"293-339","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Grids for cutting and packing problems: a study in the 2D knapsack problem"],"prefix":"10.1007","volume":"18","author":[{"given":"J\u00e9ssica Gabriela","family":"de Almeida Cunha","sequence":"first","affiliation":[]},{"given":"Vin\u00edcius Loti","family":"de\u00a0Lima","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2674-3366","authenticated-orcid":false,"given":"Thiago Alves","family":"de Queiroz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,9,24]]},"reference":[{"issue":"11","key":"419_CR1","doi-asserted-by":"publisher","first-page":"3007","DOI":"10.1016\/j.cor.2004.04.010","volume":"32","author":"R Alvarez-Valdes","year":"2005","unstructured":"Alvarez-Valdes R, Parre\u00f1o F, Tamarit JM (2005) A branch-and-cut algorithm for the pallet loading problem. Comput Oper Res 32(11):3007\u20133029","journal-title":"Comput Oper Res"},{"key":"419_CR2","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s00291-008-0128-5","volume":"31","author":"R Alvarez-Valdes","year":"2009","unstructured":"Alvarez-Valdes R, Parre\u00f1o F, Tamarit JM (2009) A branch and bound algorithm for the strip packing problem. OR Spectr 31:431\u2013459","journal-title":"OR Spectr"},{"issue":"7","key":"419_CR3","doi-asserted-by":"publisher","first-page":"1487","DOI":"10.1016\/j.cor.2011.08.021","volume":"39","author":"C Alves","year":"2012","unstructured":"Alves C, Br\u00e1s P, de Carvalho JV, Pinto T (2012) New constructive algorithms for leather nesting in the automotive industry. Comput Oper Res 39(7):1487\u20131505","journal-title":"Comput Oper Res"},{"issue":"12","key":"419_CR4","doi-asserted-by":"publisher","first-page":"2991","DOI":"10.1016\/j.cor.2012.03.003","volume":"39","author":"Y Arahori","year":"2012","unstructured":"Arahori Y, Imamichi T, Nagamochi H (2012) An exact strip packing algorithm based on canonical forms. Comput Oper Res 39(12):2991\u20133011","journal-title":"Comput Oper Res"},{"key":"419_CR5","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1016\/j.ejor.2005.11.060","volume":"183","author":"R Baldacci","year":"2007","unstructured":"Baldacci R, Boschetti MA (2007) A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem. Eur J Oper Res 183:1136\u20131149","journal-title":"Eur J Oper Res"},{"issue":"19","key":"419_CR6","first-page":"9802","volume":"218","author":"MM Baldi","year":"2012","unstructured":"Baldi MM, Perboli G, Tadei R (2012) The three-dimensional knapsack problem with balancing constraints. Appl Math Comput 218(19):9802\u20139818","journal-title":"Appl Math Comput"},{"issue":"4","key":"419_CR7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1057\/jors.1985.51","volume":"36","author":"JE Beasley","year":"1985","unstructured":"Beasley JE (1985a) Algorithms for unconstrained two-dimensional guillotine cutting. J Oper Res Soc 36(4):297\u2013306","journal-title":"J Oper Res Soc"},{"key":"419_CR8","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1287\/opre.33.1.49","volume":"33","author":"JE Beasley","year":"1985","unstructured":"Beasley JE (1985b) An exact two-dimensional non-guillotine cutting tree search procedure. Oper Res 33:49\u201364","journal-title":"Oper Res"},{"issue":"2","key":"419_CR9","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1057\/jors.2008.141","volume":"61","author":"EG Birgin","year":"2010","unstructured":"Birgin EG, Lobato RD, Morabito R (2010) An effective recursive partitioning approach for the packing of identical rectangles in a rectangle. J Oper Res Soc 61(2):306\u2013320","journal-title":"J Oper Res Soc"},{"issue":"2","key":"419_CR10","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1057\/jors.2011.6","volume":"63","author":"EG Birgin","year":"2012","unstructured":"Birgin EG, Lobato RD, Morabito R (2012) Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm. J Oper Res Soc 63(2):183\u2013200","journal-title":"J Oper Res Soc"},{"issue":"6","key":"419_CR11","doi-asserted-by":"publisher","first-page":"1774","DOI":"10.1287\/opre.1100.0833","volume":"58","author":"MA Boschetti","year":"2010","unstructured":"Boschetti MA, Montaletti L (2010) An exact algorithm for the two-dimensional strip-packing problem. Oper Res 58(6):1774\u20131791","journal-title":"Oper Res"},{"issue":"2","key":"419_CR12","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1093\/imaman\/13.2.95","volume":"13","author":"MA Boschetti","year":"2002","unstructured":"Boschetti MA, Mingozzi A, Hadjiconstantinou E (2002) New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem. IMA J Manag Math 13(2):95\u2013119","journal-title":"IMA J Manag Math"},{"issue":"4","key":"419_CR13","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s10288-004-0054-6","volume":"2","author":"A Caprara","year":"2004","unstructured":"Caprara A (2004) Knapsack problems: a book review. 4OR 2(4):317\u2013320","journal-title":"4OR"},{"key":"419_CR14","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/S0167-6377(03)00057-9","volume":"32","author":"A Caprara","year":"2004","unstructured":"Caprara A, Monaci M (2004) On the two-dimensional knapsack problem. Oper Res Lett 32:5\u201314","journal-title":"Oper Res Lett"},{"issue":"3","key":"419_CR15","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/0377-2217(94)90244-5","volume":"73","author":"C Carnieri","year":"1994","unstructured":"Carnieri C, Mendoza GA, Gavinho LG (1994) Solution procedures for cutting lumber into furniture parts. Eur J Oper Res 73(3):495\u2013501","journal-title":"Eur J Oper Res"},{"issue":"1","key":"419_CR16","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1287\/opre.25.1.30","volume":"25","author":"N Christofides","year":"1977","unstructured":"Christofides N, Whitlock C (1977) An algorithm for two-dimensional cutting problems. Oper Res 25(1):30\u201344","journal-title":"Oper Res"},{"key":"419_CR17","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.ejor.2007.08.007","volume":"191","author":"GF Cintra","year":"2008","unstructured":"Cintra GF, Miyazawa FK, Wakabayashi Y, Xavier EC (2008) Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. Eur J Oper Res 191:59\u201383","journal-title":"Eur J Oper Res"},{"issue":"4","key":"419_CR18","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1287\/ijoc.2018.0806","volume":"30","author":"JF C\u00f4t\u00e9","year":"2018","unstructured":"C\u00f4t\u00e9 JF, Iori M (2018) The meet-in-the-middle principle for cutting and packing problems. INFORMS J Comput 30(4):646\u2013661","journal-title":"INFORMS J Comput"},{"issue":"3","key":"419_CR19","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1287\/opre.2013.1248","volume":"62","author":"JF C\u00f4t\u00e9","year":"2014","unstructured":"C\u00f4t\u00e9 JF, Dell\u2019Amico M, Iori M (2014a) Combinatorial benders\u2019 cuts for the strip packing problem. Oper Res 62(3):643\u2013661","journal-title":"Oper Res"},{"issue":"5","key":"419_CR20","doi-asserted-by":"publisher","first-page":"1126","DOI":"10.1287\/opre.2014.1307","volume":"62","author":"JF C\u00f4t\u00e9","year":"2014","unstructured":"C\u00f4t\u00e9 JF, Gendreau M, Potvin JY (2014b) An exact algorithm for the two-dimensional orthogonal packing problem with unloading constraints. Oper Res 62(5):1126\u20131141","journal-title":"Oper Res"},{"issue":"3","key":"419_CR21","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1287\/ijoc.1070.0250","volume":"20","author":"TG Crainic","year":"2008","unstructured":"Crainic TG, Perboli G, Tadei R (2008) Extreme point-based heuristics for three-dimensional bin packing. Informs J Comput 20(3):368\u2013384","journal-title":"Informs J Comput"},{"issue":"11","key":"419_CR22","doi-asserted-by":"publisher","first-page":"1968","DOI":"10.1016\/j.cor.2010.01.010","volume":"37","author":"A de Almeida","year":"2010","unstructured":"de Almeida A, Figueiredo MB (2010) A particular approach for the three-dimensional packing problem with additional constraints. Comput Oper Res 37(11):1968\u20131976","journal-title":"Comput Oper Res"},{"issue":"3","key":"419_CR23","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1016\/0377-2217(93)E0221-I","volume":"84","author":"D Fayard","year":"1995","unstructured":"Fayard D, Zissimopoulos V (1995) An approximation algorithm for solving unconstrained two-dimensional knapsack problems. Eur J Oper Res 84(3):618\u2013632","journal-title":"Eur J Oper Res"},{"key":"419_CR24","volume-title":"Comput intractability: a guide to the theory of np-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Comput intractability: a guide to the theory of np-completeness. Freeman, San Francisco"},{"key":"419_CR25","doi-asserted-by":"publisher","first-page":"2192","DOI":"10.1016\/j.procs.2014.05.204","volume":"29","author":"RF Gon\u00e7alves","year":"2014","unstructured":"Gon\u00e7alves RF, Queiroz TA (2014) The knapsack problem with three practical constraints. Procedia Comput Sci 29:2192\u20132200","journal-title":"Procedia Comput Sci"},{"issue":"5","key":"419_CR26","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1147\/rd.165.0462","volume":"16","author":"JC Herz","year":"1972","unstructured":"Herz JC (1972) Recursive computational procedure for two-dimensional stock cutting. IBM J Res Dev 16(5):462\u2013469","journal-title":"IBM J Res Dev"},{"issue":"1","key":"419_CR27","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.cor.2010.07.017","volume":"39","author":"L Junqueira","year":"2012","unstructured":"Junqueira L, Morabito R, Yamashita DS (2012) Three-dimensional container loading models with cargo stability and load bearing constraints. Comput Oper Res 39(1):74\u201385","journal-title":"Comput Oper Res"},{"issue":"1","key":"419_CR28","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.cor.2010.10.022","volume":"39","author":"SCH Leung","year":"2012","unstructured":"Leung SCH, Zhang D, Zhou C, Wu T (2012) A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem. Comput Oper Res 39(1):64\u201373","journal-title":"Comput Oper Res"},{"issue":"7","key":"419_CR29","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1057\/palgrave.jors.2601553","volume":"54","author":"L Lins","year":"2003","unstructured":"Lins L, Lins S, Morabito R (2003) An L-approach for packing (l, w)-rectangles into rectangular and L-shaped pieces. J Oper Res Soc 54(7):777\u2013789","journal-title":"J Oper Res Soc"},{"key":"419_CR30","volume-title":"Knapsack problems: algorithms and computer implementations","author":"S Martello","year":"1990","unstructured":"Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, Chichester"},{"issue":"2","key":"419_CR31","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1287\/opre.48.2.256.12386","volume":"48","author":"S Martello","year":"2000","unstructured":"Martello S, Pisinger D, Vigo D (2000) The three-dimensional bin packing problem. Oper Res 48(2):256\u2013267","journal-title":"Oper Res"},{"issue":"3","key":"419_CR32","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1287\/ijoc.15.3.310.16082","volume":"15","author":"S Martello","year":"2003","unstructured":"Martello S, Monaci M, Vigo D (2003) An exact approach to the strip-packing problem. INFORMS J Compu 15(3):310\u2013319","journal-title":"INFORMS J Compu"},{"issue":"2","key":"419_CR33","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s10288-018-0384-4","volume":"17","author":"J Martinovic","year":"2018","unstructured":"Martinovic J, H\u00e4hnel M, Scheithauer G, Dargie W, Fischer A (2018) Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation. 4OR 17(2):173\u2013200","journal-title":"4OR"},{"issue":"1","key":"419_CR34","first-page":"59","volume":"1","author":"R Morabito","year":"1994","unstructured":"Morabito R, Arenales M (1994) An and\/or-graph approach to the container loading problem. Int Trans Oper Res 1(1):59\u201373","journal-title":"Int Trans Oper Res"},{"issue":"2","key":"419_CR35","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.cor.2011.03.011","volume":"39","author":"TA Queiroz","year":"2012","unstructured":"Queiroz TA, Miyazawa FK, Wakabayashi Y, Xavier EC (2012) Algorithms for 3D guillotine cutting problems: unbounded knapsack, cutting stock and strip packing. Comput Oper Res 39(2):200\u2013212","journal-title":"Comput Oper Res"},{"issue":"2","key":"419_CR36","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s10288-014-0274-3","volume":"13","author":"TA Queiroz","year":"2015","unstructured":"Queiroz TA, Miyazawa FK, Wakabayashi Y (2015) On the L-approach for generating unconstrained two-dimensional non-guillotine cutting patterns. 4OR 13(2):199\u2013219","journal-title":"4OR"},{"key":"419_CR37","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.cie.2017.01.015","volume":"105","author":"TA Queiroz","year":"2017","unstructured":"Queiroz TA, Hokama PHDB, Schouery RCS, Miyazawa FK (2017) Two-dimensional disjunctively constrained knapsack problem: heuristic and exact approaches. Comput Ind Eng 105:313\u2013328","journal-title":"Comput Ind Eng"},{"issue":"4","key":"419_CR38","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1057\/jors.1996.57","volume":"47","author":"G Scheithauer","year":"1996","unstructured":"Scheithauer G, Terno J (1996) The G4-heuristic for the pallet loading problem. J Oper Res Soc 47(4):511\u2013522","journal-title":"J Oper Res Soc"},{"key":"419_CR39","unstructured":"Terno J, Lindemann R, Scheithauer G (1987) Zuschnittprobleme and ihre praktische l\u00f6sung. Technical report, Verlag Harry Deutsch, Thun und FrankfurtMain"},{"issue":"16","key":"419_CR40","doi-asserted-by":"publisher","first-page":"12,589","DOI":"10.1016\/j.eswa.2012.05.025","volume":"39","author":"AMD Valle","year":"2012","unstructured":"Valle AMD, Queiroz TA, Miyazawa FK, Xavier EC (2012) Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape. Expert Syst Appl 39(16):12,589\u201312,598","journal-title":"Expert Syst Appl"},{"issue":"3","key":"419_CR41","doi-asserted-by":"publisher","first-page":"1109","DOI":"10.1016\/j.ejor.2005.12.047","volume":"183","author":"G W\u00e4scher","year":"2007","unstructured":"W\u00e4scher G, Hau\u00dfner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183(3):1109\u20131130","journal-title":"Eur J Oper Res"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-019-00419-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10288-019-00419-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-019-00419-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T15:25:29Z","timestamp":1601479529000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10288-019-00419-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,24]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["419"],"URL":"https:\/\/doi.org\/10.1007\/s10288-019-00419-9","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"type":"print","value":"1619-4500"},{"type":"electronic","value":"1614-2411"}],"subject":[],"published":{"date-parts":[[2019,9,24]]},"assertion":[{"value":"18 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"There is no conflict of interest that may concern the authors.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This work does not involve Human Participants and\/or Animals.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Human and animal rights"}}]}}