2193. An analysis of (mixed-)integer linear programming formulations for the Maximally Diverse Grouping Problem
Invited abstract in session TC-2: Integer Programming I, stream Discrete and Combinatorial Optimization.
Thursday, 11:45-13:15Room: H4
Authors (first author is the speaker)
| 1. | Arne Schulz
|
| Institute of Quantitative Logistics, Helmut Schmidt University |
Abstract
The Maximally Diverse Grouping Problem (MDGP) is a grouping problem that aims at assigning items to groups such that the items assigned to each group are as heterogeneous as possible. Main areas of applications are the assignment of pupils or students to groups or courses. While there can be found good heuristic solution approaches in the literature, exact solution approaches are rarely investigated and typically only able to solve small problem instances. The paper at hand discusses the two well-known model formulations for the MDGP and presents new formulations especially for the case with varying group sizes based on them. All presented and discussed model formulations are evaluated in a comprehensive computational study. The results show that branching on the item-item-assignment is superior to branching on the item-group-assignment and variables for the item-item-assignment allow for additional constraints leading to a stronger LP relaxation.
Keywords
- Combinatorial Optimization
- Mixed-Integer Programming
Status: accepted
Back to the list of papers