c# - 最小成本流未优化路线

Question

我正在尝试使用 OR-Tools 中的 MinCostFlow 解决工程问题。有一个带有管道和一些供应阀的机械分配系统。这些阀门需要连接到消费者。最初，我试图用匈牙利算法来解决这个问题，但后来我意识到通过路径的流量不被考虑在内。

我用这样的最小成本流对问题进行了建模：

节点 0-4 是消费者，节点 4-7 是供应阀，节点 8 和 9 是管道。我在每个消费者身上放置了一个“供应”，以显示它期望的流量。我在最后放了一个水槽，以便将供应从系统中取出。并非所有消费者都有相同的需求。我们可以看到节点 0 需要 10 个节点，并且我专门设计了一条路径（以红色突出显示），让它可以将它带到那里。我现在已将所有价格设置为 0。

我希望它能像这样解决这个系统：

但是，它实际上是这样解决的：

出于某种原因，它决定将节点 0 拆分为 2 个节点（6 和 7），然后让更大的节点 7 从 3 和 0 接收 5。从系统的角度来看，这并不理想，我不明白为什么它会这样解决。在匈牙利算法中，它不允许一个工人接受一个以上的工作。在该算法中，节点 4-7 将是工人，而 0-3 将是工作。

我可以通过增加从节点 1-3 到节点 7 的弧的成本来获得所需的结果，但我不想操纵成本字段来获得所需的结果。这似乎需要做很多额外的工作来帮助优化工具选择正确的路径。

我如何使用 OR-Tools 来完成此任务？

标签： c#algorithmlinear-programmingor-tools

Answer 1

为了简单起见，只要您希望求解器选择一条路径，它就变成了 NP 完全。Min Cost Flow 是多项式的，根据定义，它将跨弧分割流，而不是选择另一个。

你想要的是一个整数线性问题。您可以使用 CP-SAT 求解器或使用 CBC 的线性求解器包装器或 CP-SAT 作为后端来求解它。