2

假设我有一群学生和几个教授。每个学生都需要与其中一位教授进行口试。为此，每个学生都会提供一份（有序的）名单，其中包括他更愿意与他一起参加考试的三位教授。当然，每位教授只能进行有限数量的考试。我可以使用 Kuhn-Munkres 算法来计算一个作业，将尽可能多的学生分配给他们的第一个愿望教授。

现在假设每个学生必须参加两次考试，并相应地提供两个愿望清单。再次，我想将尽可能多的学生分配给他们的第一个愿望教授，但受制于学生不得与同一位教授一起参加两次考试。

是否有一些算法可以有效地计算最佳分配？也许是 Kuhn-Munkres 算法的推广？还是这个新问题已经是 NP 难的？可以尝试将哪些难题简化为这一难题？

我应该强调我正在寻找一个确切的解决方案。很容易想到一些启发式方法，例如考虑一种又一种类型的考试。

4

2 回答 2

2

您可以使用整数编程作为分配问题来精确建模。

变量

让有s个学生和p个教授。

决策变量

  X_sp is 1 if student s takes an exam with professor p
          0 otherwise

 Let Limit_p be the number of exams that professor p can handle.

处理学生偏好

我们可以通过成本处理每个学生的偏好（目标）

Let C_sp be the 'cost' of assigning student s to take an exam with professor p.

随着偏好的降低，我们会不断提高成本。

C_sp = 1 if p is the *first* preference of s
C_sp = 2 if p is the *second* preference of s
C_sp = 3 if p is the *third* preference of s
...
C_sp = n if p is the *n th* preference of s

公式

案例一：一场考试

 Min (sum over s)(sum over p) C_sp X_sp

 subject to:
 (sum over p) X_sp = 1 for each student s   # Every student must take an exam
 (sum over s) X_sp <= Limit_p for each professor p   # Every prof can only handle so many exams

 X_sp = {0,1} # binary

案例2：学生参加两次考试

 Min (sum over s)(sum over p) C_sp X_sp

 subject to:
 (sum over p) X_sp = 2 for each student s   # Every student must take an exam
 (sum over s) X_sp <= Limit_p for each professor p   # Every prof can only handle so many exams

 X_sp = {0,1} # binary

照顾没有学生可以和同一个教授一起参加两个考试

通常，我们必须引入指示变量 Y_sp来表示学生是否参加过 p 教授的考试。但是，在这种情况下，我们甚至不必这样做。二进制的事实X_sp将确保没有学生最终与同一位教授一起参加 2 次考试。

如果学生对他们想与教授一起参加的考试有偏好，e则需要在决策变量中添加下标。X_spe

您可以通过匈牙利方法解决这个问题，或者更简单的是，任何可用的 LP/IP 求解器实现。

匈牙利算法的复杂度为 O(n^3)，并且由于我们没有引入任何边约束来破坏完整性属性，因此线性解将始终是整数。

更新（一点理论）

为什么解决方案是不可或缺的？要理解为什么解决方案可以保证是完整的，需要一点理论知识。

通常，当遇到 IP 时，首先想到的是尝试解决线性松弛（忘记积分值要求并尝试。）这将为最小化问题提供下限。通常有一些所谓的复杂约束使得整数解很难找到。一种解决技术是通过将它们抛给目标函数来放松它们，并解决更简单的问题（拉格朗日松弛问题）。

现在，如果拉格朗日的解决方案不会改变您是否具有完整性（就像分配问题的情况一样），那么您总是会得到整数解决方案。

对于那些真正有兴趣了解 Integrality 和 Lagrangian duals 的人来说，这个参考资料非常易读。第 3 节中的示例专门涵盖了分配问题。

免费 MILP 求解器： 这个 SO 问题对此非常详尽。

希望有帮助。

于 2013-07-05T17:11:14.890 回答
1

我认为你可以通过解决最小成本流问题来最佳地解决这个问题。

下面的 Python 代码说明了如何使用 networkx 库为 3 名学生完成此操作。

import networkx as nx

G=nx.DiGraph()

multiple_prefs=[{'Tom':['Prof1','Prof2','Prof3'],
       'Dick':['Prof2','Prof1','Prof3'],
       'Harry':['Prof1','Prof3','Prof1']},

       {'Tom':['Prof2','Prof1','Prof3'],
       'Dick':['Prof2','Prof1','Prof3'],
       'Harry':['Prof1','Prof3','Prof1']}
       ]

workload={'Prof1':2,'Prof2':10,'Prof3':4}

num_tests=len(multiple_prefs)
num_students=len(multiple_prefs[0])
G.add_node('dest',demand=num_tests*num_students)
A=[]
for i,prefs in enumerate(multiple_prefs):
    testname='_test%d'%i
    for student,proflist in prefs.items():
        node=student+testname
        A.append(node)
        G.add_node(node,demand=-1)
        for i,prof in enumerate(proflist):
            if i==0:
                cost=0 # happy to assign first choices
            elif i==1:
                cost=1 # Slightly unhappy to assign second choices
            else:
                cost=4 # Very unhappy to assign third choices
            n2=prof+'_with_'+student
            n3=prof
            G.add_edge(node,n2,capacity=1,weight=cost) # Edge taken if student takes this test with the professor
            G.add_edge(n2,n3,capacity=1,weight=0) # Capacity stops student taking both tests with the same professor
            G.add_edge(n3,'dest',capacity=workload[prof],weight=0) # Capacity stops professor exceeding his workload


flowdict = nx.min_cost_flow(G)
for student in A:
    for prof,flow in flowdict[student].items():
        if flow:
            print student,'with',prof

关键是我们为学生和教授的每个组合都有一个单独的节点（在代码中称为 n2）。通过将 n2 的容量设为 1，我们确保每个学生只能与该教授一起参加一次测试。

字典 multiple_prefs 存储两个字典。第一个字典包含每个学生第一次测试的偏好列表。第二个有第二个测试的偏好。

编辑

该代码现在还包括每个教授的节点 n3。这些节点和 dest 之间边缘的容量将限制每个教授的最大工作量。

字典工作量存储每个教授允许的最大测试数。

于 2013-07-05T13:56:20.263 回答