0
$\begingroup$

I'm having trouble getting the EdgeCapacity feature in FindMinimumCostFlow to work. I have attached a simple example. We have a simple graph of four vertices. There are two paths from the "source" to the "sink." The EdgeCapacity of all edges is limited to 1 and the total flow from the "source" to the "sink" is 2.

myGraph = Graph[
  {Property[
    "source" \[DirectedEdge] "vA", {EdgeCapacity -> 1, EdgeCost -> 2}],
   Property[
    "vA" \[DirectedEdge] "sink", {EdgeCapacity -> 1, EdgeCost -> 2}],
   Property[
    "source" \[DirectedEdge] "vB", {EdgeCapacity -> 1, EdgeCost -> 1}],
   Property[
    "vB" \[DirectedEdge] "sink", {EdgeCapacity -> 1, EdgeCost -> 1}]}];


sourceSink = 
 ReplaceAll[#, {"source" -> 2, "sink" -> -2, "vA" -> 0, "vB" -> 0}] &@
  VertexList@myGraph;

flow = FindMinimumCostFlow[myGraph, sourceSink, "OptimumFlowData"];

MatrixForm@flow["FlowMatrix"]
  {{0, 0, 0, 2}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 2, 0}}

The result is not what I expected. Since the capacity of each path is 1, I would expect the flow to be evenly split. Instead, it appears to ignore the EdgeCapacity and route all the flow through the path of least resistance.

$\endgroup$
  • $\begingroup$ FindMinimumCostFlow finds A flow of minimum total cost from a set of supply vertices to a set of demand vertices in a graph with capacity constraints and edge costs--not necessarily ALL flows. To do that I suggest you either write full search code, or find ONE flow, alter a unique link in it, then search again, and check whether the second flow has the same value. If so, iterate. $\endgroup$ – David G. Stork Jan 8 '15 at 1:45
  • $\begingroup$ Thanks David. That did in fact work well for me. On each iteration, I (1) noted the used paths, (2) appropriately reduced the expected flow from the sources and sinks by the capacity of these paths and (3) added a substantial cost to reusing these paths. I then iterated with the new network. However, the question remains, does FindMinimumCostFlow honor capacities at all? $\endgroup$ – Brian Jan 8 '15 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.