algorithm - 优化学生座位安排的算法

Question

假设我需要将n = 30个学生分成2到6个小组，并且我从每个学生那里收集以下偏好数据:

Student Name: Tom

Likes to sit with: Jimi, Eric

Doesn't like to sit with: John, Paul, Ringo, George

暗示他们对整个 class 中未提及的其他任何学生持中立态度。

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

另外，还有其他方法可以用来计算满足所有提供的约束的解决方案吗？

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

Constants: Total number of students, Student preferences

Variables: Group sizes, Student Groupings, Number of different group arrangements/iterations to test

在此先感谢您提供的任何帮助/建议/指针。

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)。模型很快就解决了。

可能我们需要添加额外的逻辑以确保一个人没有得到真正糟糕的任务。在这里，我们仅优化总和。这笔总和可能会使个人得到一笔不小的交易。在模型中考虑到这一点很有趣。有一些有趣的权衡。