EUVIMEDEUVIMED entdecken
Crossref

New integer linear programming formulations for the maximally diverse grouping problem

Kevin Fu Yuan Lam, Jiang Qian

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →