New integer linear programming formulations for the maximally diverse grouping problem
Journal of Combinatorial Optimization · 2026-07 · 51 (5)
DOI: 10.1007/s10878-026-01427-2 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Combinatorial Optimization, online erschienen am 01.07.2026. Verfasst von Kevin Fu Yuan Lam und 1 weiteren Autor:innen. Die Arbeit nennt 19 Literaturangaben.
Abstract (Originalsprache)
The Maximally Diverse Grouping Problem (MDGP) is the problem of assigning a set of elements to mutually disjoint groups in order to maximise the overall diversity between the elements. The MDGP is often formulated as an Integer Quadratic Programme (IQP). Because the MDGP is NP-complete, most studies have focused on heuristic solution approaches, as compared to exact solution approaches, to the problem. Although heuristic solution approaches are often used in practice, these approaches do not guarantee a global optimal solution. Conversely, although exact solution approaches are not often used in practice, these approaches guarantee a global optimal solution, and therefore serve as useful benchmarks for the performance of heuristics. As such, a few studies have formulated the MDGP as an Integer Linear Programme (ILP), which can be solved using exact solution approaches. The present paper proposes two new ILP formulations, and compares their performances against existing formulations. The proposed formulations can be used to establish useful benchmarks for the performance of heuristics in a broader range of applications moving forward.
Zitieren
APA
Lam, K. F. Y., & Qian, J. (2026). New integer linear programming formulations for the maximally diverse grouping problem. Journal of Combinatorial Optimization, 51(5). https://doi.org/10.1007/s10878-026-01427-2
Vancouver
Lam KFY, Qian J. New integer linear programming formulations for the maximally diverse grouping problem. Journal of Combinatorial Optimization. 2026;51(5). doi:10.1007/s10878-026-01427-2
BibTeX
@article{Lam2026,
author = {Lam, Kevin Fu Yuan and Qian, Jiang},
title = {New integer linear programming formulations for the maximally diverse grouping problem},
journal = {Journal of Combinatorial Optimization},
year = {2026},
volume = {51},
number = {5},
doi = {10.1007/s10878-026-01427-2}
}
EUVIMED