8103
eng
reportzib
0
--
2020-12-07
--
The Maximum Diversity Assortment Selection Problem
In this paper, we introduce the Maximum Diversity Assortment Selection Problem (MADASS), which is a generalization of the 2-dimensional Cutting Stock Problem (2CSP). Given a set of rectangles and a rectangular container, the goal of 2CSP 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. In MADASS, we need 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 minimum or average normalized Hamming-Distance of all assortment pairs. The MADASS Problem was used in the 11th AIMMS-MOPTA Competition in 2019. The methods we describe in this article and the 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 2CSP literature.
1438-0064
urn:nbn:de:0297-zib-81039
false
true
Felix Prause
Felix Prause
Kai Hoppmann-Baum
Boris Defourny
Thorsten Koch
ZIB-Report
20-34
eng
uncontrolled
Combinatorial Optimization
eng
uncontrolled
Mixed Integer Programming
eng
uncontrolled
2-dim Cutting Stock Problem
eng
uncontrolled
Maximum Diversity Problem
Operations research and management science
Mixed integer programming
Hoppmann, Kai
Koch, Thorsten
MODAL-GasLab
MODAL-Gesamt
Prause, Felix
Mathematical Algorithmic Intelligence
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
https://opus4.kobv.de/opus4-zib/files/8103/ZIB_Report_20-34.pdf