Documentation

Arc capacity constraints

We begin with a straightforward set of constraints. The sum of the flow variables on an arc must be less than or equal to the capacity of that arc:

# Arc-capacity constraints
m.addConstrs(
    (flow.sum('*', i, j) <= capacity[i, j] for i, j in arcs), "cap")

Note that this one statement uses several of the concepts that were introduced earlier in this section.

The first concept used here is the sum method on flow, which is used to create a linear expression over a subset of the variables in the tupledict. In particular, it is summing over all commodities (the '*' in the first field) associated with an edge between a pair of cities i and j.

The second concept used here is a generator expression, which iterates over all arcs in the network. Specifically, this portion of the statement...

  for i,j in arcs

indicates that we are iterating over every edge in arcs. In each iteration, i and j will be populated using the corresponding values from a tuple in arcs. In a particular iteration, flow.sum('*',i,j) will be computed using those specific values, as will capacity[i,j].

The third thing to note is that we're passing the result as an argument to addConstrs. This method will create a set of Gurobi constraints, one for each iteration of the generator expression.

The final thing to note is that the last argument gives the base for the constraint name. The addConstrs method will automatically append the corresponding indices for each constraint. Thus, for example, the name of the constraint that limits flow from Denver to Boston will be cap[Denver,Boston].

Note that if you prefer to do your own looping, you could obtain the equivalent behavior with the following loop:

for i,j in arcs:
    m.addConstr(sum(flow[h,i,j] for h in commodities) <= capacity[i,j],
                "cap[%s,%s]" % (i, j))