## The Maximum Diversity Assortment Selection Problem

Please always quote using this URN: urn:nbn:de:0297-zib-81039

- 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: | ZIB-Report |

Tag: | 2-dim Cutting Stock Problem; Combinatorial Optimization; Maximum Diversity Problem; Mixed Integer Programming |

MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science |

90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming | |

Date of first Publication: | 2020/12/07 |

Series (Serial Number): | ZIB-Report (20-34) |

ISSN: | 1438-0064 |