不优化路线的最小成本流

Question

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

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

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

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

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

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

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

我如何使用 OR-Tools 来完成此操作？

Answer 1

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

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