流通问题的"下界"是什么意思？
Wan*_*uta 5 c++ graph-theory directed-graph data-structures
问题:循环问题允许您在通过特定弧的流动中具有下限和上限.我理解的上界(就像管道一样,只有很多东西可以通过).但是,我很难理解下限的想法.这是什么意思？将解决问题的算法...
- 尝试确保每个具有下限的弧将至少获得那么多的流量,如果找不到方法则完全失败？
- 如果不能满足下限,只需忽略弧线？这对我来说更有意义,但是意味着在结果图中可能存在流量为0的弧,即
上下文:我正在尝试找到一种方法来快速安排一组事件,每个事件都有一个长度和一组可能的时间来安排它们.我正在尝试将此问题简化为循环问题,因为存在有效的算法.
我将每个事件都放在有向图中作为一个节点,并为它提供应该填充的时隙量.然后我将所有可能的时间添加为节点,最后添加所有时间段,如下所示(所有弧点指向右侧):
前两个事件具有单个可能的时间和长度1,并且最后一个事件具有4的长度和两个可能的时间.
这个图表有意义吗？更具体地说,"填充"的时隙数量是2(只有'简单')还是6,如图所示？
(如果有任何不同,我正在使用LEMON库中的push-relabel算法.)
关于一般流通问题：
我同意@Helen；尽管下限的实际应用可能并不那么直观，但它是一个必须满足的约束。我不相信你能够忽略这个约束，即使流量为零。
flow = 0 的情况吸引了更直观的最大流量问题（正如@KillianDS 所指出的）。在这种情况下，如果一对节点之间的流量为零，那么它们就不会影响“流量和守恒”：
当没有给出下限时（假设流量非负）零流量不会影响结果，因为
- 它不能违反约束
- 它不能影响总和（因为它添加了零项）。
由于某些外部约束，可能存在最小流量的实际示例（相关问题需要至少 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 }
因此，您希望最大化任务分配的数量（即与“打开”的边缘相关的事件），结果集是成对不相交的（即分配的时隙没有重叠）。
我相信这是 NP-Hard，因为如果你能解决这个问题，你就可以用它来解决最大集包装问题（即最大集包装减少到这个）。你的问题可以用整数线性规划来解决，但实际上这些问题也可以用贪婪方法/分支定界来很好地解决。
例如，在您的示例问题中。事件E1与E3“冲突”，E2与E3“冲突”。如果E1被分配（只有一个选项），那么E3就只剩下一个可能的分配（后面的分配）。如果 E3 接受此分配，则 E2 只剩下一个分配。此外，不相交的子图（不可能在资源上发生冲突的事件集）可以单独解决。
如果是我，我会从一个非常简单的贪婪解决方案开始（首先分配可能“槽”较少的任务），然后将其用作分支定界求解器的种子（如果贪婪解决方案找到 4 个任务分配，则如果分配的递归子树不能超过 3，则绑定。您甚至可以通过创建集合之间的成对交集图并仅在进行分配时通知相邻集合来挤出一些额外的性能。当你继续分支定界时，你还可以更新你的最佳作业数量（我认为这是正常的），所以如果你早点幸运，你会很快收敛。
我用同样的想法找到了可以解释一组已识别肽（蛋白质片段）的最小蛋白质组，并发现它足以解决实际问题。这是一个非常相似的问题。
如果您需要前沿性能： 换句话说，整数线性规划几乎可以解决您想要的该问题的任何变体。当然，在非常糟糕的情况下，它可能会很慢（实际上，它可能对您有用，特别是如果您的图形连接不是很密集）。如果不是，则常规线性规划松弛近似 ILP 的解决方案，并且通常非常适合此类问题。
希望这可以帮助。