🔢 mathematics

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

本文分析并提出了最大多样性分组问题的新型混合整数线性规划模型，并通过计算研究证明，基于项目-项目分配的模型通过提供更强的线性规划松弛和更优的分支性能，其表现优于使用项目-组分配的模型。

原作者： Arne Schulz

发布于 2026-07-15

📖 1 分钟阅读🧠 深度阅读

原作者： Arne Schulz

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是某大型运动营的主教练，你有一份超长的学员名单（即“项目/物品”）和一堆小木屋（即“小组”）。你的目标并不是要把最优秀的球员聚在一起；恰恰相反，你想要的是让每一个小木屋都成为一个性格迥异的熔炉。也许你想让安静的艺术家、吵闹的音乐家和嗜睡的游戏玩家都在同一个房间里。这些人之间的差异性越大，你的“多样性得分”就越高。这就是最大多样性分组问题（Maximally Diverse Grouping Problem, MDGP）。

核心问题在于：我们如何利用计算机来计算出每个木屋最完美、最混乱的组合，同时又不至于让计算机崩溃？

旧方法：“你在哪儿？”猜谜游戏

长期以来，解决这个问题的标准方法是针对每一位学员问一个简单的问题：“你在 A 木屋吗？B 木屋吗？C 木屋吗？”

作者们称之为标准建模方式（Standard Formulation）。他们进行了多达 30 名学员规模的模拟实验，发现这种方法就像是在蒙着眼睛、穿着毛茸茸的袜子的情况下，试图在干草堆里找一根针。

问题所在： 计算机的“松弛化”猜测（即学员可以处于“一半在 A 木屋，一半在 B 木屋”的状态）过于乐观了。它认为可以通过将每个人的时间平均分配到所有木屋内来获得完美得分。
结果： 当计算机尝试解决实际问题时，它会陷入困境。对于 30 名学员和 10 个木屋的情况，计算机经常运行满 1,800 秒（30 分钟）后仍无法找到最优解，导致其最佳猜测与实际解之间存在巨大的差距。

新方法：“好朋友”策略

几年前，另一支团队（Papenberg 和 Klau）尝试了一种完全不同的方法，但该方法仅适用于每个木屋必须拥有完全相同人数的情况。他们不再问“你在哪个木屋？”，而是问：“学员 A 和学员 B 是否在同一个木屋里？”

本文的作者决定测试这种“好朋友”策略（他们称之为 Papenberg 和 Klau 建模方式），并尝试将其扩展到适用于木屋容量不等（例如有的能容纳 5 人，有的能容容纳 8 人）的情况。

重大发现：“在一起”才是王道

作者进行了一项大规模的计算研究，针对每种学员数量（10 到 30 人）和木屋数量（2 到 10 个）的 10 种不同场景进行了测试。以下是他们的发现：

“好朋友”策略更胜一筹：
这种专注于两人是否“在一起”（基于项目-项目分配进行分支）的方法，比关注他们在“哪个木屋”的方法更快、更聪明。
- 证明： 在模拟实验中，“好朋友”模型几乎完美解决了所有中小规模的问题。即使面对最难的 30 人问题，它也能找到最优解或极其接近最优解，而旧的“你在哪儿？”模型往往在 30 分钟后就放弃了。
处理不均匀木屋的“虚拟人”技巧：
原始的“好朋友”模型只能在每个木屋大小相等时工作。为了解决这个问题，作者发明了一个聪明的技巧：他们在名单中加入了“虚拟学员”（不可见的占位符）。
- 运作方式： 他们告诉计算机：“每个真实的木屋必须恰好有一个虚拟学员。”这迫使计算机围绕这些虚拟学员来组合真实的学员，从而在仍使用强大的“好朋友”逻辑的同时，有效地创建了不同规模的木屋。
- 结果： 这个经过改进的新模型（称为 FPKv）表现得最好。它比测试过的任何其他方法都更快地解决了规模变化的题目。
为什么旧方法会失败：
论文明确指出，旧方法之所以失败，是因为其“松弛化”数学模型允许出现不可能的场景（比如一名学员 50% 在两个木屋内），这些场景在理论上看起来很美，但在现实中毫无意义。新方法的数学逻辑更严密；它迫使计算机以真实的“配对”为思考基础，从而提供了一个更强大、更真实的起点。

总结

本文并不声称已经解决了宇宙中所有可能的场景，但对于他们测试的特定案例（最多 30 个项目），结论是明确的。

如果你想让分组尽可能具有多样性：

不要只问计算机“你在哪个组？”（旧方法）。
要问计算机“这两个人在一起吗？”（新方法）。

作者的模拟实验表明，这种视角的转变将一个迟钝、困惑的计算机变成了一个反应极快的求解器。他们甚至开发了这种“好朋友”模型的一个新版本，使其能够处理不均匀的组规模，这证明了通过“谁与谁在一起”的视角来看待问题，是破解代码的关键秘诀。

技术摘要：关于最大多样性分组问题（Maximally Diverse Grouping Problem）之（混合-）整数线性规划模型的分析

问题定义

最大多样性分组问题（MDGP）是一个经典的 NP-hard 组合优化问题。给定一组项目 $I$ 和一组组别 $G$ ，目标是将每个项目分配到恰好一个组中，使得组内的总多样性最大化。一对项目 $(i, j)$ 的多样性由参数 $d_{ij} \geq 0$ 定义。总多样性是分配在同一组中的所有项目对的多样性之和。该问题受限于每组项目数量的约束，即每个组 $g \in G$ 具有下界 $l_g$ 和上界 $u_g$ 。

