A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values

Schulz, Arne

doi:10.1007/s10479-022-04707-2

A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values

Publication date

2022-05-12

Document type

Forschungsartikel

Author

Schulz, Arne

Organisational unit

Institute of Operations Management, Universität Hamburg

DOI

10.1007/s10479-022-04707-2

URI

https://openhsu.ub.hsu-hh.de/handle/10.24405/22185

Scopus ID

2-s2.0-85129880910

Publisher

Springer Science and Business Media

Series or journal

Annals of Operations Research

ISSN

0254-5330

Periodical volume

318

Periodical issue

1

First page

501

Last page

530

Peer-reviewed

✅

Part of the university bibliography

Nein

Language

English

Keyword

Assignment

Combinatorial optimization

Grouping

Mixed-integer programming

Abstract

The paper presents a new mixed-integer programming formulation for the maximally diverse grouping problem (MDGP) with attribute values. The MDGP is the problem of assigning items to groups such that all groups are as heterogeneous as possible. In the version with attribute values, the heterogeneity of groups is measured by the sum of pairwise absolute differences of the attribute values of the assigned items, i.e. by the Manhattan metric. The advantage of the version with attribute values is that the objective function can be reformulated such that it is linear instead of quadratic like in the standard MDGP formulation. We evaluate the new model formulation for the MDGP with attribute values in comparison with two different MDGP formulations from the literature. Our model formulation leads to substantially improved computation times and solves instances of realistic sizes (for example the assignment of students to seminars) with up to 70 items and three attributes, 50 items and five attributes, and 30 items and ten attributes to (near) optimality within half an hour.

Description

This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Cite as

Schulz, A. A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values. Ann Oper Res 318, 501–530 (2022). https://doi.org/10.1007/s10479-022-04707-2

Version

Published version

Access right on openHSU

Metadata only access