In order to provide a gentle introduction to our interfaces, the examples so far have demonstrated only very basic capabilities. We will now attempt to demonstrate some of the power of our Python interface by describing a more complex example. This example is intended to capture most of the common ingredients of large, complex optimization models. Implementing this same example in another API would most likely have required hundreds of lines of code (ours is around 70 lines of Python code).

We'll need to present a few preliminaries before getting to the example itself. You'll need to learn a bit about the Python language, and we'll need to describe a few custom classes and functions. Our intent is that you will come away from this section with an appreciation for the power and flexibility of this interface. It can be used to create quite complex models using what we believe are very concise and natural modeling constructs. Our goal with this interface has been to provide something that feels more like a mathematical modeling language than a programming language API.

If you'd like to dig a bit deeper into the Python language constructs described here, we recommend that you visit the online Python tutorial.

Motivation

At the heart of any optimization model lies a set of decision variables. Finding a convenient way to store and access these variables can often represent the main challenge in implementing the model. While the variables in some models map naturally to simple programming language constructs (e.g., `x[i]` for contiguous integer values `i`), other models can present a much greater challenge. For example, consider a model that optimizes the flow of multiple different commodities through a supply network. You might have a variable `x['Pens', 'Denver', 'New York']` that captures the flow of a manufactured item (pens in this example) from Denver to New York. At the same time, you might *not* want to have a variable `x['Pencils', 'Denver', 'Seattle']`, since not all combinations of commodities, source cities, and destination cities represent valid paths through the network. Representing a sparse set of decision variables in a typical programming language can be cumbersome.

To compound the challenge, you typically need to build constraints that involve subsets of these decision variables. For example, in our network flow model you might want to put an upper bound on the total flow that enters a particular city. You could certainly collect the relevant decision variables by iterating over all possible cities and selecting only those variables that capture possible flow from that source city into the desired destination city. However, this is clearly wasteful if not all origin-destination pairs are valid. In a large network problem, the inefficiency of this approach could lead to major performance issues. Handling this efficiently can require complex data structures.

The Gurobi Python interface has been designed to make the issues we've just described quite easy to manage. We'll present a specific example of how this is done shortly. Before we do, though, we'll need to describe a few important Python constructs: `lists`, `tuples`, `dictionaries`, `list comprehension`, and `generator expressions`. These are standard Python concepts that are particularly important in our interface. We'll also introduce the `tuplelist` and `tupledict` classes, which are custom classes that we've added to the Gurobi Python interface.

A quick reminder: you can consult the online Python documentation for additional information on any of the Python data structures mentioned here.

Lists and tuples

The `list` data structure is central to most Python programs; Gurobi Python programs are no exception. We'll also rely heavily on a similar data structure, the `tuple`. Tuples are crucial to providing efficient and convenient access to Gurobi decision variables in Gurobi Python programs. The difference between a list and a tuple is subtle but important. We'll discuss it shortly.

Lists and tuples are both just ordered collections of Python objects. A list is created and displayed as a comma-separated list of member objects, enclosed in square brackets. A tuple is similar, except that the member objects are enclosed in parenthesis. For example, `[1, 2, 3]` is a list, while `(1, 2, 3)` is a tuple. Similarly, `['Pens', 'Denver', 'New York']` is a list, while `('Pens', 'Denver', 'New York')` is a tuple.

You can retrieve individual entries from a list or tuple using square brackets and zero-based indices:

gurobi> l = [1, 2.0, 'abc'] gurobi> t = (1, 2.0, 'abc') gurobi> print(l[0]) 1 gurobi> print(t[1]) 2.0 gurobi> print(l[2]) abc

What's the difference between a list and a tuple? A tuple is *immutable*, meaning that you can't modify it once it has been created. By contrast, you can add new members to a list, remove members, change existing members, etc. This immutable property allows you to use tuples as indices for *dictionaries*.

Dictionaries

A Python *dictionary* allows you to map arbitrary *key* values to pieces of data. Any *immutable* Python object can be used as a key: an integer, a floating-point number, a string, or even a tuple.

To give an example, the following statements create a dictionary `x`, and then associates a value `1` with key `('Pens', 'Denver', 'New York')`

gurobi> x = {} # creates an empty dictionary gurobi> x[('Pens', 'Denver', 'New York')] = 1 gurobi> print(x[('Pens', 'Denver', 'New York')]) 1

Python allows you to omit the parenthesis when accessing a dictionary using a tuple, so the following is also valid:

gurobi> x = {} gurobi> x['Pens', 'Denver', 'New York'] = 2 gurobi> print(x['Pens', 'Denver', 'New York']) 2

