优化学生座位安排的算法 [英] Algorithms for optimal student seating arrangements

问题描述

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

Say I need to place n=30 students into groups of between 2 and 6, and I collect the following preference data from each student:

学生姓名: Tom

喜欢坐在一起:埃里克·吉米

不喜欢坐在一起:约翰，保罗，林戈，乔治

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

这暗示着他们对整个班级中没有提到的其他任何学生持中立态度.

It's implied that they're neutral about any other student in the overall class that they haven't mentioned.

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

How might I best run a large number of simulations of many different/random grouping arrangements, to be able to determine a score for each arrangement, through which I could then pick the "most optimal" score/arrangement?

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

Alternatively, are there any other methods by which I might be able to calculate a solution that satisfies all of the supplied constraints?

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

I'd like a generic method that can be reused on different class sizes each year, but within each simulation run, the following constants and variables apply:

常量:学生总数，学生偏好

Constants: Total number of students, Student preferences

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

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

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

Thanks in advance for any help/advice/pointers provided.

推荐答案

我相信您可以将其声明为一个明确的数学优化问题.

I believe you can state this as an explicit mathematical optimization problem.

定义二进制决策变量:

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

我用过:

我使用了28个人的数据集和偏好矩阵(包含-1，+ 1,0个元素).对于组，我使用了4组6组和1组4组.一种解决方案如下所示:

I used your data set with 28 persons, and your preference matrix (with -1,+1,0 elements). For groups, I used 4 groups of 6 and 1 group of 4. A solution can look like:

----     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).模型很快就解决了.
• 可能我们需要添加额外的逻辑，以确保一个人没有得到真正糟糕的任务.在这里，我们仅优化总和.这笔总和可能会使一个人得到一笔不小的交易.在模型中考虑到这一点是一个有趣的练习.有一些有趣的取舍.

• This model can be linearized, so it can be fed into a standard MIP solver
• I solved this directly as a MIQP model (actually the solver reformulated the model into a MIP). The model solved in a few seconds.
• Probably we need to add extra logic to make sure one person is not getting a really bad assignment. We optimize here only the total sum. This overall sum may allow an individual to get a bad deal. It is an interesting exercise to take this into account in the model. There are some interesting trade-offs.

这篇关于优化学生座位安排的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！