最小成本流不优化路线
Minimum Cost Flow not optimizing routes
我正在尝试使用 OR-Tools 中的 MinCostFlow 解决工程问题。有一个带有管道和许多供应阀的机械分配系统。这些阀门需要连接到消费者。本来我是想用匈牙利算法解决这个问题，后来发现这个不考虑通过路径的流量
我用这样的最小成本流为问题建模：
节点 0-4 是消费者，节点 4-7 是供水阀，节点 8 和 9 是管道。我在每个消费者上放了一个 "supply" 来显示它期望的流量。我在最后放了一个水槽以从系统中取出供应。并非所有消费者都有相同的需求。我们可以看到节点 0 需要 10，我专门设计了一条路径（以红色突出显示），允许它携带它到那里。我暂时把所有价格都设为0了。
我希望它能像这样解决这个系统：
然而实际上是这样解决的：
出于某种原因，它决定将节点 0 拆分为 2 个节点（6 和 7），然后让更大的节点 7 从 3 和 0 接收 5。从系统的角度来看，这并不理想，我不不明白为什么会这样解决。在匈牙利算法中，不允许一个 Worker 接受多个 Job。在该算法中，节点 4-7 将是工人，而 0-3 将是工作。
我可以通过增加从节点 1-3 到节点 7 的弧的成本来获得所需的结果，但我不想操纵成本字段来获得所需的结果。这似乎需要做很多额外的工作来帮助优化工具 select 走上正确的道路。
如何使用 OR-Tools 来完成此操作？
为了简单起见，只要你想让求解器选择一条路径，它就变成了NP完全。
Min Cost Flow 是多项式的，根据定义，它将跨弧分割流，而不是选择另一个。
你要的是整数线性问题。您可以使用 CP-SAT 求解器或使用 CBC 的线性求解器包装器或 CP-SAT 作为后端来求解它。
我正在尝试使用 OR-Tools 中的 MinCostFlow 解决工程问题。有一个带有管道和许多供应阀的机械分配系统。这些阀门需要连接到消费者。本来我是想用匈牙利算法解决这个问题，后来发现这个不考虑通过路径的流量
我用这样的最小成本流为问题建模：
节点 0-4 是消费者，节点 4-7 是供水阀，节点 8 和 9 是管道。我在每个消费者上放了一个 "supply" 来显示它期望的流量。我在最后放了一个水槽以从系统中取出供应。并非所有消费者都有相同的需求。我们可以看到节点 0 需要 10，我专门设计了一条路径（以红色突出显示），允许它携带它到那里。我暂时把所有价格都设为0了。
我希望它能像这样解决这个系统：
然而实际上是这样解决的：
出于某种原因，它决定将节点 0 拆分为 2 个节点（6 和 7），然后让更大的节点 7 从 3 和 0 接收 5。从系统的角度来看，这并不理想，我不不明白为什么会这样解决。在匈牙利算法中，不允许一个 Worker 接受多个 Job。在该算法中，节点 4-7 将是工人，而 0-3 将是工作。
我可以通过增加从节点 1-3 到节点 7 的弧的成本来获得所需的结果，但我不想操纵成本字段来获得所需的结果。这似乎需要做很多额外的工作来帮助优化工具 select 走上正确的道路。
如何使用 OR-Tools 来完成此操作？
为了简单起见，只要你想让求解器选择一条路径，它就变成了NP完全。 Min Cost Flow 是多项式的，根据定义，它将跨弧分割流，而不是选择另一个。
你要的是整数线性问题。您可以使用 CP-SAT 求解器或使用 CBC 的线性求解器包装器或 CP-SAT 作为后端来求解它。