We've stored integers in the dictionary here, but dictionaries can hold arbitrary objects. In particular, they can hold Gurobi decision variables:

gurobi> x['Pens', 'Denver', 'New York'] = model.addVar() gurobi> print(x['Pens', 'Denver', 'New York']) <gurobi.Var *Awaiting Model Update*>

To initialize a dictionary, you can of course simply perform assignments for each relevant key:

gurobi> values = {} gurobi> values['zero'] = 0 gurobi> values['one'] = 1 gurobi> values['two'] = 2

You can also use the Python dictionary initialization construct:

gurobi> values = { 'zero': 0, 'one': 1, 'two': 2 } gurobi> print(values['zero']) 0 gurobi> print(values['one']) 1

We have included a utility routine in the Gurobi Python interface that simplifies dictionary initialization for a case that arises frequently in mathematical modeling. The `multidict` function allows you to initialize one or more dictionaries in a single statement. The function takes a dictionary as its argument, where the value associated with each key is a list of length `n`. The function splits these lists into individual entries, creating `n` separate dictionaries. The function returns a list. The first item in this list is the list of shared key values, followed by the `n` individual dictionaries. Using assignment unpacking, we can do:

gurobi> names, lower, upper = multidict({ 'x': [0, 1], 'y': [1, 2], 'z': [0, 3] }) gurobi> print(names) ['x', 'y', 'z'] gurobi> print(lower) {'x': 0, 'y': 1, 'z': 0} gurobi> print(upper) {'x': 1, 'y': 2, 'z': 3}

Note that you can also apply this function to a dictionary where each key maps to a scalar value. In that case, the function simply returns the list of keys as the first result, and the original dictionary as the second.

You will see this function in several of our Python examples.

List Comprehension and Generator Expressions

List comprehension and generator expressions are important Python features that allow you to do implicit enumeration in a concise fashion. To give a simple example, the following list comprehension builds a list containing the squares of the numbers from 1 through 5:

gurobi> [x*x for x in [1, 2, 3, 4, 5]] [1, 4, 9, 16, 25]

A generator expression is very similar, but it is used to generate an `Iterable` (something that can be iterated over). For example, suppose we want to compute the sum of the squares of the numbers from 1 through 5. We could use list comprehension to build the list, and then pass that list to `sum`. However, it is simpler and more efficient to use a generator expression:

gurobi> sum(x*x for x in [1, 2, 3, 4, 5]) 55

A generator expression can be used whenever a method accepts an `Iterable` argument (something that can be iterated over). For example, most Python methods that accept a `list` argument (the most common type of `Iterable`) will also accept a generator expression.

Note that there's a Python routine for creating a contiguous list of integers: `range`. The above would typically be written as follows:

gurobi> sum(x*x for x in range(1,6))

Details on the `range` function can be found here.

List comprehension and generator expressions can both contain more than one `for` clause, and one or more `if` clauses. The following example builds a list of tuples containing all `x,y`pairs where `x` and `y` are both less than 4 and `x` is less than `y`:

