The paper presents an exponential-sized neighborhood for the Maximally Diverse Grouping Problem (MDGP) comprising the reassignment of at most one item per group. We show that the best assignment of at most one item per group can be obtained by solving a Maximum Weighted Bipartite Matching Problem if the items are known. This neighborhood is already exponential-sized. However, we extend the neighborhood further by including the selection of at most one item per group with and without a given group sequence into the neighborhood. We show in a computational study that 40%–60% of the best found solutions by state-of-the-art metaheuristics for the MDGP for small instances with up to 960 items can be improved by an evaluation of this neighborhood. For large instances with 2000 and 3000 items only a single solution could not be improved for one of the four state-of-the-art approaches while improvements of up to 2% were realized. The neighborhood itself can be evaluated within some seconds for instances with up to 480 items (40–90s for 960 items) by an integer program. Moreover, the neighborhood can be evaluated by a dynamic program if the group sequence is determined. For the large benchmark set this algorithm could improve within around one second of computation time on 66%–92% of the best found solutions the state-of-the-art approaches found after 1200s and 3000s seconds of computation time, respectively. Finally, we develop a research agenda to evaluate how to use the new neighborhood (heuristically) within advanced solution approaches. • Investigation of neighborhood where at most one item per group is changed for MDGP. • An integer program is presented to evaluate neighborhood. • A DP is presented to evaluate neighborhood with given group sequence. • Solutions found by state-of-the-art approaches can be improved in post optimization.
Arne Schulz (Fri,) studied this question.