c++ - 循环问题中的 'lower bound'是什么意思？

Question

问题:循环问题允许您对通过特定弧的流量同时设置下限和上限。我理解的上限(就像管道一样，只有这么多东西可以通过)。但是，我很难理解下限的想法。这是什么意思？请问有解决问题的算法吗...

• 尝试确保每个具有下限的弧都至少获得那么大的流量，如果找不到方法就完全失败？
• 如果不能满足下界，就简单地忽略弧吗？这对我来说更有意义，但意味着结果图中可能存在流量为 0 的弧，即

上下文:我试图找到一种方法来快速安排一组事件，每个事件都有一个长度和一组可以安排的可能时间。我试图将此问题简化为循环问题，对此存在有效的算法。

我将每个事件作为一个节点放在有向图中，并为其提供它应该填充的时隙数量。然后我将所有可能的时间也添加为节点，最后添加所有时隙，如下所示(所有弧都指向右侧):

前两个事件有一个可能的时间和长度为 1，最后一个事件的长度为 4 和两个可能的时间。

这张图有意义吗？更具体地说，“填充”的时隙数量是 2 个(仅“简单”的)还是 6 个，如图所示？

(我正在使用 LEMON 库中的推送重新标记算法，如果这有任何区别的话。)

Answer 1

关于大循环问题:

我同意@Helen；尽管设想实际使用下限可能不是那么直观，但它是必须满足的约束。我不相信您能够忽略此约束，即使该流量为零。

flow = 0 的情况吸引了更直观的最大流量问题(正如@KillianDS 所指出的)。在那种情况下，如果一对节点之间的流量为零，则它们不会影响“流量和守恒”:

当没有给出下限时(假设流是非负的)零流不能影响结果，因为

1. 不能违反约束条件
2. 它不会影响总和(因为它添加了一个零项)。

由于某些外部约束，可能存在最小流量的实际示例(相关问题需要至少 X 水通过某个管道，正如@Helen 所指出的)。下限约束也可能来自等效的对偶问题，该问题最小化流，使得某些边缘具有下限(并找到与具有上限的最大化问题等效的最优值)。

针对您的具体问题:

您似乎正试图在一组固定的时间段内完成尽可能多的事件(其中任何两个事件都不能在一个时间段内重叠)。

考虑可以分配给给定事件的时间段集:

E1 -- { 9:10 }
E2 -- { 9:00 }
E3 -- { 9:20, 9:30, 9:40, 9:50 }
E3 -- { 9:00, 9:10, 9:20, 9:30 }

所以你想最大化任务分配的数量(即事件事件发生在被“打开”的边上)s.t.结果集是成对不相交的(即没有分配的时隙重叠)。

我相信这是 NP-Hard 因为如果你能解决这个问题，你就可以用它来解决 maximal set packing problem (即最大集合包装减少到这个)。你的问题可以用整数线性规划来解决，但实际上这些问题也可以用贪心法/分支定界法很好地解决。

例如，在您的示例问题中。事件 E1 与 E3 “冲突”，E2 与 E3 冲突。如果E1被赋值(只有一个选项)，那么E3就只剩下一个可能的赋值(后面的赋值)。如果为 E3 进行了此分配，则 E2 仅剩下一个分配。此外，可以单独解决不相交的子图(不可能在资源上发生冲突的事件集)。

如果是我，我会从一个非常简单的贪婪解决方案开始(首先分配具有较少可能“插槽”的任务)，然后将其用作分支定界求解器的种子(如果贪婪解决方案找到 4 个任务赋值，然后如果你的赋值的递归子树不能超过 3)。您甚至可以通过创建集合之间的成对交集图并仅在进行分配时通知相邻集合来挤出一些额外的性能。您还可以在继续分支定界时更新分配的最佳数量(我认为这很正常)，所以如果您运气好的话，您会很快收敛。

我用同样的想法找到了可以解释一组已识别肽(蛋白质片段)的最小蛋白质组，并发现它足以解决实际问题。这是一个非常相似的问题。

如果您需要最先进的性能:换句话说，整数线性规划几乎可以解决您喜欢的这个问题的任何变体。当然，在非常糟糕的情况下它可能会很慢(实际上，它可能对你有用，特别是如果你的图不是非常密集地连接)。如果不是，则常规线性规划松弛近似于 ILP 的解决方案并且通常非常适合此类问题。

希望这对您有所帮助。