最佳学生座位安排的算法

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

学生姓名： Tom

喜欢和以下人坐在一起：吉米·埃里克

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

这意味着他们对整个班级中他们没有提到的任何其他学生都保持中立。

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

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

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

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

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

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

我相信你可以将其表述为一个明确的数学优化问题。

定义二元决策变量：

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

I used:

我使用了包含 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

Notes:

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