# 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.8190854,"math_prob":0.79642165,"size":1125,"snap":"2020-45-2020-50","text_gpt3_token_len":361,"char_repetition_ratio":0.15165031,"word_repetition_ratio":0.10227273,"special_character_ratio":0.33333334,"punctuation_ratio":0.2112676,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.95926577,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-11-30T23:53:31Z\",\"WARC-Record-ID\":\"<urn:uuid:a7930dc4-031d-43cf-9a24-dd0fc6e873f6>\",\"Content-Length\":\"145125\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:4357baad-289a-48da-ab1f-3d4af7fa75fc>\",\"WARC-Concurrent-To\":\"<urn:uuid:1868769f-a6f3-471e-89b7-5deae92cde42>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://mathematica.stackexchange.com/questions/71316/is-it-possible-to-use-edgecapacity-in-findminimumcostflow\",\"WARC-Payload-Digest\":\"sha1:AH55NPSAY5GIOARQ5QYGSPBCDSD44QXX\",\"WARC-Block-Digest\":\"sha1:XU4RG6JAPWGIXVOZLILVRMA6QE7NEJNE\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-50/CC-MAIN-2020-50_segments_1606141515751.74_warc_CC-MAIN-20201130222609-20201201012609-00597.warc.gz\"}"}