🔢 mathematics

An analysis of mixed-integer linear programming formulations for the Maximally Diverse Grouping Problem

This paper analyzes and proposes new mixed-integer linear programming formulations for the Maximally Diverse Grouping Problem, demonstrating through computational study that models based on item-item assignments outperform those using item-group assignments by providing stronger LP relaxations and superior branching performance.

Original authors: Arne Schulz

Published 2026-07-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Arne Schulz

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the head coach of a massive sports camp, and you have a huge list of campers (the "items") and a bunch of cabins (the "groups"). Your goal isn't to put the best players together; it's the exact opposite! You want every single cabin to be a melting pot of totally different personalities. Maybe you want the quiet artist, the loud musician, and the sleepy gamer all in one room. The more different the people in a room are from each other, the higher your "Diversity Score." This is the Maximally Diverse Grouping Problem (MDGP).

The big question the paper tackles is: How do we use a computer to figure out the perfect, most chaotic mix of people for every cabin without crashing the computer?

The Old Way: The "Who Goes Where?" Guessing Game

For a long time, the standard way to solve this was to ask the computer a simple question for every camper: "Are you in Cabin A? Cabin B? Cabin C?"

The authors call this the Standard Formulation. They ran simulations with up to 30 campers and found that this method is like trying to find a needle in a haystack while wearing blindfolded, fuzzy socks.

The Problem: The computer's "relaxed" guess (where it preters campers can be half-in Cabin A and half-in Cabin B) was way too optimistic. It thought it could get a perfect score by splitting everyone's time equally among all cabins.
The Result: When the computer tried to solve real problems, it got stuck. For groups with 30 campers and 10 cabins, the computer often ran for the full 1,800 seconds (30 minutes) and still couldn't find the best answer, leaving a huge gap between its best guess and the actual solution.

The New Way: The "Best Friends" Strategy

A few years ago, a different team (Papenberg and Klau) tried a totally different approach, but only for when every cabin had to have the exact same number of people. Instead of asking "Which cabin are you in?", they asked: "Are Camper A and Camper B in the same cabin together?"

The authors of this paper decided to test this "Best Friends" strategy (which they call the Papenberg and Klau formulation) and even tried to stretch it to work when cabins have different size limits (some can hold 5 people, others 8).

The Big Discovery: "Togetherness" Wins

The authors ran a massive computational study, testing 10 different scenarios for every combination of camper counts (from 10 to 30) and cabin counts (from 2 to 10). Here is what they found:

The "Best Friends" Strategy is Superior:
The method that focuses on whether two people are together (branching on item-item assignment) is much faster and smarter than the method that focuses on which cabin they are in.
- Proof: In their simulations, the "Best Friends" model solved almost every small and medium-sized problem perfectly. Even for the hardest 30-camper problems, it found the best answer or got incredibly close, while the old "Who Goes Where?" model often gave up after 30 minutes.
The "Dummy" Trick for Uneven Cabins:
The original "Best Friends" model only worked if every cabin was the same size. To fix this, the authors invented a clever trick: they added "dummy" campers (invisible placeholders) to the list.
- How it works: They told the computer, "Every real cabin must have exactly one dummy camper." This forces the computer to group the real campers around these dummies, effectively creating cabins of different sizes while still using the powerful "Best Friends" logic.
- The Result: This new, adapted model (called FPKv) performed the best of all. It solved the varying-size problems faster than any other method tested.
Why the Old Way Failed:
The paper explicitly argues that the old method fails because its "relaxed" math allows for impossible scenarios (like a camper being 50% in two cabins) that look great on paper but are useless in reality. The new method's math is tighter; it forces the computer to think in terms of actual pairs, which leads to a much stronger, more realistic starting point.

The Bottom Line

The paper doesn't claim to have solved the problem for every possible scenario in the universe, but for the specific test cases they ran (up to 30 items), the results are clear.

If you want to group things to be as different as possible:

Don't just ask the computer "Which group?" (The old way).
Do ask the computer "Are these two together?" (The new way).

The authors' simulations show that this shift in perspective turns a sluggish, confused computer into a lightning-fast solver. They even built a new version of this "Best Friends" model that handles uneven group sizes, proving that looking at the problem through the lens of "who is with whom" is the secret sauce to cracking the code.

Technical Summary: An Analysis of (Mixed-)Integer Linear Programming Formulations for the Maximally Diverse Grouping Problem

Problem Definition

The Maximally Diverse Grouping Problem (MDGP) is a classical NP-hard combinatorial optimization problem. Given a set of items $I$ and a set of groups $G$ , the objective is to assign each item to exactly one group such that the total diversity within the groups is maximized. The diversity of a pair of items $(i, j)$ is defined by a parameter $d_{ij} \geq 0$ . The total diversity is the sum of all pairwise diversities for items assigned to the same group. The problem is subject to constraints on the number of items per group, defined by lower bounds $l_g$ and upper bounds $u_g$ for each group $g \in G$ .

