学生项目分配算法的修改版本
Modified version of Student Project Allocation algorithm
我正在为一个非营利组织开展一个项目，他们试图帮助有特殊需要的学生适应不同的项目主题。每个学生将有四个偏好，一组导师将有他们监督的主题的偏好列表。
我寻找的解决方案是一种算法，它可以找到将学生与项目主题和导师相匹配的最佳解决方案。
我广泛阅读了 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
- 当我们为学生打开主题时，他们将只能从上面的列表中选择项目，他们 preference/priority。例如
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 ）。
b.将主管分配到他对项目表现出兴趣的小组（理想情况下，每个学生的第一偏好或最匹配的项目）
C。我们需要确保我们不会让主管超负荷，如果主管对 P1, P2, P3 表现出兴趣并提到他只能监督 2 个项目，那么我们应该只将他添加到 2 项目。
到目前为止，我一直在尝试上面解释的算法，但我仍然认为我没有为学生提供合理的解决方案。我更喜欢一种更偏向于学生的解决方案，因为他们有特殊需要。如果有人能给我指出正确的方向，或者能为我提供定义明确的算法或实现，我不仅会感谢您的努力，还会请您喝杯咖啡。
作为一个以做这种事情为生的人来说，这个问题的核心与一个名为“capacitated facility location", which at the scales I imagine you're dealing with can be handled cleanly by integer programming. I can vouch for the free Google OR-Tools 的标准问题非常相似（免责声明：是的，那是我的雇主；不，不是说话为他们），但您还有其他几个免费和付费选项（SCIP、lpsolve、Gurobi、CPLEX）。
整数规划非常好：您声明一些变量，在这些变量上写一些约束和 objective，按下按钮并获得（通常是最优的）解决方案。
这里我们将有以下二进制变量：
对于每一对（学生i，学生i的潜在项目j），我们有一个0-1变量Assign[i,j]如果该学生做该项目，则为 1，否则为 0。
对于每一对（顾问k，顾问k的潜在项目j），我们有一个0-1变量Avail[k,j]如果该顾问执行该项目，则为 1，否则为 0。
objective是
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 偏向于公平。玩的多，玩的开心。根据要求，这个 objective 不关心我们让顾问做什么。
约束是
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 文档。
希望这是一个足够的开始，当您构建它并且它不可避免地让您失望时，您可以弄清楚如何添加更多约束以防止您不想要的解决方案。祝你好运！
您的问题陈述中存在歧义，根据问题的解决方式，您将更改要使用的算法。歧义以后再讨论。
正如其他人所建议的，这属于组合优化领域，有许多不同的 OR 工具可用于解决这个问题。
首先，我建议使用一系列加权二分匹配和（可能）解决方案修剪。
这是一个用 python 编写的解决方案，使用 networkx 基于两个二分匹配的序列（第一个是针对学生的加权匹配，第二个是未加权的。）
#!/usr/bin/python
"""
filename: student_assign.py
purpose: demonstrate that the problem described in
can be solved as a sequence of assignment problems solved through a weighted bipartite matching.
"""
import networkx as nx
import numpy as np
# For this demonstration we take data directly from the problem description
#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
supervisors = {
'L1' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 2},
'L2' : { 'topics' : ['P5', 'P2', 'P9'], 'num_groups' : 1},
'L3' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 1},
'L4' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 4},
'L5' : { 'topics' : ['SP1', 'P3', 'P8'], 'num_groups' : 3},
'L6' : { 'topics' : ['P32', 'P3', 'P40'], 'num_groups' : 3},
}
all_topics = sorted(list({ t for s in supervisors for t in supervisors[s]['topics'] }))
# assuming there is a typo in the problem specification and 'supervisor' = 'student' below
#supervisor | 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 |
#S6 | P9 | P1 | SP1 | P5 |
students = {
'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'] ,
'S6' : ['P9', 'P1', 'SP1', 'P5'] ,
}
MAX_GROUP_SIZE = 2
def get_student_assignments_to_topics(all_topics,students,max_group_size=MAX_GROUP_SIZE):
G = nx.DiGraph()
G.add_node('sink',demand=len(students))
for topic in all_topics:
G.add_node(topic)
G.add_edge(topic, 'sink', weight = 0, capacity = max_group_size)
for student in students:
prefs = students[student]
G.add_node(student,demand=-1)
# add increasing weight edges from student to preferences (lowest == best)
for i, topic in enumerate(prefs):
G.add_edge(student, topic, weight = i, capacity = 1)
# solve the weighted matching
flow_dict = nx.min_cost_flow(G)
# decode which student is assigned to which topic
student_assignments = { t : [] for t in all_topics}
for student in students:
adjacency = flow_dict[student]
prefs = students[student]
for pref in prefs:
if adjacency[pref]:
student_assignments[pref].append(student)
break
return student_assignments
def get_topic_assignments_to_supervisors(student_assignments,supervisors):
non_empty_student_assignments = { topic : student_assignments[topic] for topic in student_assignments if len(student_assignments[topic]) > 0}
G = nx.DiGraph()
G.add_node('sink',demand=len(non_empty_student_assignments))
for topic in non_empty_student_assignments:
G.add_node(topic,demand=-1)
for supervisor in supervisors:
supervisor_properties = supervisors[supervisor]
for topic in supervisor_properties['topics']:
if topic in non_empty_student_assignments:
G.add_edge(topic, supervisor, weight = 0, capacity = 1)
G.add_edge(supervisor, 'sink', weight = 0, capacity = supervisor_properties['num_groups'])
# solve the unweighted matching
flow_dict = nx.min_cost_flow(G)
# decode which supervisor is assigned to which topic
topic_assignments = { s : [] for s in supervisors}
for supervisor in supervisors:
supervisor_properties = supervisors[supervisor]
for topic in supervisor_properties['topics']:
if topic in non_empty_student_assignments:
adjacency = flow_dict[topic]
if adjacency[supervisor]:
topic_assignments[supervisor].append(topic)
return topic_assignments
# assign students to topics by preference
student_assignments = get_student_assignments_to_topics(all_topics,students)
# assign all topics with at least one student to a supervisor who fits the criteria
topic_assignments = get_topic_assignments_to_supervisors(student_assignments,supervisors)
print 'These are the assignment of students to topics based on preference:'
print student_assignments
print 'These are the assignment of topics to supervisors based on availability:'
print topic_assignments
此脚本输出：
These are the assignment of students to topics based on preference:
{'P2': [], 'P3': ['S3'], 'P1': ['S2', 'S1'], 'P4': ['S5', 'S4'], 'P5': [], 'SP1': [], 'P8': [], 'P9': ['S6'], 'P32': [], 'P40': []}
These are the assignment of topics to supervisors based on availability:
{'L6': [], 'L4': ['P1', 'P3'], 'L5': [], 'L2': ['P9'], 'L3': ['P4'], 'L1': []}
歧义
关于如何处理重要的边缘情况存在歧义：
- 如果学生对主题不感兴趣怎么办？
- 如果一个主题只有一个学生感兴趣怎么办？
- 学生可能必须对所有可能的主题进行排序以确保存在解决方案？
- 主管是否也应该对主题有偏好（如果有，谁的偏好优先？）
- 主管分配给主题的负载是否应该平衡（首选所有主管的工作量相似的解决方案）？
对这些消除歧义的具体问题的回答非常重要，它们将塑造您所设计的解决方案的类型（以及能够向您的算法用户传达优化的内容。）
我绝对建议您花更多时间来消除问题的歧义。
解决方案存在
此处介绍的顺序二分匹配算法将找到最优解；但是，它可能找不到 a 解决方案，即使存在。
如果第一个匹配的解决方案产生一组没有主管分配的项目，就会发生这种情况。
解决此问题的一种可能方法是系统地搜索可能项目的子集，直到存在解决方案（请参阅下面的修剪。）
修剪解决方案
如果学生对主题的某些分配不利，则防止该解决方案成为可能的一种简单方法是将学生主题分配的权重设置得非常高（无穷大）。这提供了一种结构化的方法来修剪不需要的配对：
- 求解加权二分匹配
- 识别不良的学生主题配对
- 将权重设置为无穷大或删除学生-主题配对之间的边，解决。
效率
这里 python 与 networkx 一起使用来优化原型制作能力 而不是 效率。如果您希望将此解决方案扩展到大型问题规模，我会推荐柠檬 MCF 库（特别是成本扩展 MCF algorithm) or Andrew V Goldberg's original cost-scaling MCF algorithm implementation.
根据我对 MCF 进行基准测试的经验，这是两个最具竞争力的实现。我没有 Google-OR 实施 MCF 的经验。
这是一个（更正确的）答案，基于与上一个答案相同的方法，但是，它作为单个加权二分匹配解决了整个问题。
与上一个答案相同的注意事项；但是，如果存在，此答案将找到答案。但是，它必须以最终解决方案中使用的项目数量为条件，因此它可以为使用的不同数量的项目找到多个“好的”解决方案（如果一个项目有 1 个或多个学生，则认为该项目已使用。）
#!/usr/bin/python
"""
filename: student_assign.py
purpose: demonstrate that the problem described in
can be solved as an instance of MCF.
"""
import networkx as nx
# For this demonstration we take data directly from the problem description
#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
supervisors = {
'L1' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 2},
'L2' : { 'topics' : ['P5', 'P2', 'P9'], 'num_groups' : 1},
'L3' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 1},
'L4' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 4},
'L5' : { 'topics' : ['SP1', 'P3', 'P8'], 'num_groups' : 3},
'L6' : { 'topics' : ['P32', 'P3', 'P40'], 'num_groups' : 3},
}
all_topics = sorted(list({ t for s in supervisors for t in supervisors[s]['topics'] }))
# assuming there is a typo in the problem specification and 'supervisor' = 'student' below
#supervisor | 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 |
#S6 | P9 | P1 | SP1 | P5 |
students = {
'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'] ,
'S6' : ['P9', 'P1', 'SP1', 'P5'] ,
}
MAX_GROUP_SIZE = 2
def get_student_topic_supervisor_assignments(all_topics,students,supervisors,num_topics_used,max_group_size=MAX_GROUP_SIZE,do_supervisor_load_balancing=False):
G = nx.DiGraph()
G.add_node('sink',demand=len(students) - num_topics_used)
for topic in all_topics:
G.add_node(topic)
G.add_edge(topic, 'sink', weight = 0, capacity = max_group_size-1)
for student in students:
prefs = students[student]
G.add_node(student,demand=-1)
# add increasing weight edges from student to preferences (lowest == best)
for i, topic in enumerate(prefs):
G.add_edge(student, topic, weight = i, capacity = 1)
G.add_node('sink_2',demand=num_topics_used)
for topic in all_topics:
G.add_node(topic + "_2")
G.add_edge(topic, topic + "_2", weight = 0, capacity = 1 )
for supervisor in supervisors:
supervisor_properties = supervisors[supervisor]
for topic in supervisor_properties['topics']:
G.add_edge(topic + "_2", supervisor, weight = 0, capacity = 1)
if do_supervisor_load_balancing:
for i in range(supervisor_properties['num_groups']):
G.add_node(supervisor + "_dummy")
G.add_edge(supervisor, supervisor + "_dummy", weight = i, capacity = 1)
G.add_edge(supervisor + "_dummy", 'sink_2', weight = 0, capacity = 1)
else:
G.add_edge(supervisor, 'sink_2', weight = 0, capacity = supervisor_properties['num_groups'])
# solve the weighted matching
flow_dict = nx.min_cost_flow(G)
for topic in all_topics:
edges = flow_dict[topic]
if edges['sink'] and not edges[topic+"_2"]:
raise RuntimeError('Solution with num_topics_used={n} is not valid.'.format(n=num_topics_used))
# decode solution
topic_assignments = {t : [] for t in all_topics}
for student in students:
edges = flow_dict[student]
for target in edges:
if edges[target]:
topic_assignments[target].append(student)
break
supervisor_assignments = {s : [] for s in supervisors}
for topic in all_topics:
edges = flow_dict[topic+"_2"]
for target in edges:
if edges[target]:
supervisor_assignments[target].append(topic)
return topic_assignments, supervisor_assignments
num_students = len(students)
for n in range(1,num_students+1):
try:
topic_assignments, supervisor_assignments =\
get_student_topic_supervisor_assignments(all_topics,students,supervisors,num_topics_used=n)
print ' An optimal solution was found with `num_topics_used`={n}'.format(n=n)
print ' Topic assignments:\n', topic_assignments
print ' Supervisor assignments:\n', supervisor_assignments
except Exception as e:
pass
这输出：
An optimal solution was found with `num_topics_used`=4
Topic assignments:
{'P2': [], 'P3': ['S3'], 'P1': ['S2', 'S4'], 'P4': ['S1', 'S5'], 'P5': [], 'SP1': [], 'P8': [], 'P9': ['S6'], 'P32': [], 'P40': []}
Supervisor assignments:
{'L6': ['P3'], 'L4': ['P4'], 'L5': [], 'L2': ['P9'], 'L3': ['P1'], 'L1': []}
An optimal solution was found with `num_topics_used`=5
Topic assignments:
{'P2': [], 'P3': ['S3'], 'P1': ['S2'], 'P4': ['S1', 'S4'], 'P5': [], 'SP1': [], 'P8': [], 'P9': ['S6'], 'P32': ['S5'], 'P40': []}
Supervisor assignments:
{'L6': ['P3', 'P32'], 'L4': ['P1'], 'L5': [], 'L2': ['P9'], 'L3': ['P4'], 'L1': []}
An optimal solution was found with `num_topics_used`=6
Topic assignments:
{'P2': [], 'P3': ['S3'], 'P1': ['S2'], 'P4': ['S4'], 'P5': [], 'SP1': ['S1'], 'P8': [], 'P9': ['S6'], 'P32': ['S5'], 'P40': []}
Supervisor assignments:
{'L6': ['P3', 'P32'], 'L4': ['P1'], 'L5': ['SP1'], 'L2': ['P9'], 'L3': ['P4'], 'L1': []}
主管负载平衡
此解决方案的更新向函数 do_supervisor_load_balancing 添加了一个额外参数，该参数（当设置为 true 时）将更喜欢分配给每个主管的主题数量相似的解决方案。
请注意，使用负载平衡可能会使两个标准不一致：
- 平衡主管负载
- 让学生优先选择他们从事的项目
将一个的权重设置为高于另一个（一个数量级）将确保标准的权重更高。就目前而言，此处提供的解决方案对这两个标准给予了大致相同的权重。
在上面的示例中，当使用负载平衡时，输出如下：
An optimal solution was found with `num_topics_used`=4
Topic assignments:
{'P2': [], 'P3': ['S3'], 'P1': ['S2', 'S4'], 'P4': ['S1', 'S5'], 'P5': [], 'SP1': [], 'P8': [], 'P9': ['S6'], 'P32': [], 'P40': []}
Supervisor assignments:
{'L6': ['P3'], 'L4': [], 'L5': [], 'L2': ['P9'], 'L3': ['P4'], 'L1': ['P1']}
An optimal solution was found with `num_topics_used`=5
Topic assignments:
{'P2': [], 'P3': ['S3'], 'P1': ['S2'], 'P4': ['S1', 'S4'], 'P5': [], 'SP1': [], 'P8': [], 'P9': ['S6'], 'P32': ['S5'], 'P40': []}
Supervisor assignments:
{'L6': ['P32'], 'L4': [], 'L5': ['P3'], 'L2': ['P9'], 'L3': ['P4'], 'L1': ['P1']}
An optimal solution was found with `num_topics_used`=6
Topic assignments:
{'P2': [], 'P3': ['S3'], 'P1': ['S2'], 'P4': ['S4'], 'P5': [], 'SP1': ['S1'], 'P8': [], 'P9': ['S6'], 'P32': ['S5'], 'P40': []}
Supervisor assignments:
{'L6': ['P32'], 'L4': ['P3'], 'L5': ['SP1'], 'L2': ['P9'], 'L3': ['P4'], 'L1': ['P1']}
我正在为一个非营利组织开展一个项目，他们试图帮助有特殊需要的学生适应不同的项目主题。每个学生将有四个偏好，一组导师将有他们监督的主题的偏好列表。
我寻找的解决方案是一种算法，它可以找到将学生与项目主题和导师相匹配的最佳解决方案。
我广泛阅读了 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
- 当我们为学生打开主题时，他们将只能从上面的列表中选择项目，他们 preference/priority。例如
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 ）。
b.将主管分配到他对项目表现出兴趣的小组（理想情况下，每个学生的第一偏好或最匹配的项目）
C。我们需要确保我们不会让主管超负荷，如果主管对 P1, P2, P3 表现出兴趣并提到他只能监督 2 个项目，那么我们应该只将他添加到 2 项目。
到目前为止，我一直在尝试上面解释的算法，但我仍然认为我没有为学生提供合理的解决方案。我更喜欢一种更偏向于学生的解决方案，因为他们有特殊需要。如果有人能给我指出正确的方向，或者能为我提供定义明确的算法或实现，我不仅会感谢您的努力，还会请您喝杯咖啡。
作为一个以做这种事情为生的人来说，这个问题的核心与一个名为“capacitated facility location", which at the scales I imagine you're dealing with can be handled cleanly by integer programming. I can vouch for the free Google OR-Tools 的标准问题非常相似（免责声明：是的，那是我的雇主；不，不是说话为他们），但您还有其他几个免费和付费选项（SCIP、lpsolve、Gurobi、CPLEX）。
整数规划非常好：您声明一些变量，在这些变量上写一些约束和 objective，按下按钮并获得（通常是最优的）解决方案。
这里我们将有以下二进制变量：
对于每一对（学生
i，学生i的潜在项目j），我们有一个0-1变量Assign[i,j]如果该学生做该项目，则为 1，否则为 0。对于每一对（顾问
k，顾问k的潜在项目j），我们有一个0-1变量Avail[k,j]如果该顾问执行该项目，则为 1，否则为 0。
objective是
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 偏向于公平。玩的多，玩的开心。根据要求，这个 objective 不关心我们让顾问做什么。
约束是
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 文档。
希望这是一个足够的开始，当您构建它并且它不可避免地让您失望时，您可以弄清楚如何添加更多约束以防止您不想要的解决方案。祝你好运！
您的问题陈述中存在歧义，根据问题的解决方式，您将更改要使用的算法。歧义以后再讨论。
正如其他人所建议的，这属于组合优化领域，有许多不同的 OR 工具可用于解决这个问题。
首先，我建议使用一系列加权二分匹配和（可能）解决方案修剪。
这是一个用 python 编写的解决方案，使用 networkx 基于两个二分匹配的序列（第一个是针对学生的加权匹配，第二个是未加权的。）
#!/usr/bin/python
"""
filename: student_assign.py
purpose: demonstrate that the problem described in
can be solved as a sequence of assignment problems solved through a weighted bipartite matching.
"""
import networkx as nx
import numpy as np
# For this demonstration we take data directly from the problem description
#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
supervisors = {
'L1' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 2},
'L2' : { 'topics' : ['P5', 'P2', 'P9'], 'num_groups' : 1},
'L3' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 1},
'L4' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 4},
'L5' : { 'topics' : ['SP1', 'P3', 'P8'], 'num_groups' : 3},
'L6' : { 'topics' : ['P32', 'P3', 'P40'], 'num_groups' : 3},
}
all_topics = sorted(list({ t for s in supervisors for t in supervisors[s]['topics'] }))
# assuming there is a typo in the problem specification and 'supervisor' = 'student' below
#supervisor | 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 |
#S6 | P9 | P1 | SP1 | P5 |
students = {
'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'] ,
'S6' : ['P9', 'P1', 'SP1', 'P5'] ,
}
MAX_GROUP_SIZE = 2
def get_student_assignments_to_topics(all_topics,students,max_group_size=MAX_GROUP_SIZE):
G = nx.DiGraph()
G.add_node('sink',demand=len(students))
for topic in all_topics:
G.add_node(topic)
G.add_edge(topic, 'sink', weight = 0, capacity = max_group_size)
for student in students:
prefs = students[student]
G.add_node(student,demand=-1)
# add increasing weight edges from student to preferences (lowest == best)
for i, topic in enumerate(prefs):
G.add_edge(student, topic, weight = i, capacity = 1)
# solve the weighted matching
flow_dict = nx.min_cost_flow(G)
# decode which student is assigned to which topic
student_assignments = { t : [] for t in all_topics}
for student in students:
adjacency = flow_dict[student]
prefs = students[student]
for pref in prefs:
if adjacency[pref]:
student_assignments[pref].append(student)
break
return student_assignments
def get_topic_assignments_to_supervisors(student_assignments,supervisors):
non_empty_student_assignments = { topic : student_assignments[topic] for topic in student_assignments if len(student_assignments[topic]) > 0}
G = nx.DiGraph()
G.add_node('sink',demand=len(non_empty_student_assignments))
for topic in non_empty_student_assignments:
G.add_node(topic,demand=-1)
for supervisor in supervisors:
supervisor_properties = supervisors[supervisor]
for topic in supervisor_properties['topics']:
if topic in non_empty_student_assignments:
G.add_edge(topic, supervisor, weight = 0, capacity = 1)
G.add_edge(supervisor, 'sink', weight = 0, capacity = supervisor_properties['num_groups'])
# solve the unweighted matching
flow_dict = nx.min_cost_flow(G)
# decode which supervisor is assigned to which topic
topic_assignments = { s : [] for s in supervisors}
for supervisor in supervisors:
supervisor_properties = supervisors[supervisor]
for topic in supervisor_properties['topics']:
if topic in non_empty_student_assignments:
adjacency = flow_dict[topic]
if adjacency[supervisor]:
topic_assignments[supervisor].append(topic)
return topic_assignments
# assign students to topics by preference
student_assignments = get_student_assignments_to_topics(all_topics,students)
# assign all topics with at least one student to a supervisor who fits the criteria
topic_assignments = get_topic_assignments_to_supervisors(student_assignments,supervisors)
print 'These are the assignment of students to topics based on preference:'
print student_assignments
print 'These are the assignment of topics to supervisors based on availability:'
print topic_assignments
此脚本输出：
These are the assignment of students to topics based on preference:
{'P2': [], 'P3': ['S3'], 'P1': ['S2', 'S1'], 'P4': ['S5', 'S4'], 'P5': [], 'SP1': [], 'P8': [], 'P9': ['S6'], 'P32': [], 'P40': []}
These are the assignment of topics to supervisors based on availability:
{'L6': [], 'L4': ['P1', 'P3'], 'L5': [], 'L2': ['P9'], 'L3': ['P4'], 'L1': []}
歧义
关于如何处理重要的边缘情况存在歧义：
- 如果学生对主题不感兴趣怎么办？
- 如果一个主题只有一个学生感兴趣怎么办？
- 学生可能必须对所有可能的主题进行排序以确保存在解决方案？
- 主管是否也应该对主题有偏好（如果有，谁的偏好优先？）
- 主管分配给主题的负载是否应该平衡（首选所有主管的工作量相似的解决方案）？
对这些消除歧义的具体问题的回答非常重要，它们将塑造您所设计的解决方案的类型（以及能够向您的算法用户传达优化的内容。）
我绝对建议您花更多时间来消除问题的歧义。
解决方案存在
此处介绍的顺序二分匹配算法将找到最优解；但是，它可能找不到 a 解决方案，即使存在。
如果第一个匹配的解决方案产生一组没有主管分配的项目，就会发生这种情况。
解决此问题的一种可能方法是系统地搜索可能项目的子集，直到存在解决方案（请参阅下面的修剪。）
修剪解决方案
如果学生对主题的某些分配不利，则防止该解决方案成为可能的一种简单方法是将学生主题分配的权重设置得非常高（无穷大）。这提供了一种结构化的方法来修剪不需要的配对：
- 求解加权二分匹配
- 识别不良的学生主题配对
- 将权重设置为无穷大或删除学生-主题配对之间的边，解决。
效率
这里 python 与 networkx 一起使用来优化原型制作能力 而不是 效率。如果您希望将此解决方案扩展到大型问题规模，我会推荐柠檬 MCF 库（特别是成本扩展 MCF algorithm) or Andrew V Goldberg's original cost-scaling MCF algorithm implementation.
根据我对 MCF 进行基准测试的经验，这是两个最具竞争力的实现。我没有 Google-OR 实施 MCF 的经验。
这是一个（更正确的）答案，基于与上一个答案相同的方法，但是，它作为单个加权二分匹配解决了整个问题。
与上一个答案相同的注意事项；但是，如果存在，此答案将找到答案。但是，它必须以最终解决方案中使用的项目数量为条件，因此它可以为使用的不同数量的项目找到多个“好的”解决方案（如果一个项目有 1 个或多个学生，则认为该项目已使用。）
#!/usr/bin/python
"""
filename: student_assign.py
purpose: demonstrate that the problem described in
can be solved as an instance of MCF.
"""
import networkx as nx
# For this demonstration we take data directly from the problem description
#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
supervisors = {
'L1' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 2},
'L2' : { 'topics' : ['P5', 'P2', 'P9'], 'num_groups' : 1},
'L3' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 1},
'L4' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 4},
'L5' : { 'topics' : ['SP1', 'P3', 'P8'], 'num_groups' : 3},
'L6' : { 'topics' : ['P32', 'P3', 'P40'], 'num_groups' : 3},
}
all_topics = sorted(list({ t for s in supervisors for t in supervisors[s]['topics'] }))
# assuming there is a typo in the problem specification and 'supervisor' = 'student' below
#supervisor | 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 |
#S6 | P9 | P1 | SP1 | P5 |
students = {
'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'] ,
'S6' : ['P9', 'P1', 'SP1', 'P5'] ,
}
MAX_GROUP_SIZE = 2
def get_student_topic_supervisor_assignments(all_topics,students,supervisors,num_topics_used,max_group_size=MAX_GROUP_SIZE,do_supervisor_load_balancing=False):
G = nx.DiGraph()
G.add_node('sink',demand=len(students) - num_topics_used)
for topic in all_topics:
G.add_node(topic)
G.add_edge(topic, 'sink', weight = 0, capacity = max_group_size-1)
for student in students:
prefs = students[student]
G.add_node(student,demand=-1)
# add increasing weight edges from student to preferences (lowest == best)
for i, topic in enumerate(prefs):
G.add_edge(student, topic, weight = i, capacity = 1)
G.add_node('sink_2',demand=num_topics_used)
for topic in all_topics:
G.add_node(topic + "_2")
G.add_edge(topic, topic + "_2", weight = 0, capacity = 1 )
for supervisor in supervisors:
supervisor_properties = supervisors[supervisor]
for topic in supervisor_properties['topics']:
G.add_edge(topic + "_2", supervisor, weight = 0, capacity = 1)
if do_supervisor_load_balancing:
for i in range(supervisor_properties['num_groups']):
G.add_node(supervisor + "_dummy")
G.add_edge(supervisor, supervisor + "_dummy", weight = i, capacity = 1)
G.add_edge(supervisor + "_dummy", 'sink_2', weight = 0, capacity = 1)
else:
G.add_edge(supervisor, 'sink_2', weight = 0, capacity = supervisor_properties['num_groups'])
# solve the weighted matching
flow_dict = nx.min_cost_flow(G)
for topic in all_topics:
edges = flow_dict[topic]
if edges['sink'] and not edges[topic+"_2"]:
raise RuntimeError('Solution with num_topics_used={n} is not valid.'.format(n=num_topics_used))
# decode solution
topic_assignments = {t : [] for t in all_topics}
for student in students:
edges = flow_dict[student]
for target in edges:
if edges[target]:
topic_assignments[target].append(student)
break
supervisor_assignments = {s : [] for s in supervisors}
for topic in all_topics:
edges = flow_dict[topic+"_2"]
for target in edges:
if edges[target]:
supervisor_assignments[target].append(topic)
return topic_assignments, supervisor_assignments
num_students = len(students)
for n in range(1,num_students+1):
try:
topic_assignments, supervisor_assignments =\
get_student_topic_supervisor_assignments(all_topics,students,supervisors,num_topics_used=n)
print ' An optimal solution was found with `num_topics_used`={n}'.format(n=n)
print ' Topic assignments:\n', topic_assignments
print ' Supervisor assignments:\n', supervisor_assignments
except Exception as e:
pass
这输出：
An optimal solution was found with `num_topics_used`=4
Topic assignments:
{'P2': [], 'P3': ['S3'], 'P1': ['S2', 'S4'], 'P4': ['S1', 'S5'], 'P5': [], 'SP1': [], 'P8': [], 'P9': ['S6'], 'P32': [], 'P40': []}
Supervisor assignments:
{'L6': ['P3'], 'L4': ['P4'], 'L5': [], 'L2': ['P9'], 'L3': ['P1'], 'L1': []}
An optimal solution was found with `num_topics_used`=5
Topic assignments:
{'P2': [], 'P3': ['S3'], 'P1': ['S2'], 'P4': ['S1', 'S4'], 'P5': [], 'SP1': [], 'P8': [], 'P9': ['S6'], 'P32': ['S5'], 'P40': []}
Supervisor assignments:
{'L6': ['P3', 'P32'], 'L4': ['P1'], 'L5': [], 'L2': ['P9'], 'L3': ['P4'], 'L1': []}
An optimal solution was found with `num_topics_used`=6
Topic assignments:
{'P2': [], 'P3': ['S3'], 'P1': ['S2'], 'P4': ['S4'], 'P5': [], 'SP1': ['S1'], 'P8': [], 'P9': ['S6'], 'P32': ['S5'], 'P40': []}
Supervisor assignments:
{'L6': ['P3', 'P32'], 'L4': ['P1'], 'L5': ['SP1'], 'L2': ['P9'], 'L3': ['P4'], 'L1': []}
主管负载平衡
此解决方案的更新向函数 do_supervisor_load_balancing 添加了一个额外参数，该参数（当设置为 true 时）将更喜欢分配给每个主管的主题数量相似的解决方案。
请注意，使用负载平衡可能会使两个标准不一致：
- 平衡主管负载
- 让学生优先选择他们从事的项目
将一个的权重设置为高于另一个（一个数量级）将确保标准的权重更高。就目前而言，此处提供的解决方案对这两个标准给予了大致相同的权重。
在上面的示例中，当使用负载平衡时，输出如下：
An optimal solution was found with `num_topics_used`=4
Topic assignments:
{'P2': [], 'P3': ['S3'], 'P1': ['S2', 'S4'], 'P4': ['S1', 'S5'], 'P5': [], 'SP1': [], 'P8': [], 'P9': ['S6'], 'P32': [], 'P40': []}
Supervisor assignments:
{'L6': ['P3'], 'L4': [], 'L5': [], 'L2': ['P9'], 'L3': ['P4'], 'L1': ['P1']}
An optimal solution was found with `num_topics_used`=5
Topic assignments:
{'P2': [], 'P3': ['S3'], 'P1': ['S2'], 'P4': ['S1', 'S4'], 'P5': [], 'SP1': [], 'P8': [], 'P9': ['S6'], 'P32': ['S5'], 'P40': []}
Supervisor assignments:
{'L6': ['P32'], 'L4': [], 'L5': ['P3'], 'L2': ['P9'], 'L3': ['P4'], 'L1': ['P1']}
An optimal solution was found with `num_topics_used`=6
Topic assignments:
{'P2': [], 'P3': ['S3'], 'P1': ['S2'], 'P4': ['S4'], 'P5': [], 'SP1': ['S1'], 'P8': [], 'P9': ['S6'], 'P32': ['S5'], 'P40': []}
Supervisor assignments:
{'L6': ['P32'], 'L4': ['P3'], 'L5': ['SP1'], 'L2': ['P9'], 'L3': ['P4'], 'L1': ['P1']}