Try our new documentation site (beta).
Filter Content By
Version
Text Search
${sidebar_list_label} - Back
Filter by Language
netflow.py
#!/usr/bin/python # Copyright 2016, Gurobi Optimization, Inc. # Solve a multi-commodity flow problem. Two products ('Pencils' and 'Pens') # are produced in 2 cities ('Detroit' and 'Denver') and must be sent to # warehouses in 3 cities ('Boston', 'New York', and 'Seattle') to # satisfy demand ('inflow[h,i]'). # # Flows on the transportation network must respect arc capacity constraints # ('capacity[i,j]'). The objective is to minimize the sum of the arc # transportation costs ('cost[i,j]'). from gurobipy import * # Model data commodities = ['Pencils', 'Pens'] nodes = ['Detroit', 'Denver', 'Boston', 'New York', 'Seattle'] arcs, capacity = multidict({ ('Detroit', 'Boston'): 100, ('Detroit', 'New York'): 80, ('Detroit', 'Seattle'): 120, ('Denver', 'Boston'): 120, ('Denver', 'New York'): 120, ('Denver', 'Seattle'): 120 }) arcs = tuplelist(arcs) cost = { ('Pencils', 'Detroit', 'Boston'): 10, ('Pencils', 'Detroit', 'New York'): 20, ('Pencils', 'Detroit', 'Seattle'): 60, ('Pencils', 'Denver', 'Boston'): 40, ('Pencils', 'Denver', 'New York'): 40, ('Pencils', 'Denver', 'Seattle'): 30, ('Pens', 'Detroit', 'Boston'): 20, ('Pens', 'Detroit', 'New York'): 20, ('Pens', 'Detroit', 'Seattle'): 80, ('Pens', 'Denver', 'Boston'): 60, ('Pens', 'Denver', 'New York'): 70, ('Pens', 'Denver', 'Seattle'): 30 } inflow = { ('Pencils', 'Detroit'): 50, ('Pencils', 'Denver'): 60, ('Pencils', 'Boston'): -50, ('Pencils', 'New York'): -50, ('Pencils', 'Seattle'): -10, ('Pens', 'Detroit'): 60, ('Pens', 'Denver'): 40, ('Pens', 'Boston'): -40, ('Pens', 'New York'): -30, ('Pens', 'Seattle'): -30 } # Create optimization model m = Model('netflow') # Create variables flow = {} for h in commodities: for i,j in arcs: flow[h,i,j] = m.addVar(ub=capacity[i,j], obj=cost[h,i,j], name='flow_%s_%s_%s' % (h, i, j)) m.update() # Arc capacity constraints for i,j in arcs: m.addConstr(quicksum(flow[h,i,j] for h in commodities) <= capacity[i,j], 'cap_%s_%s' % (i, j)) # Flow conservation constraints for h in commodities: for j in nodes: m.addConstr( quicksum(flow[h,i,j] for i,j in arcs.select('*',j)) + inflow[h,j] == quicksum(flow[h,j,k] for j,k in arcs.select(j,'*')), 'node_%s_%s' % (h, j)) # Compute optimal solution m.optimize() # Print solution if m.status == GRB.Status.OPTIMAL: solution = m.getAttr('x', flow) for h in commodities: print('\nOptimal flows for %s:' % h) for i,j in arcs: if solution[h,i,j] > 0: print('%s -> %s: %g' % (i, j, solution[h,i,j]))