Applications for the MDGP include assigning students to groups or courses, forming project teams, creating reviewer groups, and scheduling final exams. While heuristic approaches are common in the literature, exact solution methods have historically been limited to small problem instances.

Methodology and Model Formulations

The paper analyzes and compares four distinct (mixed-)integer linear programming (MILP) formulations:

Standard Formulation (Weitz and Lakshminarayanan, 1998):
- Variables: Binary variables $x_{ig}$ indicate if item $i$ is assigned to group $g$ . Auxiliary binary variables $y_{ijg}$ represent if items $i$ and $j$ are both in group $g$ .
- Mechanism: The objective is linearized using constraints $y_{ijg} \leq x_{ig}$ and $y_{ijg} \leq x_{jg}$ .
- Weakness: The Linear Programming (LP) relaxation is weak. In the relaxation, items can be fractionally assigned to all groups ( $x_{ig} = 1/|G|$ ), causing the objective value to sum all possible $d_{ij}$ pairs, which is an unattainable upper bound for feasible integer solutions.
Papenberg and Klau Formulation (2021):
- Variables: Binary variables $z_{ij}$ indicate if items $i$ and $j$ are assigned to the same group, without specifying which group.
- Mechanism: Uses transitivity constraints (e.g., $-z_{ij} + z_{ik} + z_{jk} \leq 1$ ) to ensure consistency and a constraint ensuring every item is grouped with exactly $|I|/|G| - 1$ other items.
- Strength: Branching occurs on item-item assignments ( $z_{ij}$ ), which directly influence the objective function. The LP relaxation is significantly stronger because constraints limit the number of pairs per item to the group size.
- Limitation: Originally designed only for equal-sized groups.
Combined Formulation:
- Mechanism: Merges the standard formulation with the Papenberg and Klau approach by linking $z_{ij} = \sum_{g \in G} y_{ijg}$ .
- Contribution: Adds transitivity constraints to the standard model and adapts group size constraints for varying sizes. The paper proves that for equal-sized groups, this formulation has an LP relaxation at least as strong as the Papenberg and Klau formulation.
Adapted Papenberg and Klau Formulation (for Varying Group Sizes):
- Mechanism: Extends the Papenberg and Klau model to handle varying group sizes ( $l_g \neq u_g$ ) by introducing a "dummy item" for each group.
- Variables: Items are assigned to dummy items (representing groups) via $z_{i, \text{dummy}}$ .
- Constraints: Transitivity constraints apply to all items including dummies. Constraints ensure each real item is assigned to exactly one dummy group, and the size of the cluster around each dummy adheres to $l_g$ and $u_g$ .

Key Contributions

Comparative Analysis: The paper provides a theoretical and empirical comparison of the standard item-group assignment formulation versus the item-item assignment formulation.
Theoretical Insight: It demonstrates that branching on item-item assignment variables ( $z_{ij}$ ) is superior to branching on item-group assignment variables ( $x_{ig}$ ) because the former directly restricts the objective function value and yields a tighter LP relaxation.
New Formulations: Two new formulations are presented to handle the general case of varying group sizes, extending the applicability of the stronger item-item assignment logic.
Symmetry Breaking: The paper discusses and transfers symmetry-breaking constraints to the general case for the standard formulation.

Computational Results

A comprehensive computational study was conducted using CPLEX 12.9 on instances ranging from 10 to 30 items and 2 to 10 groups. Both equal-sized and varying-sized group scenarios were tested.

LP Relaxation Quality: The Papenberg and Klau formulation and its adaptations consistently produced significantly tighter upper bounds (smaller gaps) compared to the standard formulation. The standard formulation's LP relaxation gaps were often over 100%, whereas the item-item formulations remained much lower.
Solving Performance:
- Equal-Sized Groups: The Papenberg and Klau formulation solved almost all instances to optimality faster than the standard formulation.
- Varying Group Sizes: The adapted Papenberg and Klau formulation (Section 3.4) performed best, solving instances with up to 30 items to optimality or with small gaps within the 1800-second time limit.
- Standard Formulation: Struggled significantly, often failing to close the gap or solve instances with more than 15 items within the time limit.
- Combined Formulation: While theoretically strong, the combined formulation did not show a substantial performance improvement over the standard formulation when branching on $x_{ig}$ variables, suggesting that the transitivity constraints alone are insufficient to overcome the weakness of the item-group branching strategy.

Significance and Claims

The paper claims that the primary driver for the superior performance of the new formulations is the branching strategy. By branching on item-item assignments rather than item-group assignments, the solver can more effectively prune the search space due to the stronger LP relaxation provided by transitivity constraints.

The study concludes that for the MDGP, especially in settings with varying group sizes, the adaptation of the Papenberg and Klau formulation is the most effective exact approach currently available. It successfully extends the benefits of item-item assignment logic to general grouping constraints, overcoming the limitations of the decades-old standard formulation. The authors note that while the adapted formulation performs best, instances with varying group sizes remain harder to solve than equal-sized ones, likely due to the increased solution space flexibility.