algorithm - 修改版学生项目分配算法

Question

我正在为一个非营利组织开展一个项目，他们试图帮助有特殊需求的学生适应不同的项目主题。每个学生将有四个偏好，一组主管将列出他们对所指导主题的偏好列表。
我寻找的解决方案是一种算法，它可以找到将学生与项目主题和主管相匹配的最佳解决方案。
我已经广泛阅读了 SPA、HR 和其他贪心算法，甚至尝试了一种遗传算法。到目前为止，我只有压力。
这是程序的流程。

我们有一系列主题供主管表达他们的兴趣。主管可以选择他们喜欢监督的主题，他们也可以建议一个主题并决定他们想要监督多少个项目组。

P1, P2, P3, P4, P5 ...... Pn ... SP1, SP2, SP3 .... SPn在上面的列表中， P1 ... Pn是现有主题和 SP1...SPn是建议的主题。
假设在这一轮之后，我们有一个具有以下偏好的主管列表。

supervisor | Topics of Interest | No. Of Groups
L1         | P1, P3, P4         |     2
L2         | P5, P2, P9         |     1
L3         | P1, P3, P4         |     1
L4         | P1, P3, P4         |     4
L5         | SP1, P3, P8        |     3
L6         | P32, P3, P40       |     3

经过以上一轮，我们知道只有主管可以在以下主题上监督学生。 P1, P2, P3, P4, P8, P9, P32, P40, SP1

当我们为学生打开主题时，他们将只能从上面的列表中选择项目，以及他们的偏好/优先级。例如

student    | Pref1 | Pref 2 | Pref 3 | Pref 4 |
S1         |  P4   |  P1    |  SP1   |   P5   |
S2         |  P1   |  P9    |  SP1   |   P5   |
S3         |  P3   |  P1    |  P2    |   P5   |
S4         |  P4   |  P1    |  P40   |   P5   |
S5         |  P4   |  P32   |  SP1   |   P5   |
...
Sn         |  P9   |  P1    |  SP1   |   P5   |

现在，一旦学生选择了偏好，我们将决定一个数字 MAX_GROUP_SIZE我们将运行我们的算法将这些学生分组
一种。将兴趣相似的学生分组到同一组中(例如，我们添加选择 P1 作为他们的 pref1 的学生，并在他们没有第一选择的组时用 pref2, pref3, pref4 填写其余的学生)。
湾将一名主管分配给他对项目表现出兴趣的小组(理想情况下，每个学生的第一个偏好或最匹配的项目)
C。如果主管对 P1, P2, P3 表现出兴趣，我们需要确保我们不会让主管重载。并提到他只能监督 2项目，那么我们应该只将他添加到 2项目。
到目前为止，我一直在尝试上述算法，但我仍然认为我没有为学生提供合理的解决方案。我更喜欢更偏向于学生的解决方案，因为他们有特殊需求。如果有人可以为我指明正确的方向，或者可以为我提供定义明确的算法或实现，我不仅会感谢您的努力，而且还会请您喝杯咖啡。

Answer 1

作为一个以做这种事情为生的人来说，这个问题的核心与一个名为“capacitated facility location”的标准问题非常相似，在我想象你正在处理的规模上，可以通过整数规划干净地处理.我可以保证免费Google OR-Tools (免责声明:是的，那是我的雇主；不，不是代表他们说话)，但您还有其他几个免费和付费选项(SCIP、lpsolve、Gurobi、CPLEX)。
整数规划非常好:你声明一些变量，在这些变量上写一些约束和目标，按下一个按钮，得到一个(通常是最优的)解决方案。
在这里，我们将拥有以下二进制变量:

对于每对(学生 i，潜在项目 j 学生 i)，我们有一个 0-1 变量 Assign[i,j]如果该学生执行该项目，则为 1，否则为 0。

对于每对(顾问 k，潜在项目 j 为顾问 k)，我们有一个 0-1 变量 Avail[k,j]如果该顾问执行该项目，则为 1，否则为 0。

目标是

minimize sum_{i,j} PreferenceValue[i,j] Assign[i,j],

哪里 PreferenceValue[i,j]具有较低的值来表示学生更喜欢的项目。您可以使用 1,2,3,4例如第一、第二、第三、第四选择；或偏向首选 1,2,2,2 ;或对公平的偏见 1,4,9,16 .玩的多，玩的开心。根据要求，这个目标并不关心我们让顾问做什么。
约束是

for each student i, sum_j Assign[i,j] = 1,

即，每个学生都被分配了一个项目；

for each advisor k, sum_j Avail[k,j] ≤ MaxGroups[k],

即，没有顾问有比他们想要的更多的工作；

for each student i and project j, Assign[i,j] ≤ sum_k Avail[k,j],

即，每个学生只能分配到一个可用的项目中；

for each project j, sum_i Assign[i,j] ≤ MaxGroupSize,

即每组最多有 MaxGroupSize学生们。
OR-Tools 不允许您像这样编写“for each”和“sum”，因此您必须编写一个简短的程序来扩展它们。阅读 OR-Tools 文档。
希望这是一个足够的开始，当您构建它并且它不可避免地让您的期望失望时，您可以弄清楚如何添加更多约束以防止您不想要的解决方案。祝你好运!