这个会议安排的场景是否有一个被广泛理解的算法或解决方案模型？

Question

输入:

• 由开始时间、结束时间和地点定义的N个时间事件日历。
• 每个会议场所的容量（可以同时容纳的最大人数）。
• 一组表示与会者Ai希望与参加者Aj会面并且Aj接受了邀请的配对（Ai，Aj）。

输出:

• 对于每个助手A，列出他将参加的所有活动计划表。主要标准是使每个参与者与尽可能多接受其邀请的参与者会面，满足空间限制。

如果Ai已经在某个事件中与Aj见面，则他们不需要再次见面（因为他们已经见过面）。目前我们考虑使用回溯法（尝试所有可能的解决方案）和线性规划（即定义模型并使用单纯形算法求解）来解决问题。

- dario_ramos

---

可以有两个以上的人同时参加会议，还是只能一对一地进行会议？ - Mahmoud Al-Qudsi

这符合一类算法的标准：拍卖类算法。 - jim mcnamara

每个会议室可以容纳多人的事实表明，您可以同时举行多人会议。 - btilly

谷歌搜索“排课算法”。 - Michael Slade

@MichaelSlade 你确定排课足够接近了吗？ - Victor P.

Answer 1

你的问题就像区间图中的最小最大匹配问题一样困难，假设房间容量为2，这意味着它们只能同时处理一个会议。你可以使用区间图来模拟你的问题，每个时间段（每个人）是一个节点。如果A_i和A_j有共同的时间并且他们也想见面，那么将边的权重设置为他们应该见面的时间量。如果在这个图中找到了最小的最大匹配，就可以找到受限制情况下的解决方案。但请注意，这个图是n部分图，而且每个部分都是区间图。

附注：请注意，如果人们应该在一起的时间固定，那么这将比加权问题更容易。

- Saeed Amiri

---

我在问题中添加了一个约束条件。你能展示一下如何从输入数据设置图形的小例子吗？与此同时，我会尝试理解最小最大匹配理论（我在大学学过离散数学-图论-课程，但这超出了那个范围）。 - dario_ramos

@dario_ramos，我用图形建模了你的受限版本（放宽了你的问题），这并不难。首先将可能的时间段设置为图形的节点，然后连接两个节点，如果它们属于应该相互查看的两个不同人，并且它们的相关时间段有一些重叠。做到这一步，如果你对此有很好的直觉，我会说更多的细节。 - Saeed Amiri

Answer 2

如果您可以访问一个好的MIP求解器（通过acedamic计划使用cplex/gurobi，但coin OR和LP_solve是开源的，也不错），我建议您一定要尝试simplex算法。我查看了将您的问题制定为混合整数规划的方式，我的感觉是它将具有相当强的松弛度，因此分支定界和价格算法对您来说将非常有用。这些求解器现在提供了非常可扩展的解决方案，特别是商业求解器。优点是它们还提供上限，因此您可以了解解决方案的质量，这对于启发式算法并不适用。

制定：

定义z（i，j）（二进制）作为变量，表示i和j至少在1,2, ...，N中的一个事件n中在一起。 定义z（i，j，n）（二进制）表示他们在事件n中在一起。 定义z（i，n）表示i参加n。 只有当i和j应该见面时，z（i，j）和z（i，j，m）才存在。

对于每个t，M ^ t是同时举行的时间事件的子集。 因此，如果事件1从9到11，事件2从10到12，事件3从11到13，则 M ^ 1 = {事件1，事件2}，M ^ 2 = {事件2，事件3}。即没有人可以同时参加1和2，或者2和3，但可以同时参加1和3。

Max sum Z(i,j)                      

z(i,j)<= sum_m z(i,j,m)   
(every i,j)(i and j can meet if they are in the same location m at least once)

z(i,j,m)<= z(i,m)   (for every i,j,m) 
(if i and j attend m, then i attends m)

z(i,j,m)<= z(j,m)     (for every i,j,m) 
(if i and j attend m, then j attends m)

sum_i z(i,m) <= C(m)   (for every m) 
(only C(m) persons can visit event m)

sum_(m in M^t) z(i,m) <= 1  (for every t and i)  
(if m and m' are both overlapping time t, then no person can visit them both. )

- willem

---

LPSolve 的好处在于他们有一个非常好的雅虎社区。顺便问一下，你的问题规模是多少？ - willem

参与者人数在百位数级别，房间数量在十位数级别，活动持续1个月，每次活动时长为1-3小时。 - dario_ramos

Answer 3

正如@SaeedAmiri所指出的那样，这看起来是一个复杂的问题。

我猜测，当助手数量增加到几十个时（可能在这个数量级），您正在考虑的回溯和线性规划选项将会失效。

如果不需要最优解，也许您应该考虑一种（元）启发式方法，或者使用约束编程构建一个初始模型并查看其扩展性。

为了给您一个更精确的答案，您为什么需要解决这个问题？参与者的典型数量是多少？房间数量呢？

- Victor P.

---

使用启发式方法似乎是合理的，因为这个问题似乎是NP难的。我正在研究这些方法，但仍然无法设计出一个好的方法。参与者数量在数百人左右，房间数量在十个左右，活动在一个月内持续1-3小时。 - dario_ramos

我认为你面临着一个相当大的问题，如果你从实际角度考虑，我建议你首先设计一种有建设性的启发式算法来构建可行解决方案。 然后，我认为大邻域搜索（LNS）是一个很好的开始，因为它的实现非常直接：对于给定数量的迭代，您将从日程安排中删除会议，然后尝试重新插入它们。 - Victor P.

我们最终实现了一种特别的启发式方法，我不确定它是否符合LNS类别。@Saeed Amiri基于图论的答案看起来很有前途，但我们没有时间去深入研究理论。我们的解决方案在给定问题规模下运行时间为毫秒级，并且似乎对于更大的规模也能很好地扩展，尽管我们没有进行过太彻底的测试。 - dario_ramos