The balanced maximally diverse grouping problem with integer attribute values
Publication date
2023-07-14
Document type
Forschungsartikel
Author
Organisational unit
Institute of Operations Management, Universität Hamburg
Scopus ID
Publisher
Springer Science and Business Media
Series or journal
Journal of Combinatorial Optimization
ISSN
Periodical volume
45
Periodical issue
5
Article ID
135
Peer-reviewed
✅
Part of the university bibliography
Nein
Language
English
Keyword
Balanced assignments
Complexity analysis
Grouping
Lower bound
Mixed-integer programming
Abstract
The paper considers the assignment of items to groups according to their attribute values such that the groups are as balanced as possible. Although the problem is in general NP-hard, we prove that it can be solved in pseudo-polynomial time if attribute values are integer. We point out a relation to partition and more general to multi-way number partitioning. Furthermore, we introduce a mixed-integer programming (MIP) formulation, a variable reduction technique, and an efficient lower bound for the objective value. Our computational results show that the lower bound meets the optimal objective value in the most of our instances of realistic size. Hence, the MIP solves instances with several thousand items within seconds to optimality.
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. The balanced maximally diverse grouping problem with integer attribute values. J Comb Optim 45, 135 (2023). https://doi.org/10.1007/s10878-023-01061-2
Version
Published version
Access right on openHSU
Metadata only access