algorithm - 计算带有附加约束的赋值

Question

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

现在假设每个学生都必须参加两次 考试，因此提供两个愿望 list 。我再次希望将尽可能多的学生分配给他们的第一个希望的教授，但受到限制，即学生不得参加同一位教授的两次考试。

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

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

Answer 1

您可以使用整数编程将其准确建模为 Assignment Problem.

变量

有 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

配方

案例 1:一次考试

 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 求解器实现来解决此问题。

Hungarian algorithm's复杂度为 O(n^3)，并且由于我们没有引入任何边约束来破坏完整性属性，线性解将始终是积分的。

更新(一点理论)

为什么解是积分的？要理解为什么解保证是积分的，需要一点理论知识。

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

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

对于那些真正有兴趣了解积分和拉格朗日对偶的人，this reference is quite readable.第 3 节中的示例专门介绍了分配问题。

免费 MILP 求解器: This SO question is quite exhaustive for that.

希望对您有所帮助。