最低成本流未优化路线 [英] Minimum Cost Flow not optimizing routes

问题描述

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

I am trying to solve an engineering problem using the MinCostFlow in OR-Tools. There is a mechanical distribution system with pipes and a number of supply valves. Those valves need to be connected to consumers. Originally, I was trying to solve this with the Hungarian Algorithm, but then I realized that the flow through the path is not considered by this.

我使用最小成本流对问题进行了建模，如下所示:

I have modeled the problem with a Min Cost Flow like this:

节点0-4是使用者，节点4-7是供水阀，节点8和9是管道.我对每个消费者进行了供应"以显示预期的流量.我在最后放了一个水槽，以便从系统中取出电源.并非所有消费者都有相同的需求.我们可以看到节点0需要10，并且我专门设计了一条路径(用红色突出显示)，可以将其携带到那里.我现在将所有价格都设为0.

Nodes 0-4 are the Consumers, Nodes 4-7 are the supply valves, Nodes 8 and 9 are the pipes. I put a "supply" on each of the consumers to show how much flow it expects. I put a sink at the end to get the supply out of the system. Not all consumers have the same need. We can see Node 0 requires 10, and I have specifically designed a path (highlighted in red) that would allow it to carry it there. I have set all prices to 0 for now.

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

I would expect it to solve this system like this:

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

However, it actually solves it like this:

由于某种原因，它决定将节点0划分为2个节点(6和7)，然后让较大的节点7从3和0接收5.从系统角度来看，这是不理想的，我不认为了解为什么会这样解决.在匈牙利算法中，它不允许工作人员接受多个工作.在该算法中，节点4-7将是Workers，节点0-3将是Jobs.

For some reason, it decides to split Node 0 across 2 Nodes (6 and 7) and then has the bigger Node 7 receiving 5 from both 3 and 0. This is not ideal from a system perspective, and I don't understand why it would solve it this way. In the Hungarian Algorithm, it would not allow a Worker to accept more than one Job. And in that algorithm, Node 4-7 would be Workers and 0-3 would be the Jobs.

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

I can get the desired result by increasing the cost of the arcs from Nodes 1-3 to node 7, but I do not want to manipulate the cost field to get the desired result. This seems like a lot of extra work to help the optimization tool select the right path.

如何使用OR-Tools完成此操作?

How do I use OR-Tools to accomplish this?

推荐答案

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

To make it simple, as soon as you want the solver to choose a path, it becomes NP complete. Min Cost Flow is polynomial, by definition it will split flows across arcs, and not choose one of the other.

您想要的是一个整数线性问题.您可以使用CP-SAT求解器或使用CBC或CP-SAT作为后端的线性求解器包装器对其进行求解.

What you want is a integer linear problem. You can solve it with the CP-SAT solver, or the linear solver wrapper using CBC, or CP-SAT as a backend.

这篇关于最低成本流未优化路线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！