Minimum cost flow problem with multiple arcs between nodes in Python / Google OR

Question

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],
                                                arc[3])

# 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?

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.