MDGP 的应用包括将学生分配到小组或课程、组建项目团队、创建评审小组以及安排期末考试。虽然文献中常见的做法是启发式方法，但精确解法在历史上仅限于处理小规模问题实例。

方法论与模型构建

本文分析并比较了四种不同的（混合-）整数线性规划（MILP）模型：

标准模型 (Weitz and Lakshminarayanan, 1998)：
- 变量： 二进制变量 $x_{ig}$ 表示项目 $i$ 是否被分配到组 $g$ 。辅助二进制变量 $y_{ijg}$ 表示项目 $i$ 和 $j$ 是否同时在组 $g$ 中。
- 机制： 通过约束条件 $y_{ijg} \leq x_{ig}$ 和 $y_{ijg} \leq x_{jg}$ 实现目标函数的线性化。
- 缺陷： 其线性规划（LP）松弛非常弱。在松弛状态下，项目可以被分数化地分配到所有组中（ $x_{ig} = 1/|G|$ ），导致目标值累加了所有可能的 $d_{ij}$ 对，这是一个对于可行整数解而言无法达到的上界。
Papenberg and Klau 模型 (2021)：
- 变量： 二进制变量 $z_{ij}$ 表示项目 $i$ 和 $j$ 是否被分配到相同的组中，而不指定具体是哪一组。
- 机制： 使用传递性约束（例如， $-z_{ij} + z_{ik} + z_{jk} \leq 1$ ）来确保一致性，并使用一个约束确保每个项目与其他 $|I|/|G| - 1$ 个项目分组。
- 优势： 分支过程发生在项目-项目分配（ $z_{ij}$ ）上，这直接影响目标函数。其 LP 松弛显著增强，因为约束限制了每个项目的配对数量以符合组大小。
- 局限性： 最初仅为等规模分组设计。
组合模型：
- 机制： 通过链接 $z_{ij} = \sum_{g \in G} y_{ijg}$ 将标准模型与 Papenberg and Klau 方法结合起来。
- 贡献： 为标准模型增加了传递性约束，并针对不同规模的组调整了规模约束。论文证明，对于等规模分组，该模型的 LP 松弛至少与 Papenberg and Klau 模型一样强。
适配后的 Papenberg and Klau 模型（用于变化规模的分组）：
- 机制： 通过引入每个组的“虚拟项目”（dummy item）来扩展 Papenberg and Klau 模型，以处理变化的组规模（ $l_g \neq u_g$ ）。
- 变量： 项目通过 $z_{i, \text{dummy}}$ 被分配给虚拟项目（代表组）。
- 约束： 传递性约束适用于包括虚拟项目在内的所有项目。约束确保每个真实项目被分配到恰好一个虚拟组中，且每个虚拟组周围的集群规模符合 $l_g$ 和 $u_g$ 。

核心贡献

对比分析： 论文提供了项目-组分配模型与项目-项目分配模型的理论与实证比较。
理论洞察： 论文表明，在项目-项目分配变量（ $z_{ij}$ ）上进行分支优于在项目-组分配变量（ $x_{ig}$ ）上进行分支，因为前者能直接限制目标函数值，并产生更紧的 LP 松弛。
新模型： 提出了两种新模型来处理一般情况下的变化规模分组，扩展了更强的项目-项目分配逻辑的应用范围。
对称性破缺： 论文讨论并将对称性破缺约束转移到了标准模型的通用情况中。

计算结果

研究使用 CPLEX 12.9 对规模从 10 到 30 个项目、2 到 10 个组的实例进行了全面的计算研究。测试了等规模分组和变化规模分组两种场景。

LP 松弛质量： Papenberg and Klau 模型及其适配版本始终比标准模型产生显著更紧的上界（更小的间隙）。标准模型的 LP 松弛间隙通常超过 100%，而项目-项目模型保持在较低水平。
求解性能：
- 等规模分组： Papenberg and Klau 模型几乎比标准模型更快地求解了几乎所有实例。
- 变化规模分组： 适配后的 Papenberg and Klau 模型（第 3.4 节）表现最佳，在 1800 秒的时间限制内，将多达 30 个项目的实例求解至最优或取得了较小的间隙。
- 标准模型： 表现挣扎，通常无法在时间限制内缩小间隙或求解超过 15 个项目的实例。
- 组合模型： 虽然在理论上很强，但在基于 $x_{ig}$ 变量进行分支时，组合模型并未显示出相对于标准模型的实质性性能提升，这表明仅靠传递性约束不足以克服项目-组分支策略的弱点。

意义与主张

论文声称，新模型卓越性能的主要驱动力是分支策略。通过在项目-项目分配而非项目-组分配上进行分支，由于传递性约束提供了更强的 LP 松弛，求解器可以更有效地剪枝搜索空间。

研究结论指出，对于 MDGP，特别是在组规模变化的情况下，适配后的 Papenberg and Klau 模型是目前最有效的精确方法。它成功地将项目-项目分配逻辑的优势扩展到了通用的分组约束中，克服了存在数十年的标准模型的局限性。作者指出，虽然适配后的模型表现最好，但由于解空间灵活性的增加，具有变化规模分组的实例仍然比等规模分组更难求解。