{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:24:13Z","timestamp":1740108253332,"version":"3.37.3"},"reference-count":89,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T00:00:00Z","timestamp":1621900800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T00:00:00Z","timestamp":1621900800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["05M14ZAM"],"award-info":[{"award-number":["05M14ZAM"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\"ur Bildung und Forschung","doi-asserted-by":"publisher","award":["05M20ZBM"],"award-info":[{"award-number":["05M20ZBM"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this article, we introduce the Maximum Diversity Assortment Selection Problem (MDASP), which is a generalization of the two-dimensional Knapsack Problem (2D-KP). Given a set of rectangles and a rectangular container, the goal of 2D-KP is to determine a subset of rectangles that can be placed in the container without overlapping, i.e., a feasible assortment, such that a maximum area is covered. MDASP is to determine a set of feasible assortments, each of them covering a certain minimum threshold of the container, such that the diversity among them is maximized. Thereby, diversity is defined as the minimum or average normalized Hamming distance of all assortment pairs. MDASP was the topic of the 11th AIMMS-MOPTA Competition in 2019. The methods described in this article and the resulting computational results won the contest. In the following, we give a definition of the problem, introduce a mathematical model and solution approaches, determine upper bounds on the diversity, and conclude with computational experiments conducted on test instances derived from the 2D-KP literature.<\/jats:p>","DOI":"10.1007\/s00186-021-00740-2","type":"journal-article","created":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T13:03:03Z","timestamp":1621947783000},"page":"521-554","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The maximum diversity assortment selection problem"],"prefix":"10.1007","volume":"93","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9401-3707","authenticated-orcid":false,"given":"Felix","family":"Prause","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9184-8215","authenticated-orcid":false,"given":"Kai","family":"Hoppmann-Baum","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0405-5538","authenticated-orcid":false,"given":"Boris","family":"Defourny","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1967-0077","authenticated-orcid":false,"given":"Thorsten","family":"Koch","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,25]]},"reference":[{"key":"740_CR1","doi-asserted-by":"publisher","unstructured":"Achterberg T (2007) Constraint Integer Programming. Doctoral thesis, Technische Universit\u00e4t Berlin, Fakult\u00e4t II - Mathematik und Naturwissenschaften, Berlin. https:\/\/doi.org\/10.14279\/depositonce-1634","DOI":"10.14279\/depositonce-1634"},{"key":"740_CR2","unstructured":"AdaCore: GNAT Reference Manual (2019). https:\/\/www.adacore.com\/documentation"},{"key":"740_CR3","unstructured":"AIMMS-MOPTA optimization modeling competition. ORMS Today (2019). https:\/\/pubsonline.informs.org\/do\/10.1287\/orms.2019.05.13\/full\/"},{"issue":"4","key":"740_CR4","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1057\/palgrave.jors.2601829","volume":"56","author":"R \u00c1lvarez Vald\u00e9s","year":"2005","unstructured":"\u00c1lvarez Vald\u00e9s R, Parre\u00f1o F, Tamarit JM (2005) A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems. J Oper Res Soc 56(4):414\u2013425. https:\/\/doi.org\/10.1057\/palgrave.jors.2601829","journal-title":"J Oper Res Soc"},{"issue":"3","key":"740_CR5","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1016\/j.ejor.2005.11.068","volume":"183","author":"R \u00c1lvarez Vald\u00e9s","year":"2007","unstructured":"\u00c1lvarez Vald\u00e9s R, Parre\u00f1o F, Tamarit JM (2007) A tabu search algorithm for a two-dimensional non-guillotine cutting problem. Eur J Oper Res 183(3):1167\u20131182. https:\/\/doi.org\/10.1016\/j.ejor.2005.11.068","journal-title":"Eur J Oper Res"},{"issue":"7","key":"740_CR6","doi-asserted-by":"publisher","first-page":"1625","DOI":"10.1080\/002075499191166","volume":"37","author":"AR Babu","year":"1999","unstructured":"Babu AR, Babu NR (1999) Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms. Int J Prod Res 37(7):1625\u20131643. https:\/\/doi.org\/10.1080\/002075499191166","journal-title":"Int J Prod Res"},{"issue":"4","key":"740_CR7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1057\/jors.1985.51","volume":"36","author":"JE Beasley","year":"1985","unstructured":"Beasley JE (1985) Algorithms for unconstrained two-dimensional Guillotine cutting. J Oper Res Soc 36(4):297\u2013306. https:\/\/doi.org\/10.1057\/jors.1985.51","journal-title":"J Oper Res Soc"},{"issue":"1","key":"740_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 (1985) An exact two-dimensional non-guillotine cutting tree search procedure. Oper Res 33(1):49\u201364. https:\/\/doi.org\/10.1287\/opre.33.1.49","journal-title":"Oper Res"},{"issue":"3","key":"740_CR9","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1016\/S0377-2217(03)00139-5","volume":"156","author":"JE Beasley","year":"2004","unstructured":"Beasley JE (2004) A population heuristic for constrained two-dimensional non-guillotine cutting. Eur J Oper Res 156(3):601\u2013627. https:\/\/doi.org\/10.1016\/S0377-2217(03)00139-5","journal-title":"Eur J Oper Res"},{"issue":"6","key":"740_CR10","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1111\/j.1475-3995.2009.00713.x","volume":"16","author":"G Belov","year":"2009","unstructured":"Belov G, Kartak V, Rohling H, Scheithauer G (2009) One-dimensional relaxations and LP bounds for orthogonal packing. Int Trans Oper Res 16(6):745\u2013766. https:\/\/doi.org\/10.1111\/j.1475-3995.2009.00713.x","journal-title":"Int Trans Oper Res"},{"issue":"1","key":"740_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10287-004-0020-y","volume":"2","author":"JF Benders","year":"2005","unstructured":"Benders JF (2005) Partitioning procedures for solving mixed-variables programming problems. Comput Manag Sci 2(1):3\u201319. https:\/\/doi.org\/10.1007\/s10287-004-0020-y","journal-title":"Comput Manag Sci"},{"issue":"3","key":"740_CR12","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1093\/comjnl\/25.3.353","volume":"25","author":"BE Bengtsson","year":"1982","unstructured":"Bengtsson BE (1982) Packing rectangular pieces\u2014a heuristic approach. Comput J 25(3):353\u2013357. https:\/\/doi.org\/10.1093\/comjnl\/25.3.353","journal-title":"Comput J"},{"issue":"5","key":"740_CR13","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1057\/jors.1987.70","volume":"38","author":"JO Berkey","year":"1987","unstructured":"Berkey JO, Wang PY (1987) Two-dimensional finite bin-packing algorithms. J Oper Res Soc 38(5):423\u2013429. https:\/\/doi.org\/10.1057\/jors.1987.70","journal-title":"J Oper Res Soc"},{"issue":"6","key":"740_CR14","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1111\/j.1475-3995.2009.00701.x","volume":"16","author":"A Bortfeldt","year":"2009","unstructured":"Bortfeldt A, Winter T (2009) A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces. Int Trans Oper Res 16(6):685\u2013713. https:\/\/doi.org\/10.1111\/j.1475-3995.2009.00701.x","journal-title":"Int Trans Oper Res"},{"key":"740_CR15","doi-asserted-by":"publisher","unstructured":"Bortfeldt A, Gehring H (2006) New large benchmark instances for the two-dimensional strip packing problem with rectangular pieces. In: Proceedings of the 39th annual Hawaii international conference on system sciences (HICSS\u201906), pp. 30b\u201330b. IEEE, Kauia, HI, USA. https:\/\/doi.org\/10.1109\/HICSS.2006.360. http:\/\/ieeexplore.ieee.org\/document\/1579352\/","DOI":"10.1109\/HICSS.2006.360"},{"issue":"2","key":"740_CR16","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. https:\/\/doi.org\/10.1093\/imaman\/13.2.95","journal-title":"IMA J Manag Math"},{"key":"740_CR17","doi-asserted-by":"publisher","DOI":"10.24425\/119524","author":"A Bouaine","year":"2018","unstructured":"Bouaine A, Lebbar M, Ha MA (2018) Minimization of the wood wastes for an industry of furnishing: a two dimensional cutting stock problem. Manag Prod Eng Rev. https:\/\/doi.org\/10.24425\/119524","journal-title":"Manag Prod Eng Rev"},{"issue":"4","key":"740_CR18","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1287\/opre.1040.0109","volume":"52","author":"EK Burke","year":"2004","unstructured":"Burke EK, Kendall G, Whitwell G (2004) A new placement heuristic for the orthogonal stock-cutting problem. Oper Res 52(4):655\u2013671. https:\/\/doi.org\/10.1287\/opre.1040.0109","journal-title":"Oper Res"},{"issue":"3","key":"740_CR19","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0925-5273(94)00045-X","volume":"36","author":"CH Cheng","year":"1994","unstructured":"Cheng CH, Feiring BR, Cheng TCE (1994) The cutting stock problem\u2014a survey. Int J Prod Econ 36(3):291\u2013305. https:\/\/doi.org\/10.1016\/0925-5273(94)00045-X","journal-title":"Int J Prod Econ"},{"issue":"1","key":"740_CR20","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. https:\/\/doi.org\/10.1287\/opre.25.1.30","journal-title":"Oper Res"},{"issue":"3","key":"740_CR21","doi-asserted-by":"publisher","first-page":"1196","DOI":"10.1016\/j.ejor.2005.12.048","volume":"183","author":"F Clautiaux","year":"2007","unstructured":"Clautiaux F, Carlier J, Moukrim A (2007) A new exact method for the two-dimensional orthogonal packing problem. Eur J Oper Res 183(3):1196\u20131211. https:\/\/doi.org\/10.1016\/j.ejor.2005.12.048","journal-title":"Eur J Oper Res"},{"issue":"3","key":"740_CR22","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, DellAmico M, Iori M (2014) Combinatorial benders cuts for the strip packing problem. Oper Res 62(3):643\u2013661. https:\/\/doi.org\/10.1287\/opre.2013.1248","journal-title":"Oper Res"},{"key":"740_CR23","doi-asserted-by":"publisher","unstructured":"Crainic TG, Perboli G, Tadei R (2012) Recent advances in multi-dimensional packing problems. In: Volosencu C (Eds) New technologies\u2014trends, innovations and research. InTech. https:\/\/doi.org\/10.5772\/33302. http:\/\/www.intechopen.com\/books\/new-technologies-trends-innovations-and-research\/recent-advances-in-multi-dimensional-packing-problems","DOI":"10.5772\/33302"},{"issue":"2","key":"740_CR24","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/j.ejor.2011.11.002","volume":"219","author":"J de Armas","year":"2012","unstructured":"de Armas J, Miranda G, Le\u00f3n C (2012) Improving the efficiency of a best-first bottom-up approach for the Constrained 2d Cutting Problem. Eur J Oper Res 219(2):201\u2013213. https:\/\/doi.org\/10.1016\/j.ejor.2011.11.002","journal-title":"Eur J Oper Res"},{"issue":"1","key":"740_CR25","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/0377-2217(92)90288-K","volume":"56","author":"KA Dowsland","year":"1992","unstructured":"Dowsland KA, Dowsland WB (1992) Packing problems. Eur J Oper Res 56(1):2\u201314. https:\/\/doi.org\/10.1016\/0377-2217(92)90288-K","journal-title":"Eur J Oper Res"},{"issue":"1","key":"740_CR26","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.ejor.2006.01.021","volume":"178","author":"A Duarte","year":"2007","unstructured":"Duarte A, Mart\u00ed R (2007) Tabu search and GRASP for the maximum diversity problem. Eur J Oper Res 178(1):71\u201384. https:\/\/doi.org\/10.1016\/j.ejor.2006.01.021","journal-title":"Eur J Oper Res"},{"issue":"2","key":"740_CR27","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0377-2217(90)90350-K","volume":"44","author":"H Dyckhoff","year":"1990","unstructured":"Dyckhoff H (1990) A typology of cutting and packing problems. Eur J Oper Res 44(2):145\u2013159. https:\/\/doi.org\/10.1016\/0377-2217(90)90350-K","journal-title":"Eur J Oper Res"},{"issue":"4","key":"740_CR28","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1016\/j.cor.2007.12.004","volume":"36","author":"J Egeblad","year":"2009","unstructured":"Egeblad J, Pisinger D (2009) Heuristic approaches for the two- and three-dimensional knapsack packing problem. Comput Oper Res 36(4):1026\u20131049. https:\/\/doi.org\/10.1016\/j.cor.2007.12.004","journal-title":"Comput Oper Res"},{"key":"740_CR29","unstructured":"Fekete SP, Schepers J (2000) On more-dimensional packing III: exact algorithms"},{"issue":"2","key":"740_CR30","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1287\/moor.1030.0079","volume":"29","author":"SP Fekete","year":"2004","unstructured":"Fekete SP, Schepers J (2004) A combinatorial characterization of higher-dimensional orthogonal packing. Math Oper Res 29(2):353\u2013368. https:\/\/doi.org\/10.1287\/moor.1030.0079","journal-title":"Math Oper Res"},{"issue":"3","key":"740_CR31","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1287\/opre.1060.0369","volume":"55","author":"SP Fekete","year":"2007","unstructured":"Fekete SP, Schepers J, van der Veen JC (2007) An exact algorithm for higher-dimensional orthogonal packing. Oper Res 55(3):569\u2013587. https:\/\/doi.org\/10.1287\/opre.1060.0369","journal-title":"Oper Res"},{"issue":"3","key":"740_CR32","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s10589-007-9161-6","volume":"44","author":"M Gallego","year":"2009","unstructured":"Gallego M, Duarte A, Laguna M, Mart\u00ed R (2009) Hybrid heuristics for the maximum diversity problem. Comput Optim Appl 44(3):411\u2013426. https:\/\/doi.org\/10.1007\/s10589-007-9161-6","journal-title":"Comput Optim Appl"},{"key":"740_CR33","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, San Francisco. https:\/\/bohr.wlu.ca\/hfan\/cp412\/references\/ChapterOne.pdf"},{"issue":"4","key":"740_CR34","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF00934810","volume":"10","author":"AM Geoffrion","year":"1972","unstructured":"Geoffrion AM (1972) Generalized Benders decomposition. J Optim Theory Appl 10(4):237\u2013260. https:\/\/doi.org\/10.1007\/BF00934810","journal-title":"J Optim Theory Appl"},{"issue":"4","key":"740_CR35","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0167-6377(96)00025-9","volume":"19","author":"JB Ghosh","year":"1996","unstructured":"Ghosh JB (1996) Computational aspects of the maximum diversity problem. Oper Res Lett 19(4):175\u2013181. https:\/\/doi.org\/10.1016\/0167-6377(96)00025-9","journal-title":"Oper Res Lett"},{"issue":"1","key":"740_CR36","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1287\/opre.13.1.94","volume":"13","author":"PC Gilmore","year":"1965","unstructured":"Gilmore PC, Gomory RE (1965) Multistage cutting stock problems of two and more dimensions. Oper Res 13(1):94\u2013120. https:\/\/doi.org\/10.1287\/opre.13.1.94","journal-title":"Oper Res"},{"key":"740_CR37","unstructured":"Gon\u00e7alves JF, Resende MGC (2006) A hybrid heuristic for the constrained two-dimensional non-guillotine orthogonal cutting problem. http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.73.3368"},{"issue":"3","key":"740_CR38","doi-asserted-by":"publisher","first-page":"1212","DOI":"10.1016\/j.ejor.2005.11.062","volume":"183","author":"JF Gon\u00e7alves","year":"2007","unstructured":"Gon\u00e7alves JF (2007) A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem. Eur J Oper Res 183(3):1212\u20131229. https:\/\/doi.org\/10.1016\/j.ejor.2005.11.062","journal-title":"Eur J Oper Res"},{"key":"740_CR39","unstructured":"Gurobi optimization, LLC: Gurobi Optimizer Reference Manual (2019). http:\/\/www.gurobi.com"},{"issue":"1","key":"740_CR40","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0377-2217(93)E0278-6","volume":"83","author":"E Hadjiconstantinou","year":"1995","unstructured":"Hadjiconstantinou E, Christofides N (1995) An exact algorithm for general, orthogonal, two-dimensional knapsack problems. Eur J Oper Res 83(1):39\u201356. https:\/\/doi.org\/10.1016\/0377-2217(93)E0278-6","journal-title":"Eur J Oper Res"},{"issue":"3","key":"740_CR41","doi-asserted-by":"publisher","first-page":"1150","DOI":"10.1016\/j.ejor.2005.11.061","volume":"183","author":"E Hadjiconstantinou","year":"2007","unstructured":"Hadjiconstantinou E, Iori M (2007) A hybrid genetic algorithm for the two-dimensional single large object placement problem. Eur J Oper Res 183(3):1150\u20131166. https:\/\/doi.org\/10.1016\/j.ejor.2005.11.061","journal-title":"Eur J Oper Res"},{"issue":"12","key":"740_CR42","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1287\/mnsc.17.12.B793","volume":"17","author":"RW Haessler","year":"1971","unstructured":"Haessler RW (1971) A heuristic programming solution to a nonlinear cutting stock problem. Manag Sci 17(12):793. https:\/\/doi.org\/10.1287\/mnsc.17.12.B793","journal-title":"Manag Sci"},{"issue":"6","key":"740_CR43","doi-asserted-by":"publisher","first-page":"1100","DOI":"10.1287\/opre.16.6.1100","volume":"16","author":"SG Hahn","year":"1968","unstructured":"Hahn SG (1968) On the optimal cutting of defective sheets. Oper Res 16(6):1100\u20131114. https:\/\/doi.org\/10.1287\/opre.16.6.1100","journal-title":"Oper Res"},{"issue":"2","key":"740_CR44","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1002\/j.1538-7305.1950.tb00463.x","volume":"29","author":"RW Hamming","year":"1950","unstructured":"Hamming RW (1950) Error detecting and error correcting codes. Bell Syst Tech J 29(2):147\u2013160. https:\/\/doi.org\/10.1002\/j.1538-7305.1950.tb00463.x","journal-title":"Bell Syst Tech J"},{"issue":"6","key":"740_CR45","doi-asserted-by":"publisher","first-page":"3287","DOI":"10.24200\/sci.2017.4401","volume":"24","author":"MA Hatefi","year":"2017","unstructured":"Hatefi MA (2017) Developing column generation approach to solve the rectangular two-dimensional single knapsack problem. Sci Iran 24(6):3287\u20133296. https:\/\/doi.org\/10.24200\/sci.2017.4401","journal-title":"Sci Iran"},{"issue":"7","key":"740_CR46","doi-asserted-by":"publisher","first-page":"1355","DOI":"10.1016\/j.cor.2011.08.005","volume":"39","author":"K He","year":"2012","unstructured":"He K, Huang W, Jin Y (2012) An efficient deterministic heuristic for two-dimensional rectangular packing. Comput Oper Res 39(7):1355\u20131363. https:\/\/doi.org\/10.1016\/j.cor.2011.08.005","journal-title":"Comput Oper Res"},{"issue":"1","key":"740_CR47","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1023\/A:1008743711658","volume":"18","author":"M Hifi","year":"2001","unstructured":"Hifi M (2001) Exact algorithms for large-scale unconstrained two and three staged cutting problems. Comput Optim Appl 18(1):63\u201388. https:\/\/doi.org\/10.1023\/A:1008743711658","journal-title":"Comput Optim Appl"},{"issue":"3","key":"740_CR48","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1057\/palgrave.jors.2600364","volume":"48","author":"M Hifi","year":"1997","unstructured":"Hifi M, Zissimopoulos V (1997) Constrained two-dimensional cutting: an improvement of Christofides and Whitlocks exact algorithm. J Oper Res Soc 48(3):324\u2013331. https:\/\/doi.org\/10.1057\/palgrave.jors.2600364","journal-title":"J Oper Res Soc"},{"issue":"1","key":"740_CR49","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/0377-2217(80)90068-5","volume":"5","author":"AI Hinxman","year":"1980","unstructured":"Hinxman AI (1980) The trim-loss and assortment problems: a survey. Eur J Oper Res 5(1):8\u201318. https:\/\/doi.org\/10.1016\/0377-2217(80)90068-5","journal-title":"Eur J Oper Res"},{"key":"740_CR50","unstructured":"Hopper E (2000) Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods. Ph.D. thesis, University of Wales, Cardiff. http:\/\/vmk.ugatu.ac.ru\/c%26p\/article\/hopper\/PhDisser\/part1.pdf"},{"issue":"1","key":"740_CR51","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/S0377-2217(99)00357-4","volume":"128","author":"E Hopper","year":"2001","unstructured":"Hopper E, Turton BCH (2001) An empirical investigation of meta-heuristic and heuristic algorithms for a 2d packing problem. Eur J Oper Res 128(1):34\u201357. https:\/\/doi.org\/10.1016\/S0377-2217(99)00357-4","journal-title":"Eur J Oper Res"},{"issue":"10","key":"740_CR52","doi-asserted-by":"publisher","first-page":"1356","DOI":"10.1016\/j.simpat.2007.09.004","volume":"15","author":"W Huang","year":"2007","unstructured":"Huang W, Chen D (2007) An efficient heuristic algorithm for rectangle-packing problem. Simul Model Pract Theory 15(10):1356\u20131365. https:\/\/doi.org\/10.1016\/j.simpat.2007.09.004","journal-title":"Simul Model Pract Theory"},{"key":"740_CR53","unstructured":"Imahori S (2019) Cutting and Packing. Accessed 2019-11-13. http:\/\/www-or.amp.i.kyoto-u.ac.jp\/~imahori\/packing\/index.html"},{"key":"740_CR54","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.06.050","author":"M Iori","year":"2020","unstructured":"Iori M, de Lima VL, Martello S, Miyazawa FK, Monaci M (2020) Exact solution techniques for two-dimensional cutting and packing. Eur J Oper Res. https:\/\/doi.org\/10.1016\/j.ejor.2020.06.050","journal-title":"Eur J Oper Res"},{"issue":"1","key":"740_CR55","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0377-2217(94)00166-9","volume":"88","author":"S Jakobs","year":"1996","unstructured":"Jakobs S (1996) On genetic algorithms for the packing of polygons. Eur J Oper Res 88(1):165\u2013181","journal-title":"Eur J Oper Res"},{"issue":"4","key":"740_CR56","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1287\/mnsc.6.4.366","volume":"6","author":"LV Kantorovich","year":"1960","unstructured":"Kantorovich LV (1960) Mathematical methods of organizing and planning production. Manag Sci 6(4):366\u2013422. https:\/\/doi.org\/10.1287\/mnsc.6.4.366","journal-title":"Manag Sci"},{"key":"740_CR57","doi-asserted-by":"publisher","unstructured":"K\u00f6k AG, Fisher ML, Vaidyanathan R (2015) Assortment planning: Review of literature and industry practice. In: Retail supply chain management, pp. 175\u2013236. Springer. https:\/\/doi.org\/10.1007\/978-1-4899-7562-1_8","DOI":"10.1007\/978-1-4899-7562-1_8"},{"issue":"6","key":"740_CR58","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1111\/j.1540-5915.1993.tb00509.x","volume":"24","author":"CC Kuo","year":"1993","unstructured":"Kuo CC, Glover F, Dhir KS (1993) Analyzing and modeling the maximum diversity problem by zero-one programming. Decis Sci 24(6):1171\u20131185. https:\/\/doi.org\/10.1111\/j.1540-5915.1993.tb00509.x","journal-title":"Decis Sci"},{"issue":"1","key":"740_CR59","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0360-8352(96)00205-7","volume":"32","author":"KK Lai","year":"1997","unstructured":"Lai KK, Chan JWM (1997) Developing a simulated annealing algorithm for the cutting stock problem. Comput Ind Eng 32(1):115\u2013127. https:\/\/doi.org\/10.1016\/S0360-8352(96)00205-7","journal-title":"Comput Ind Eng"},{"issue":"3","key":"740_CR60","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1016\/S0377-2217(02)00218-7","volume":"145","author":"TW Leung","year":"2003","unstructured":"Leung TW, Chan CK, Troutt MD (2003) Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem. Eur J Oper Res 145(3):530\u2013542. https:\/\/doi.org\/10.1016\/S0377-2217(02)00218-7","journal-title":"Eur J Oper Res"},{"issue":"1","key":"740_CR61","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. https:\/\/doi.org\/10.1016\/j.cor.2010.10.022","journal-title":"Comput Oper Res"},{"issue":"4","key":"740_CR62","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1287\/ijoc.11.4.345","volume":"11","author":"A Lodi","year":"1999","unstructured":"Lodi A, Martello S, Vigo D (1999) Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS J Comput 11(4):345\u2013357. https:\/\/doi.org\/10.1287\/ijoc.11.4.345","journal-title":"INFORMS J Comput"},{"issue":"1","key":"740_CR63","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.ejor.2011.04.018","volume":"214","author":"M Lozano","year":"2011","unstructured":"Lozano M, Molina D, Garc\u00eda-Mart\u00ednez C (2011) Iterated greedy for the maximum diversity problem. Eur J Oper Res 214(1):31\u201338. https:\/\/doi.org\/10.1016\/j.ejor.2011.04.018","journal-title":"Eur J Oper Res"},{"issue":"3","key":"740_CR64","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1287\/mnsc.44.3.388","volume":"44","author":"S Martello","year":"1998","unstructured":"Martello S, Vigo D (1998) Exact solution of the two-dimensional finite bin packing problem. Manag Sci 44(3):388\u2013399. https:\/\/doi.org\/10.1287\/mnsc.44.3.388","journal-title":"Manag Sci"},{"issue":"1","key":"740_CR65","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.ejor.2008.12.023","volume":"200","author":"R Mart\u00ed","year":"2010","unstructured":"Mart\u00ed R, Gallego M, Duarte A (2010) A branch and bound algorithm for the maximum diversity problem. Eur J Oper Res 200(1):36\u201344. https:\/\/doi.org\/10.1016\/j.ejor.2008.12.023","journal-title":"Eur J Oper Res"},{"issue":"4","key":"740_CR66","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/s10732-011-9172-4","volume":"19","author":"R Mart\u00ef","year":"2013","unstructured":"Mart\u00ef R, Gallego M, Duarte A, Pardo EG (2013) Heuristics and metaheuristics for the maximum diversity problem. J Heurist 19(4):591\u2013615. https:\/\/doi.org\/10.1007\/s10732-011-9172-4","journal-title":"J Heurist"},{"issue":"1\u20134","key":"740_CR67","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/s00170-015-7107-1","volume":"81","author":"SA MirHassani","year":"2015","unstructured":"MirHassani SA, Jalaeian Bashirzadeh A (2015) A GRASP meta-heuristic for two-dimensional irregular cutting stock problem. Int J Adv Manuf Technol 81(1\u20134):455\u2013464. https:\/\/doi.org\/10.1007\/s00170-015-7107-1","journal-title":"Int J Adv Manuf Technol"},{"key":"740_CR68","doi-asserted-by":"publisher","unstructured":"Murata H, Fujiyoshi K, Nakatake S, Kajitani Y (2003) Rectangle-packing-based module placement. In: The best of ICCAD. Springer, pp 535\u2013548.https:\/\/doi.org\/10.1007\/978-1-4615-0292-0_42","DOI":"10.1007\/978-1-4615-0292-0_42"},{"issue":"1","key":"740_CR69","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s001860000066","volume":"52","author":"M Padberg","year":"2000","unstructured":"Padberg M (2000) Packing small boxes into a big box. Math Methods Oper Res 52(1):1\u201321. https:\/\/doi.org\/10.1007\/s001860000066","journal-title":"Math Methods Oper Res"},{"key":"740_CR70","doi-asserted-by":"publisher","unstructured":"Perboli G, Crainic TG, Tadei R (2011) An efficient metaheuristic for multi-dimensional multi-container packing. In: 2011 ieee international conference on automation science and engineering, pp. 563\u2013568. IEEE, Trieste, Italy. https:\/\/doi.org\/10.1109\/CASE.2011.6042476. http:\/\/ieeexplore.ieee.org\/document\/6042476\/","DOI":"10.1109\/CASE.2011.6042476"},{"key":"740_CR71","unstructured":"Pinto E, Oliveira JF (2005) Algorithm based on graphs for the non-guillotinable two-dimensional packing problem. In: Second ESICUP meeting, Southampton"},{"issue":"3","key":"740_CR72","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1287\/ijoc.1060.0192","volume":"19","author":"D Pisinger","year":"2007","unstructured":"Pisinger D (2007) Denser packings obtained in $$O$$($$n$$ log log $$n$$) time. INFORMS J Comput 19(3):395\u2013405. https:\/\/doi.org\/10.1287\/ijoc.1060.0192","journal-title":"INFORMS J Comput"},{"key":"740_CR73","unstructured":"Problem description for the 11th AIMMS-MOPTA Competition (2019). https:\/\/coral.ise.lehigh.edu\/~mopta2019\/\/mopta2019\/AIMMS_MOPTA_case_2019.pdf"},{"key":"740_CR74","unstructured":"Python Software Foundation: Python 3.6 documentation (2020). https:\/\/docs.python.org\/3.6\/"},{"issue":"2","key":"740_CR75","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1287\/opre.42.2.299","volume":"42","author":"SS Ravi","year":"1994","unstructured":"Ravi SS, Rosenkrantz DJ, Tayi GK (1994) Heuristic and special case algorithms for dispersion problems. Oper Res 42(2):299\u2013310. https:\/\/doi.org\/10.1287\/opre.42.2.299","journal-title":"Oper Res"},{"issue":"3","key":"740_CR76","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/j.cor.2008.05.011","volume":"37","author":"MGC Resende","year":"2010","unstructured":"Resende MGC, Mart\u00ef R, Gallego M, Duarte A (2010) GRASP and path relinking for the max-min diversity problem. Comput Oper Res 37(3):498\u2013508. https:\/\/doi.org\/10.1016\/j.cor.2008.05.011","journal-title":"Comput Oper Res"},{"key":"740_CR77","doi-asserted-by":"crossref","unstructured":"Sandoya F, Mart\u00ednez-Gavara A, Aceves R, Duarte A, Mart\u00ed R (2018) Diversity and equity models. In: R.\u00a0Mart\u00ed, P.M. Pardalos, M.G.C. Resende (eds.) Handbook of heuristics, pp. 979\u2013998. Springer International Publishing. https:\/\/www.springer.com\/gp\/book\/9783319071237","DOI":"10.1007\/978-3-319-07124-4_61"},{"key":"740_CR78","doi-asserted-by":"publisher","unstructured":"Santos LF, Ribeiro MH, Plastino A, Martins SL (2005) A Hybrid GRASP with data mining for the maximum diversity problem. In: Hutchison D, Kanade T, Kittler J, Kleinberg JM, Mattern K, Mitchell JC, Naor M, Nierstrasz O, Pandu\u00a0Rangan C, Steffen B, Sudan M, Terzopoulos D, Tygar D, Vardi MY, Weikum G, Blesa MJ, Blum C, Roli A, Sampels M (Eds) Hybrid metaheuristics, vol. 3636, pp. 116\u2013127. Springer Berlin Heidelberg, Berlin, Heidelberg. https:\/\/doi.org\/10.1007\/11546245_11. http:\/\/link.springer.com\/10.1007\/11546245_11","DOI":"10.1007\/11546245_11"},{"issue":"2","key":"740_CR79","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1080\/0305215X.2017.1315571","volume":"50","author":"K Shiangjen","year":"2018","unstructured":"Shiangjen K, Chaijaruwanich J, Srisujjalertwaja W, Unachak P, Somhom S (2018) An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem. Eng Optim 50(2):347\u2013365. https:\/\/doi.org\/10.1080\/0305215X.2017.1315571","journal-title":"Eng Optim"},{"key":"740_CR80","doi-asserted-by":"publisher","unstructured":"Silva GC, Ochi LS, Martins SL (2004) Experimental comparison of greedy randomized adaptive search procedures for the maximum diversity problem. In: Kanade T, Kittler J, Kleinberg JM, Mattern F, Mitchell JC, Nierstrasz O, Pandu\u00a0Rangan C, Steffen B, Sudan M, Terzopoulos D, Tygar D, Vardi MY, Weikum G, Ribeiro CC, Martins SL (Eds.) Experimental and efficient algorithms, vol. 3059, pp 498\u2013512. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-3-540-24838-5_37","DOI":"10.1007\/978-3-540-24838-5_37"},{"issue":"4","key":"740_CR81","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s10732-007-9010-x","volume":"13","author":"GC Silva","year":"2007","unstructured":"Silva GC, de Andrade MRQ, Ochi LS, Martins SL, Plastino A (2007) New heuristics for the maximum diversity problem. J Heuristics 13(4):315\u2013336. https:\/\/doi.org\/10.1007\/s10732-007-9010-x","journal-title":"J Heuristics"},{"key":"740_CR82","doi-asserted-by":"publisher","unstructured":"Wang S (2017) Solving rectangle packing problem based on heuristic dynamic decomposition algorithm. DEStech Transactions on Engineering and Technology Research (eeta). https:\/\/doi.org\/10.12783\/dtetr\/eeta2017\/7728","DOI":"10.12783\/dtetr\/eeta2017\/7728"},{"issue":"3","key":"740_CR83","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1287\/opre.31.3.573","volume":"31","author":"PY Wang","year":"1983","unstructured":"Wang PY (1983) Two algorithms for constrained two-dimensional cutting stock problems. Oper Res 31(3):573\u2013586. https:\/\/doi.org\/10.1287\/opre.31.3.573","journal-title":"Oper Res"},{"issue":"2","key":"740_CR84","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/S0377-2217(00)00263-0","volume":"134","author":"PY Wang","year":"2001","unstructured":"Wang PY, Valenzela CL (2001) Data set generation for rectangular placement problems. Eur J Oper Res 134(2):378\u2013391. https:\/\/doi.org\/10.1016\/S0377-2217(00)00263-0","journal-title":"Eur J Oper Res"},{"issue":"3","key":"740_CR85","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. https:\/\/doi.org\/10.1016\/j.ejor.2005.12.047","journal-title":"Eur J Oper Res"},{"issue":"5","key":"740_CR86","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1016\/j.cor.2008.03.004","volume":"36","author":"L Wei","year":"2009","unstructured":"Wei L, Zhang D, Chen Q (2009) A least wasted first heuristic algorithm for the rectangular packing problem. Comput Oper Res 36(5):1608\u20131614. https:\/\/doi.org\/10.1016\/j.cor.2008.03.004","journal-title":"Comput Oper Res"},{"key":"740_CR87","unstructured":"Wei L, Wenbin Z (2019) Skyline heuristic for the 2d rectangular packing and strip packing problems. Accessed 2019-11-13. https:\/\/www.computational-logistics.org\/orlib\/topic\/2D%20Strip%20Packing\/index.html#data"},{"key":"740_CR88","doi-asserted-by":"publisher","unstructured":"Wu YL, Chan CK (2005) On improved least flexibility first heuristics superior for packing and stock cutting problems. In: Hutchison D, Kanade T, Kittler J, Kleinberg JM, Mattern F, Mitchell JC, Naor M, Nierstrasz O, Pandu\u00a0Rangan C, Steffen B, Sudan M, Terzopoulos D, Tygar D, Vardi MY, Weikum G, Lupanov OB, Kasim-Zade OM, Chaskin AV, Steinh\u00f6fel K (Eds) Stochastic algorithms: foundations and applications, vol. 3777, pp 70\u201381. Springer, Berlin. https:\/\/doi.org\/10.1007\/11571155_8","DOI":"10.1007\/11571155_8"},{"issue":"2","key":"740_CR89","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/S0377-2217(02)00129-7","volume":"141","author":"YL Wu","year":"2002","unstructured":"Wu YL, Huang W, Lau SC, Wong CK, Young GH (2002) An effective quasi-human based heuristic for solving the rectangle packing problem. Eur J Oper Res 141(2):341\u2013358. https:\/\/doi.org\/10.1016\/S0377-2217(02)00129-7","journal-title":"Eur J Oper Res"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-021-00740-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-021-00740-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-021-00740-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T11:15:35Z","timestamp":1625570135000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-021-00740-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,25]]},"references-count":89,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["740"],"URL":"https:\/\/doi.org\/10.1007\/s00186-021-00740-2","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"type":"print","value":"1432-2994"},{"type":"electronic","value":"1432-5217"}],"subject":[],"published":{"date-parts":[[2021,5,25]]},"assertion":[{"value":"24 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}