The maximum diversity assortment selection problem

dc.contributor.authorPrause, Felix
dc.contributor.authorHoppmann-Baum, Kai
dc.contributor.authorDefourny, Boris
dc.contributor.authorKoch, Thorsten
dc.date.accessioned2023-04-05T12:27:41Z
dc.date.available2023-04-05T12:27:41Z
dc.date.issued2021-05-25
dc.date.updated2023-03-24T17:13:18Z
dc.description.abstractIn 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.en
dc.description.sponsorshipBMBF, 05M14ZAM, Forschungscampus Modal - Mathematical Optimization and Data Analysis Laboratories. Antrag auf die erste Hauptphase (Implementierung) des Forschungscampus Modal
dc.description.sponsorshipBMBF, 05M20ZBM, Forschungscampus MODAL - Mathematical Optimization and Data Analysis Laboratories - zweite Förderphase (Stabilisierung)
dc.identifier.eissn1432-5217
dc.identifier.issn1432-2994
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/18452
dc.identifier.urihttps://doi.org/10.14279/depositonce-17261
dc.language.isoen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subject.ddc500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik
dc.subject.othercombinatorial optimizationen
dc.subject.othermixed integer programmingen
dc.subject.othertwo-dimensional knapsack problemen
dc.subject.othermaximum diversity problemen
dc.titleThe maximum diversity assortment selection problemen
dc.typeArticle
dc.type.versionpublishedVersion
dcterms.bibliographicCitation.doi10.1007/s00186-021-00740-2
dcterms.bibliographicCitation.issue3
dcterms.bibliographicCitation.journaltitleMathematical Methods of Operations Research
dcterms.bibliographicCitation.originalpublishernameSpringer Nature
dcterms.bibliographicCitation.originalpublisherplaceHeidelberg
dcterms.bibliographicCitation.pageend554
dcterms.bibliographicCitation.pagestart521
dcterms.bibliographicCitation.volume93
dcterms.rightsHolder.referenceCreative-Commons-Lizenz
tub.accessrights.dnbfree
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::N/A (Not Applicable)
tub.publisher.universityorinstitutionTechnische Universität Berlin

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
s00186-021-00740-2.pdf
Size:
707.14 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.86 KB
Format:
Item-specific license agreed upon to submission
Description:

Collections