优化学生座位安排的算法

Question

假设我需要将 n=30 名学生分成 2 到 6 人一组，我从每个学生那里收集以下偏好数据：

学生姓名：汤姆

喜欢坐在一起：吉米、埃里克

不喜欢坐在一起：约翰、保罗、林戈、乔治

这暗示他们对全班其他他们没有提到的学生保持中立。

我如何才能最好地运行许多不同/随机分组安排的大量模拟，以便能够确定每个安排的分数，然后我可以选择“最佳”分数/安排？

或者，是否有任何其他方法可以计算出满足所有提供的约束的解决方案？

我想要一种可以每年在不同班级规模上重复使用的通用方法，但在每次模拟运行中，以下常量和变量都适用：

常量：学生总数、学生偏好

变量：团体规模、学生分组、不同团体安排/要测试的迭代次数

预先感谢您提供的任何帮助/建议/指示。

Answer 1

我相信您可以将其表述为一个显式的数学优化问题。

定义二元决策变量：

x(p,g) = 1 if person p is assigned to group g
         0 otherwise

我用了：

我使用了您的 28 人数据集和您的偏好矩阵（包含 -1,+1,0 元素）。对于组，我使用了 4 组 6 组和 1 组 4 组。解决方案如下所示：

----     80 PARAMETER solution  using MIQP model

               group1      group2      group3      group4      group5

aimee               1
amber-la                                                1
amber-le                                                            1
andrina             1
catelyn-t                                   1
charlie                                                 1
charlotte                                   1
cory                            1
daniel                          1
ellie               1
ellis               1
eve                                         1
grace-c                                                 1
grace-g                                                 1
holly                                                   1
jack                            1
jade                                                                1
james                           1
kadie                                       1
kieran                                                              1
kristiana                                   1
lily                                                                1
luke                            1
naz                 1
nibah                                       1
niko                            1
wiki                1
zeina                                                   1
COUNT               6           6           6           6           4

笔记：

• 该模型可以线性化，因此可以输入标准 MIP 求解器
• 我直接作为 MIQP 模型解决了这个问题（实际上，求解器将模型重新制定为 MIP）。该模型在几秒钟内求解。
• 可能我们需要添加额外的逻辑来确保一个人不会得到一个非常糟糕的任务。我们在这里只优化总和。这个总和可能会让个人得到一笔糟糕的交易。在模型中考虑到这一点是一个有趣的练习。有一些有趣的权衡。