gurobi> [(x,y) for x in range(4) for y in range(4) if x < y] [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

Note that the `for` statements are executed left-to-right, and values from one can be used in the next, so a more efficient way to write the above is:

gurobi> [(x,y) for x in range(4) for y in range(x+1, 4)]

Generator expressions are used extensively in our Python examples, primarily in the context of creating multiple constraints at once using the `addConstrs` method.

Tuplelist Class

The next important item we would like to discuss is the `tuplelist` class. This is a custom sub-class of the Python `list` class that is designed to allow you to efficiently build sub-lists from a list of tuples. To be more specific, you can use the `select` method on a `tuplelist` object to retrieve all tuples that match one or more specified values in specific fields.

Let us give a simple example. We'll begin by creating a simple `tuplelist` (by passing a list of tuples to the constructor):

gurobi> l = tuplelist([(1, 2), (1, 3), (2, 3), (2, 4)])

To select a sub-list where particular tuple entries match desired values, you specify the desired values as arguments to the `select` method. The number of arguments to `select` is equal to the number of entries in the members of the `tuplelist` (they should all have the same number of entries). You can provide a list argument to indicate that multiple values are acceptable in that position in the tuple, or a `'*'` string to indicate that any value is acceptable.

Each tuple in our example contains two entries, so we can perform the following selections:

gurobi> print(l.select(1, '*')) <gurobi.tuplelist (2 tuples, 2 values each): ( 1 , 2 ) ( 1 , 3 ) > gurobi> print(l.select('*', 3)) <gurobi.tuplelist (2 tuples, 2 values each): ( 1 , 3 ) ( 2 , 3 ) > gurobi> print(l.select('*', [2, 4])) <gurobi.tuplelist (2 tuples, 2 values each): ( 1 , 2 ) ( 2 , 4 ) > gurobi> print(l.select(1, 3)) <gurobi.tuplelist (1 tuples, 2 values each): ( 1 , 3 ) > gurobi> print(l.select('*', '*')) <gurobi.tuplelist (4 tuples, 2 values each): ( 1 , 2 ) ( 1 , 3 ) ( 2 , 3 ) ( 2 , 4 ) >

You may have noticed that similar results could have been achieved using list comprehension. For example:

gurobi> print(l.select(1, '*')) <gurobi.tuplelist (2 tuples, 2 values each): ( 1 , 2 ) ( 1 , 3 ) > gurobi> print([(x,y) for x,y in l if x == 1]) [(1, 2), (1, 3)]

The problem is that the latter statement considers every member in the list `l`, which can be quite inefficient for large lists. The `select` method builds internal data structures that make these selections quite efficient.

Note that `tuplelist` is a sub-class of `list`, so you can use the standard `list` methods to access or modify a `tuplelist`:

gurobi> print(l[1]) (1,3) gurobi> l += [(3, 4)] gurobi> print(l) <gurobi.tuplelist (5 tuples, 2 values each): ( 1 , 2 ) ( 1 , 3 ) ( 2 , 3 ) ( 2 , 4 ) ( 3 , 4 ) >

Tupledict class

The final important preliminary we would like to discuss is the `tupledict` class. This is a custom sub-class of the Python `dict` class that allows you to efficiently work with subsets of Gurobi variable objects. To be more specific, you can use the `sum` and `prod` methods on a `tupledict` object to easily and concisely build linear expressions. The keys for a `tupledict` are stored as a `tuplelist`, so the same `select` syntax can be used to choose subsets of entries. Specifically, by associating a tuple with each Gurobi variable, you can efficiently create expressions that contain a subset of matching variables. For example, using the `sum` method on a `tupledict` object, you could easily build an expression that captures the sum over all Gurobi variables for which the first field of the corresponding tuple is equal to 3 (using `x.sum(3, '*')`).

While you can directly build your own `tupledict`, the Gurobi interface provides an `addVars` method that adds one Gurobi decision variable to the model for each tuple in the input argument(s) and returns the result as a `tupledict`. Let us give a simple example. We'll begin by constructing a list of tuples, and then we'll create a set of Gurobi variables that are indexed using this list:

gurobi> l = list([(1, 2), (1, 3), (2, 3), (2, 4)]) gurobi> d = model.addVars(l, name="d") gurobi> model.update()

The `addVars` method will create variables `d(1,2)`, `d(1,3)`, `d(2,3)`, and `d(2,4)`. Note that the `name` argument is used to name the resulting variables, but it only gives the prefix for the name - the names are subscripted by the tuple keys (so the variables would be named `d[1,2]`, `d[1,3]`, etc.). The final call to `update` synchronizes certain internal data structures; this detail can be safely ignored for now.

You can then use this `tupledict`

to build linear expressions. For example, you could do:

gurobi> sum(d.select(1, '*'))

The `select` method returns a list of Gurobi variables where the first field of the associated tuple is 1. The Python `sum` statement then creates a linear expression that captures the sum of these variables. In this case, that expression would be `d(1,2) + d(1,3)`. Similarly, `sum(d.select('*', 3))` would give `d(1,3) + d(2,3)`. As with a `tuplelist`, you use a `'*'` string to indicate that any value is acceptable in that position in the tuple.

The `tupledict` class includes a method that simplifies the above. Rather than `sum(d.select('*', 3))`, you can use `d.sum('*', 3)` instead.

The `tupledict` class also includes a `prod` method, for cases where you need to build a linear expression with coefficients that aren't all `1.0`. Coefficients are provided through a `dict` argument. They are indexed using the same tuples as the `tupledict`. For example, given a `dict` named `coeff` with two entries: `coeff(1,2)` = 5 and `coeff(2,3)` = 7, a call to `d.prod(coeff)` would give the expression `5 d(1,2) + 7 d(2,3)`. You can also include a filter, so `d.prod(coeff, 2, '*')` would give just `7 d(2,3)`.

Note that `tupledict` is a sub-class of `dict`, so you can use the standard `dict` methods to access or modify a `tupledict`:

gurobi> print(d[1,3]) <gurobi.Var d[1,3]> gurobi> d[3, 4] = 0.3 gurobi> print(d[3, 4]) 0.3 gurobi> print(d.values()) dict_values([<gurobi.Var d[1,2]>, 0.3, <gurobi.Var d[1,3]>, <gurobi.Var d[2,3]>, <gurobi.Var d[2,4]>])

In our upcoming network flow example, once we've built a `tupledict` that contains a variable for each valid commodity-source-destination combination on the network (we'll call it `flows`), we can create a linear expression that captures the total flow on all arcs that empty into a specific destination city as follows:

