Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/286813 
Year of Publication: 
2021
Citation: 
[Journal:] Mathematical Methods of Operations Research [ISSN:] 1432-5217 [Volume:] 93 [Issue:] 3 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2021 [Pages:] 521-554
Publisher: 
Springer, Berlin, Heidelberg
Abstract: 
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.
Subjects: 
Combinatorial optimization
Mixed integer programming
Two-dimensional knapsack problem
Maximum diversity problem
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.