Documentation

netflow.py example details

Let us now walk through the example, line by line, to understand how it achieves the desired result of computing the optimal network flow. As with the simple Python example presented earlier, this example begins by importing the Gurobi functions and classes:


from gurobipy import *

We then create a few lists that contain model data:


# Base 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 })

The model works with two commodities (Pencils and Pens), and the network contains 5 nodes and 6 arcs. We initialize commodities and nodes as simple Python lists. We use the Gurobi multidict function to initialize arcs (the list of keys) and capacity (a dictionary).

The model also requires cost data for each commodity-arc pair:


# Cost for triplets commodity-source-destination
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 }

Once this dictionary has been created, the cost of moving commodity h from node i to j can be queried as cost[(h,i,j)]. Recall that Python allows you to omit the parenthesis when using a tuple to index a dictionary, so this can be shortened to just cost[h,i,j].

A similar construct is used to initialize node demand data:


# Demand for pairs of commodity-city
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 }