## The Maximum Diversity Assortment Selection Problem

under review

- 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.

Author: | Felix PrauseORCiD, Kai Hoppmann-BaumORCiD, Boris DefournyORCiD, Thorsten KochORCiD |
---|---|

Document Type: | Article |

Parent Title (English): | Mathematical Methods of Operations Research |

Year of first publication: | 2020 |

Preprint: | urn:nbn:de:0297-zib-81039 |