Hi There,

I'm playing with FindMinimumCostFlow with constrained edge capacities. It doesn't seem to work as I would expect. If I assign EdgeCapacity within a Graph and try to use the option

EdgeCapacity->Automatic

in FindMinimumCostFlow, Mathematica appears to ignore this option and assume capacities are infinite.

It does work when I explicitly assign EdgeCapacity within FindMinimumFlowCost, however I get inconsistent results. As an example, I created a very simple graph where one path has half the capacity of the other;

edgeCapacity = {1, 2, 2, 1};

es = {1 [DirectedEdge] 2, 1 [DirectedEdge] 3, 3 [DirectedEdge] 4, 
   2 [DirectedEdge] 4};

g3 = Graph[,
  VertexLabels -> "Name",
  EdgeLabels -> Table[es[[ii]] -> edgeCapacity[[ii]], {ii, 1, 4}]
  ];

When I use FindMinimumCostFlow to get the minimum cost between nodes 3 and 4 it fails for demands on node 4 greater than one, even though the capacity of edge 3->4 is 2

mc = FindMinimumCostFlow[g3, {0, 0, 20, -1.1}, "OptimumFlowData",
  EdgeCapacity -> edgeCapacity]; mc["CostValue"] (*Fail*)

Apparently, this has something to do with the ordering in which I input the nodes - as if the function were sorting by the first element. When I do the corresponding re-ordering the results make sense. I checked whether EdgeList and VertexList orderings are the same as the input and that's ok.

I'm attaching a notebook with a full description of what I'm observing.

Am I doing something wrong?

All the best

Attachments: