Push-relabel algorithm: Google or-tools
At last we will solve the instance of a Minimum cost flow problem described in (1) with Google or-tools. Node 1 is the source node, nodes 2 and 3 are the transshipment nodes and node 4 is the sink node.
So let’s see how the python API of google or-tools work:
# import graph from google or-tools from graph import pywrapgraph # Create graph # Attention: add +1 for number of nodes and arcs, if your node-IDs begin with 1 # because google or-tools mcf solver internal counters are strictly zero-based! num_nodes = 4 + 1 num_arcs = 5 + 1 # args: NumNodes * NumArcs G = pywrapgraph.StarGraph(num_nodes, num_arcs) # create min cost flow solver min_cost_flow = pywrapgraph.MinCostFlow(G) # add node to graph with positive supply for each supply node min_cost_flow.SetNodeSupply(1, 4) # add node to graph with negative demand for each demand node min_cost_flow.SetNodeSupply(4, -4) # you can ignore transshipment nodes with zero supply when you are working with # the mcfp-solver of google or-tools # add arcs to the graph arc = G.AddArc(1, 2) min_cost_flow.SetArcCapacity(arc, 4) min_cost_flow.SetArcUnitCost(arc, 2) arc = G.AddArc(1, 3) min_cost_flow.SetArcCapacity(arc, 2) min_cost_flow.SetArcUnitCost(arc, 2) arc = G.AddArc(2, 3) min_cost_flow.SetArcCapacity(arc, 2) min_cost_flow.SetArcUnitCost(arc, 1) arc = G.AddArc(2, 4) min_cost_flow.SetArcCapacity(arc, 3) min_cost_flow.SetArcUnitCost(arc, 3) arc = G.AddArc(3, 4) min_cost_flow.SetArcCapacity(arc, 5) min_cost_flow.SetArcUnitCost(arc, 1) # solve the min cost flow problem # flowDict contains the optimized flow # flowCost contains the total minimized optimum min_cost_flow.Solve() flowCost = min_cost_flow.GetOptimalCost() print "Optimum: %s" %flowCost
As one can see the python API of google or-tools is also pretty handy although everything is coded in C++. The python API was created using SWIG. The biggest caveat one can run into is the fact that the MCFP solver in google or-tools is strictly zero based. So adding nodes starting from 1 ..n result in strange errors if you don’t size the initial graph properly: just add +1 to the number of nodes and the number of arcs if your node ids start with 1.
Alternatively you can pass the proper number of nodes and arcs at the graph initialization and substract -1 from all of your node ids so they are zero based. But be careful – any arc is made of the node ids so you’ll have to substract -1 at the arcs level also.