{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T04:25:50Z","timestamp":1784262350701,"version":"3.55.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,7,12]],"date-time":"2022-07-12T00:00:00Z","timestamp":1657584000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,12]],"date-time":"2022-07-12T00:00:00Z","timestamp":1657584000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We advance the state of the art in Mixed-Integer Linear Programming formulations for Guillotine 2D Cutting Problems by (i) adapting a previously-known reduction to our preprocessing phase (plate-size normalization) and by (ii) enhancing a previous formulation (PP-G2KP from Furini et alli) by cutting down its size and symmetries. Our focus is the Guillotine 2D Knapsack Problem with orthogonal and unrestricted cuts, constrained demand, unlimited stages, and no rotation \u2013 however, the formulation may be adapted to many related problems. The code is available. Concerning the set of 59 instances used to benchmark the original formulation, the enhanced formulation takes about 4 hours to solve all instances while the original formulation takes 12 hours to solve 53 of them (the other six runs hit a three-hour time limit each). We integrate, to both formulations, a pricing framework proposed for the original formulation; the enhanced formulation keeps a significant advantage in this situation. Finally, in a recently proposed set of 80 harder instances, the enhanced formulation (with and without the pricing framework) found: 22 optimal solutions (5 already known, 17 new); better lower bounds for 25 instances; better upper bounds for 58 instances.<\/jats:p>","DOI":"10.1007\/s12532-022-00222-4","type":"journal-article","created":{"date-parts":[[2022,7,12]],"date-time":"2022-07-12T20:11:51Z","timestamp":1657656711000},"page":"673-697","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Enhanced formulation for the Guillotine 2D Cutting Knapsack Problem"],"prefix":"10.1007","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3879-2691","authenticated-orcid":false,"given":"Henrique","family":"Becker","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1136-5032","authenticated-orcid":false,"given":"Olinto","family":"Ara\u00fajo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9598-5732","authenticated-orcid":false,"given":"Luciana S.","family":"Buriol","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,7,12]]},"reference":[{"issue":"2","key":"222_CR1","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, J.M.: A branch and bound algorithm for the strip packing problem. OR Spectr. 31(2), 431\u2013459 (2009). https:\/\/doi.org\/10.1007\/s00291-008-0128-5","journal-title":"OR Spectr."},{"issue":"4","key":"222_CR2","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1057\/jors.1985.51.","volume":"36","author":"JE Beasley","year":"1985","unstructured":"Beasley, J.E.: Algorithms for unconstrained Two-dimensional guillotine cutting. J. Oper. Res. Soc. 36(4), 297\u2013306 (1985). https:\/\/doi.org\/10.1057\/jors.1985.51.","journal-title":"J. Oper. Res. Soc."},{"key":"222_CR3","doi-asserted-by":"publisher","unstructured":"Becker, H.: Guillotinemodels.jl (2022). https:\/\/doi.org\/10.5281\/zenodo.6486737. https:\/\/github.com\/henriquebecker91\/GuillotineModels.jl\/tree\/MPC_EXPERIMENTS","DOI":"10.5281\/zenodo.6486737"},{"key":"222_CR4","unstructured":"Belov, G.: Problems, models and algorithms in one- and two-dimensional cutting. Fakult\u00e4t Mathematik und Naturwissenschaften der Technischen Universit\u00e4t Dresden (2003). https:\/\/d-nb.info\/970782489\/"},{"key":"222_CR5","doi-asserted-by":"publisher","unstructured":"Ben Messaoud, S., Chu, C., Espinouse, M.L.: Characterization and modelling of guillotine constraints. Eur. J. Oper. Res. 191(1), 112\u2013126 (2008). https:\/\/doi.org\/10.1016\/j.ejor.2007.08.029","DOI":"10.1016\/j.ejor.2007.08.029"},{"key":"222_CR6","doi-asserted-by":"publisher","unstructured":"Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing. SIAM Rev. 59(1), 65\u201398 (2017). https:\/\/doi.org\/10.1137\/141000671","DOI":"10.1137\/141000671"},{"issue":"2","key":"222_CR7","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1093\/imaman\/13.2.95","volume":"13","author":"MA Boschetti","year":"2002","unstructured":"Boschetti, M.A., Mingozzi, A., Hadjiconstantinou, E.: New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem. IMA J. Manag. Math. 13(2), 95\u2013119 (2002). https:\/\/doi.org\/10.1093\/imaman\/13.2.95","journal-title":"IMA J. Manag. Math."},{"issue":"1","key":"222_CR8","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.: An algorithm for Two-Dimensional cutting problems. Oper. Res. 25(1), 30\u201344 (1977). https:\/\/doi.org\/10.1287\/opre.25.1.30","journal-title":"Oper. Res."},{"issue":"3","key":"222_CR9","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/s13675-019-00113-9","volume":"7","author":"F Clautiaux","year":"2019","unstructured":"Clautiaux, F., Sadykov, R., Vanderbeck, F., Viaud, Q.: Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers. EURO J. Comput. Optim. 7(3), 265\u2013297 (2019). https:\/\/doi.org\/10.1007\/s13675-019-00113-9","journal-title":"EURO J. Comput. Optim."},{"issue":"4","key":"222_CR10","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, J.F., Iori, M.: The meet-in-the-middle principle for cutting and packing problems. INFORMS J. Comput. 30(4), 646\u2013661 (2018). https:\/\/doi.org\/10.1287\/ijoc.2018.0806","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"222_CR11","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1287\/ijoc.2018.0880","volume":"32","author":"M Delorme","year":"2019","unstructured":"Delorme, M., Iori, M.: Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS J. Comput. 32(1), 101\u2013119 (2019). https:\/\/doi.org\/10.1287\/ijoc.2018.0880","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"222_CR12","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.cor.2010.12.018","volume":"39","author":"M Dolatabadi","year":"2012","unstructured":"Dolatabadi, M., Lodi, A., Monaci, M.: Exact algorithms for the two-dimensional guillotine knapsack. Computers Oper. Res. 39(1), 48\u201353 (2012). https:\/\/doi.org\/10.1016\/j.cor.2010.12.018","journal-title":"Computers Oper. Res."},{"issue":"2","key":"222_CR13","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1137\/15M1020575","volume":"59","author":"I Dunning","year":"2017","unstructured":"Dunning, I., Huchette, J., Lubin, M.: Jump: a modeling language for mathematical optimization. SIAM Rev. 59(2), 295\u2013320 (2017). https:\/\/doi.org\/10.1137\/15M1020575","journal-title":"SIAM Rev."},{"issue":"4","key":"222_CR14","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1287\/ijoc.2016.0710","volume":"28","author":"F Furini","year":"2016","unstructured":"Furini, F., Malaguti, E., Thomopulos, D.: Modeling Two-Dimensional guillotine cutting problems via integer programming. INFORMS J. Comput. 28(4), 736\u2013751 (2016). https:\/\/doi.org\/10.1287\/ijoc.2016.0710","journal-title":"INFORMS J. Comput."},{"key":"222_CR15","unstructured":"Gurobi\u00a0Optimization, L.: Gurobi optimizer reference manual (2020). http:\/\/www.gurobi.com"},{"issue":"5","key":"222_CR16","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1147\/rd.165.0462","volume":"16","author":"JC Herz","year":"1972","unstructured":"Herz, J.C.: Recursive computational procedure for two-dimensional stock cutting. IBM J. Res. Dev. 16(5), 462\u2013469 (1972). https:\/\/doi.org\/10.1147\/rd.165.0462","journal-title":"IBM J. Res. Dev."},{"key":"222_CR17","doi-asserted-by":"publisher","unstructured":"Iori, M., de\u00a0Lima, V.L., Martello, S., Miyazawa, F.K., Monaci, M.: Exact solution techniques for Two-dimensional cutting and packing. Eur. J. Oper. Res. p. S0377221720306111 (2020). https:\/\/doi.org\/10.1016\/j.ejor.2020.06.050. http:\/\/arxiv.org\/abs\/2004.12619. ArXiv: 2004.12619","DOI":"10.1016\/j.ejor.2020.06.050"},{"issue":"2","key":"222_CR18","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s10107-002-0319-9","volume":"94","author":"A Lodi","year":"2003","unstructured":"Lodi, A., Monaci, M.: Integer linear programming models for 2-staged two-dimensional Knapsack problems. Math. Program. 94(2), 257\u2013278 (2003). https:\/\/doi.org\/10.1007\/s10107-002-0319-9","journal-title":"Math. Program."},{"issue":"2","key":"222_CR19","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1111\/itor.12703","volume":"27","author":"M Martin","year":"2020","unstructured":"Martin, M., Birgin, E.G., Lobato, R.D., Morabito, R., Munari, P.: Models for the two-dimensional rectangular single large placement problem with guillotine cuts and constrained pattern. Int. Transactions Oper. Res. 27(2), 767\u2013793 (2020). https:\/\/doi.org\/10.1111\/itor.12703","journal-title":"Int. Transactions Oper. Res."},{"key":"222_CR20","doi-asserted-by":"publisher","unstructured":"Martin, M., Morabito, R., Munari, P.: A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem. Computers Oper. Res. 115 (2020). https:\/\/doi.org\/10.1016\/j.cor.2019.104851. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S030505481930293X","DOI":"10.1016\/j.cor.2019.104851"},{"key":"222_CR21","doi-asserted-by":"publisher","DOI":"10.1080\/01605682.2020.1813640","author":"M Martin","year":"2020","unstructured":"Martin, M., Morabito, R., Munari, P.: A top-down cutting approach for modeling the constrained two- and three-dimensional guillotine cutting problems. J. Oper. Res. Soc. (2020). https:\/\/doi.org\/10.1080\/01605682.2020.1813640","journal-title":"J. Oper. Res. Soc."},{"issue":"3","key":"222_CR22","doi-asserted-by":"publisher","first-page":"1405","DOI":"10.1016\/j.ejor.2005.11.066","volume":"183","author":"R Morabito","year":"2007","unstructured":"Morabito, R., Belluzzo, L.: Optimising the cutting of wood fibre plates in the hardboard industry. Eur. J. Oper. Res. 183(3), 1405\u20131420 (2007). https:\/\/doi.org\/10.1016\/j.ejor.2005.11.066","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"222_CR23","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/j.ejor.2020.05.016","volume":"287","author":"F Parre\u00f1o","year":"2020","unstructured":"Parre\u00f1o, F., Alonso, M.T., Alvarez-Valdes, R.: Solving a large cutting problem in the glass manufacturing industry. Eur. J. Oper. Res. 287(1), 378\u2013388 (2020). https:\/\/doi.org\/10.1016\/j.ejor.2020.05.016","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"222_CR24","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/ijoc.1060.0181","volume":"19","author":"D Pisinger","year":"2007","unstructured":"Pisinger, D., Sigurd, M.: Using decomposition techniques and constraint programming for solving the Two-Dimensional bin-packing problem. INFORMS J. Comput. 19(1), 36\u201351 (2007). https:\/\/doi.org\/10.1287\/ijoc.1060.0181","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"222_CR25","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1111\/itor.12687","volume":"27","author":"M Russo","year":"2020","unstructured":"Russo, M., Boccia, M., Sforza, A., Sterle, C.: Constrained two-dimensional guillotine cutting problem: upper-bound review and categorization. Int. Transactions Oper. Res. 27(2), 794\u2013834 (2020). https:\/\/doi.org\/10.1111\/itor.12687","journal-title":"Int. Transactions Oper. Res."},{"issue":"4","key":"222_CR26","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.: The g4-heuristic for the pallet loading problem. J. Oper. Res. Soc. 47(4), 511\u2013522 (1996). https:\/\/doi.org\/10.1057\/jors.1996.57","journal-title":"J. Oper. Res. Soc."},{"issue":"2","key":"222_CR27","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1016\/j.ejor.2009.05.047","volume":"202","author":"X Song","year":"2010","unstructured":"Song, X., Chu, C.B., Lewis, R., Nie, Y.Y., Thompson, J.: A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting. Eur. J. Oper. Res. 202(2), 368\u2013378 (2010). https:\/\/doi.org\/10.1016\/j.ejor.2009.05.047","journal-title":"Eur. J. Oper. Res."},{"key":"222_CR28","unstructured":"Terno, J., Lindemann, R., Scheithauer, G.: Zuschnittprobleme und ihre praktische l\u00f6sung. Verlag Harri Deutsch, Thun und Frankfurt\/Main (1987)"},{"key":"222_CR29","unstructured":"Thomopulos, D.: Models and solutions of resource allocation problems based on integer linear and nonlinear programming. Ph.D. thesis, University of Bologna (2016). http:\/\/amsdottorato.unibo.it\/7399\/"},{"issue":"1","key":"222_CR30","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.ejor.2018.06.016","volume":"272","author":"AS Velasco","year":"2019","unstructured":"Velasco, A.S., Uchoa, E.: Improved state space relaxation for constrained two-dimensional guillotine cutting problems. Eur. J. Oper. Res. 272(1), 106\u2013120 (2019). https:\/\/doi.org\/10.1016\/j.ejor.2018.06.016","journal-title":"Eur. J. Oper. Res."},{"issue":"21","key":"222_CR31","doi-asserted-by":"publisher","first-page":"6189","DOI":"10.1080\/00207540601011543","volume":"46","author":"HH Yanasse","year":"2008","unstructured":"Yanasse, H.H., Morabito, R.: A note on linear models for two-group and three-group two-dimensional guillotine cutting problems. Int. J. Prod. Res. 46(21), 6189\u20136206 (2008). https:\/\/doi.org\/10.1080\/00207540601011543","journal-title":"Int. J. Prod. Res."}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-022-00222-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-022-00222-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-022-00222-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T14:31:32Z","timestamp":1666362692000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-022-00222-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,12]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["222"],"URL":"https:\/\/doi.org\/10.1007\/s12532-022-00222-4","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,12]]},"assertion":[{"value":"10 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The code, in the specific version used, is available at\u00a0[]. The code is in public domain (by means of the Unlicense template, see  for details).","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}