Is it possible to work with multiple arcs between 2 nodes within Google OR?

Or are there better modeling techniques?

I want to optimize flow from supply to demand areas, where supply and demand are constraints on node level (each node has 1 supply/demand that the arcs can use/fulfill).

# Application to liner shipping

# Instantiate a SimpleMinCostFlow solver. min_cost_flow = pywrapgraph.SimpleMinCostFlow()

# Define four parallel arrays: sources, destinations, capacities,
# and unit costs between each pair.
# start_nodes and end_nodes contain list of edges between nodes (both arrays have same length) start_nodes = [1, 1, 1, 2, 2] end_nodes = [2, 2, 3, 3, 3] capacities = [70, 50, 90, 60, 40] unit_costs = [100, 100, 100, 100, 100]

# Define an array of supplies at each node. supplies = [500, 0, -500]

# Add each arc. for arc in zip(start_nodes, end_nodes, capacities, unit_costs):
    min_cost_flow.AddArcWithCapacityAndUnitCost(arc[0], arc[1], arc[2],

# Add node supply. for count, supply in enumerate(supplies):
    min_cost_flow.SetNodeSupply(count, supply)
# Find the min cost flow. status = min_cost_flow.Solve()

if status != min_cost_flow.OPTIMAL:
    print('There was an issue with the min cost flow input.')
    print(f'Status: {status}')
    exit(1) print('Minimum cost: ', min_cost_flow.OptimalCost()) print('') print(' Arc   Flow / Capacity  Cost') for i in range(min_cost_flow.NumArcs()):
    cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i)
    print('%1s -> %1s    %3s   / %3s   %3s' %
          (min_cost_flow.Tail(i), min_cost_flow.Head(i),
           min_cost_flow.Flow(i), min_cost_flow.Capacity(i), cost))

The example (modified from Google OR: https://developers.google.com/optimization/flow/mincostflow) crashes immediately, because I suppose the framework was not built for this type of modeling.

How can I achieve this? Has it been done before?


1 Answer 1


I'm assuming that parallel arcs between the same nodes differ in something relevant (cost?), since otherwise you could just combine them into a single arc (summing capacities, if they are capacitated). Not being a Google OR user, I can't address whether it can handle multigraphs. There is, however, a fairly common hack for a situation like this. For each set of parallel arcs, leave one alone and break each of the remaining ones into two arcs with a new (dummy) node in between them. One of the new arcs retains the cost of the original arc (if there are costs); both of the new arcs have the capacity (if pertinent) of the original arc. The dummy node neither generates nor absorbs traffic. So if there are two arcs A -> B, you wind up with one arc A -> B and two arcs forming a path A -> A' -> B, where A' is the dummy node.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.