gurobi> inbound = flows.sum('*', '*', 'New York')

Example details

Our example solves a multi-commodity flow model on a small network. In the example, two commodities (Pencils and Pens) are produced in two cities (Detroit and Denver), and must be shipped to warehouses in three cities (Boston, New York, and Seattle) to satisfy given demand. Each arc in the transportation network has a per-unit cost associated with it, as well as a maximum total shipping capacity.

The complete source code for our example can be found in:

- Online: Example netflow.py
- Distribution:
`<installdir>/examples/python/netflow.py`

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:

import gurobipy as gp from gurobipy import GRB

We then create a few lists that contain model data:

# Base data commodities = ['Pencils', 'Pens'] nodes = ['Detroit', 'Denver', 'Boston', 'New York', 'Seattle'] arcs, capacity = gp.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 one unit of 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 supply/demand data:

# Supply (> 0) and demand (< 0) 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}

A positive value indicates supply, while a negative value indicates demand.

Building a Multi-dimensional Array of Variables

The next step in our example (after creating an empty `Model` object) is to add decision variables to the model. The variables are created using `addVars`, and are returned in a `tupledict` which we'll call `flow`:

# Create optimization model m = gp.Model('netflow') # Create variables flow = m.addVars(commodities, arcs, obj=cost, name="flow")

The first, positional arguments to `addVars` give the index set. In this case, we'll be indexing `flow` by `commodities` and `arcs`. In other words, `flow[c,i,j]` will capture the flow of commodity `c` from node `i` to node `j`. Note that `flow` only contains variables for source, destination pairs that are present in `arcs`. Note also that `flow[c,i,j]` is a continuous decision variable; variables are assumed to be continuous unless you state otherwise.

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))

Flow Conservation Constraints

The next set of constraints are the flow conservation constraints. They require that, for each commodity and node, the sum of the flow into the node plus the quantity of external inflow at that node must be equal to the sum of the flow out of the node:

# Flow-conservation constraints m.addConstrs( (flow.sum(h, '*', j) + inflow[h, j] == flow.sum(h, j, '*') for h in commodities for j in nodes), "node")

This call to `addConstrs` is similar to the previous one, although a bit more complex. We invoke the `sum` method on a `tupledict`, wrapped inside of a generator expression, to add one linear constraint for each commodity-node pair. In this instance, we call `sum` twice, and we use a generator expression that contains of a pair of `for` loops, but the basic concepts remain the same.

Example results

Once we've added the model constraints, we call `optimize` and then output the optimal solution:

# Compute optimal solution m.optimize() # Print solution if m.Status == GRB.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]))

If you run the example `python netflow.py`, you should see the following output:

Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (linux64)

CPU model: AMD EPYC 7282 16-Core Processor, instruction set [SSE2|AVX|AVX2] Thread count: 4 physical cores, 4 logical processors, using up to 4 threads Optimize a model with 16 rows, 12 columns and 36 nonzeros Model fingerprint: 0xc43e5943 Coefficient statistics: Matrix range [1e+00, 1e+00] Objective range [1e+01, 8e+01] Bounds range [0e+00, 0e+00] RHS range [1e+01, 1e+02] Presolve removed 16 rows and 12 columns Presolve time: 0.00s Presolve: All rows and columns removed Iteration Objective Primal Inf. Dual Inf. Time 0 5.5000000e+03 0.000000e+00 2.000000e+01 0s Extra simplex iterations after uncrush: 1 1 5.5000000e+03 0.000000e+00 0.000000e+00 0s Solved in 1 iterations and 0.00 seconds (0.00 work units) Optimal objective 5.500000000e+03 Optimal flows for Pencils: Detroit -> Boston: 50 Denver -> New York: 50 Denver -> Seattle: 10 Optimal flows for Pens: Detroit -> Boston: 30 Detroit -> New York: 30 Denver -> Boston: 10 Denver -> Seattle: 30

## Comments

0 comments

Article is closed for comments.