# Is it possible to use EdgeCapacity in FindMinimumCostFlow?

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.

• 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. – David G. Stork Jan 8 '15 at 1:45
• 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? – Brian Jan 8 '15 at 15:15