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

Arne Schulz ()
Additional contact information
Arne Schulz: Universität Hamburg

Annals of Operations Research, 2022, vol. 318, issue 1, No 16, 530 pages

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

Keywords: Mixed-integer programming; Assignment; Grouping; Combinatorial optimization (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-022-04707-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:318:y:2022:i:1:d:10.1007_s10479-022-04707-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-022-04707-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().