The other day I `pip install`

ed google's or-tools and started madly optimizing every facet of my life, using constraint programming. Er, well, actually I've been futzing about solving toy problems and trying to figure out *how to use or-tools?*. You see `or-tools`

is written in C++ and the python interface is a pretty basic wrapper. It is not particularly self-documenting (pythonically), and the official docs and examples are only very basic models in python. For example, in iPython the documentation for the `Add()`

method is:

```
In [3]: solver.Add?
Signature: solver.Add(ct)
Docstring: <no docstring>
File: ~/.virtualenvs/discrete/lib/python3.5/site-packages/ortools/constraint_solver/pywrapcp.py
Type: method
```

Which is pretty unhelpful but also pretty typical.

There are lots of more complex features that are not clearly explained in the python examples, and it isn't always obvious how to use them from the docstrings, so I'm going to take a moment and run through some of my hiccups.

I'm going to focus on constraint programming, because that's the problem space I happen to be occupying right now, and as an introductory toy-example let's consider the N-Queens problem.

First off we need to set up the solver:

```
from ortools.constraint_solver import pywrapcp as cp
params = cp.Solver.DefaultSolverParameters()
solver = cp.Solver('N-Queens Problem with CP', params)
```

The `params`

is a struct that defines the basic operation of the solver, with a bunch of attributes you can modify, though honestly I have no idea what any of them do. The `solver`

object is the primary interface to the `or-tools`

magic, most of what you will do in python will will go through the `solver`

API.

### Variables, Constraints, and Expressions

Anyways, back to the N-Queen problem, suppose I want to solve the classic 8 queens problem. The classic variable choice is 8 variables representing the 8 columns of the chess-board and the value they take is the particular row that column's queen occupies. I'm not going to give you any real details, read the wikipedia page if you care that much

```
# The decision variables for this problem
queens = [solver.IntVar(0, 7, 'Queen {}'.format(i)) for i in range(8)]
```

It's that easy. But what have I done? The `IntVar(...)`

method creates integer valued variables that or-tools can use. When you call `solver.IntVar(...)`

it returns an `IntVar`

type object. In this case the `queen`

s are each given a domain {0..7} and a name "Queen i". Collecting them all in a list like this, or assigning them each to a python variable, is necessary because we haven't added them to our model yet, that comes later.

There are other variable types beyond integers, `IntVar`

s, for example booleans `BoolVar`

, and there are also interval and sequence variables but I'm not going to get into those.

**Note** from now on I'm just going to call variables in the model `Vars`

to indicate that they are specifically `or-tools`

objects with special properties, not regular old python variables.

Now to add some constraints (it wouldn't really be constraint programming without them):

```
# All rows have to be different
solver.Add(solver.AllDifferent(queens))
# All diagonals have to be different
solver.Add(solver.AllDifferent([queens[i] + i for i in range(8)]))
solver.Add(solver.AllDifferent([queens[i] - i for i in range(8)]))
```

So what's going on here? `solver.Add( ... )`

adds a `Constraint`

object to the model. The `AllDifferent`

function takes a list of `Vars`

and returns a `Constraint`

where the members of the list are (wait for it) *all different*. The constraints are evaluated in the order in which they are added to the solver, so keep that in mind.

The python logical operators have been overloaded on `Vars`

so you can easily generate constraints in a way that is syntactically nice, for example: `queens[1] != queens[2]`

returns an object of type `Constraint`

, which can be added to the model using `solver.Add(...)`

.

You can also generate 'expressions' (I guess kind of like functions) in a sensible way, so `queens[1] + 2`

returns a `IntExpr`

, and expressions can be turned into constraints as above. In fact the diagonals `AllDifferent(...)`

constraint is taking a list of `IntExpr`

s and making a constraint on that.

The solver API also has some special functions, useful for dealing with lists of variables: `solver.Min()`

, `solver.Max()`

, `solver.Sum()`

, and `solver.Count()`

. They all do what you would expect, taking a list of `Vars`

and returning an `Expr`

. Be warned, the python builtins don't necessarily do what you expect:

`sum(queens)`

returns an `Expr`

`max(queens)`

returns queen[7], a `Var`

So it's probably best to use the solver API methods for these things.

**One giant note:** `Expr`

s don't have a value, only `Var`

s have values (once the solver is done), so how do you turn one into the other?

```
e = some expression
y = e.Var() # this is the Var for whatever the expression evaluates to
val = y.Value() # the actual value of the variable
```

**Massive Warning** Don't try and access a `Var`

s value before it has been set, it won't throw an exception, it will segmentation fault and crash python. In fact lots of things that you would wish would throw exceptions don't, so when in doubt be less pythonic and ask permission instead of begging forgiveness.

```
x = solver.IntVar(0, 10, 'for example')
x.Value() # Everything crashes
```

### Decision Builders

This is something the main reference docs just glide over and don't really explain. Let's take a step back and think about what the solver is actually *doing* (very generally): It takes the problem space, branches it in some way, then prunes based on the constraints. By defining the constraints and the domains of our variables we have given the solver a way of *pruning* but not *branching*. This, in essence, is what a `DecisionBuilder`

does.

The most basic way of doing this is through the `Phase(...)`

method. Supposing we stick with the default from the documentation,

```
db = solver.Phase(queens,
solver.CHOOSE_FIRST_UNBOUND,
solver.ASSIGN_MIN_VALUE)
```

The first argument is a list of decision variables, *this needs to be a flat list*, if you give it a single variable or a list of lists it will throw an obtuse exception. For example, suppose that you parametrised this problem as a matrix of boolean `Vars`

with `True`

if a queen was in that position, `False`

otherwise. You might make it like so:

```
queens = [ [solver.BoolVar('Queen at row {}, col {}'.format(i, j)) for j in range(8)] for i in range(8)]
```

When it comes time to create the `DecisionBuilder`

, though, you'll have to flatten that list. If you pass it directly, e.g. `Phase(queens, ...)`

it will throw a `NotImplementedError`

and complain about the wrong number or type of arguments, etc. The same thing will happen if you try to create a `DecisionBuilder`

using *a single variable*. You need to pass it a list of `Vars`

(or `Exprs`

) even if it is a list with only one member.

The next two arguments are the variable strategy and the value strategy. The variable strategy is basically how you are going to choose the next variable to branch on, the value strategy is how you are going to pick the next value of that variable. There is a whole list of them and they are pretty self explanatory. One thing to keep in mind is that the `DecisionBuilder`

looks through the `Vars`

in the order that they are given *to the DecisionBuilder* (subject to the variable strategy of course). So CHOOSE_FIRST_UNBOUND is the first unbound

`Var`

in the list.For `Var`

strategies:

- CHOOSE_FIRST_UNBOUND
- CHOOSE_RANDOM
- CHOOSE_MIN_SIZE_LOWEST_MIN
- CHOOSE_MIN_SIZE_HIGHEST_MIN
- CHOOSE_MIN_SIZE_LOWEST_MAX
- CHOOSE_MIN_SIZE_HIGHEST_MAX
- CHOOSE_LOWEST_MIN
- CHOOSE_HIGHEST_MAX
- CHOOSE_MIN_SIZE
- CHOOSE_MAX_SIZE
- CHOOSE_MAX_REGRET
- CHOOSE_PATH

For *value* strategies they are:

- ASSIGN_MIN_VALUE
- ASSIGN_MAX_VALUE
- ASSIGN_RANDOM_VALUE
- ASSIGN_CENTER_VALUE
- SPLIT_LOWER_HALF
- SPLIT_UPPER_HALF

The examples talk about exploring in multiple *phases* but they don't really say *how*. This is where it is useful to realize that `DecisionBuilder`

s are not "part of the model", to look forward a bit, when it comes time to solve you have to specify which `DecisionBuilder`

to use. You can create several different ones that exlore different decision variables if you want, and with different search strategies.

Suppose you had two sets of `Vars`

and you created two `DecisionBuilder`

s one for each set, `db1`

and `db2`

. You can run them sequentially, branch using db1 all the way down, then branch using db2, and so on. This is done using `Compose(...)`

. It takes a list of `DecisionBuilder`

s and returns a `DecisionBuilder`

```
db = solver.Compose([db1, db2])
```

Relatedly there is `Try(...)`

which has the same signature, but *tries* each `DecisionBuilder`

on the whole tree, one at a time, in the order of the list. So, for example, it would try db1 all the way through, then db2 all the way through, and so on through the list. This is convenient if you want to try some simpler scheme first, then if it fails try a more elaborate search.

### Search Monitors

Search Monitors are a broad class of objects, the basic idea is they monitor the search and intervene for some reason in some intelligent way. There are three types of search monitor (they all inherit from `SearchMonitor`

) that I've used and are most useful: search limits, objectives, and solution collectors.

`SearchLimit`

s, as the name implies, are limits on the search, and once the solver hits those limits it stops. Our current 8-Queens model has no limits so it will run until it finds all solutions, even if this means taking forever.

A very important limit and the first *gotcha* that got me diving into the C++ documentation is setting a *time limit*. Naively I expeced the method `solver.TimeLimit(...)`

to set a time limit for the solver. *It does not*, it returns a `SearchLimit`

object that you then *have to use* when you run the solver. Suppose I only want to wait 1 minute for a solution, since `TimeLimit(...)`

takes an integer number of milliseconds I need to create a `SearchLimit`

object to limit the search to 60,000ms.

```
tl = solver.TimeLimit(60000) # One minute
```

You can also limit branches, failures, and solutions. They all work the same basic way, they take an integer as the limit and return a `SearchLimit`

object

```
# For example
bl = solver.BranchesLimit(1234)
fl = solver.FailuresLimit(5678);
sl = solver.SolutionsLimit(1);
```

If you want to set a bunch of limits at once there is a better method to call `Limit(...)`

```
# For example
lim = solver.Limit(60000, # time
1234, # branches
5678, # failures
1, # solutions
True, # smart_time_check, minimizes calls to walltime()
True) # cumulative, i.e. are these global limits?
```

Objectives are also a search monitor. A quick example: suppose you have a system where you want to minimize some `Expr`

then you would do something like this:

```
objexpr = solver.Sum(othervars) # This is an IntExpr for the sum of the othervars
obj = solver.Minimize(objexpr, 1) # type OptimizeVar, a SearchMonitor
obj = solver.Maximize(objexpr, 1)
```

Objective functions take two arguments, a `Var`

or `Expr`

(the objective), and a step-size, here I'm using a step size of 1 arbitrarily. However in this case the objective has no domain. If you want to look for a solution within a particular boundary you need to make the objective into a constraint:

```
objvar = solver.IntVar(0, 10, 'my objective, which must be between 0 and 10')
objexpr = solver.Sum(othervars)
solver.Add(objvar == objexpr) # Now the objective is constrained
objective = solver.Minimize(objexpr, 1) # But I'm still optimizing the expression
```

A solution collector gathers solutions. You don't need to use one but it is convenient for a few reasons: If you are looking for more than one solution this gives you a place to collect them (as opposed to stepping through each solution one by one, more on that later), you can filter your solutions here too, say keeping the best solution or the last solution or whatever. In the case of the 8-Queen problem I might want to keep all solutions, whereas in an optimization problem I would only want to keep the *best* solution.

```
collector = solver.FirstSolutionCollector()
collector = solver.LastSolutionCollector()
collector = solver.BestValueSolutionCollector(bool maximum) #True for a maximum,
#False for a min
collector = solver.AllSolutionCollector() # Collects everything
```

I think the names are pretty self explanatory. You can either add the variables you want to collect solutions for during creation or later with the `Add()`

function. In the 8-Queens problem I want to collect the solution for the queens variables, and I want to collect all solutions:

```
collector = solver.AllSolutionsCollector()
collector.Add(queens)
```

If you have an objective you should add it to the solution collector as well:

```
collector.AddObjective(objective)
```

### Solving the Problem

Now, finally, we are ready to start solving the problem. Brief recap: We've defined our decision variables (with appropriate domains), we've created constraints using those variables and added them to the solver, we've created a decision builder and some search limits that define how the search will take place.

```
status = solver.Solve(db, [objective, collector, timelimit])
```

That's it. The first argument is the decision builder, the second is a list of any search monitors or search limits that you want to use (as far as I know order isn't really important).

The `status`

returned is a boolean, `True`

if the search ended properly and `False`

if it didn't. *Pay attention to this* the status will be `True`

if *any* solution is found, even if the search limits were exceeded. To check if, for example, the time limit was exceeded use the `Crossed()`

method

```
timelimit.Crossed() #True if the timelimit was crossed, otherwise False
```

Now that you have run the solver you probably want the solution. You unpack them from the solution collector (again: *only if the search succeeded* trying to access variables that haven't been set to anything is a bad idea).

```
# Unpacks the result for each queen
solution = [collector.Value(0, queen) for queen in queens]
```

If there was an objective function, the value of the objective is also available through the solution collector

```
objective = collector.ObjectiveValue(0)
```

In both of these there is a 0, that's the index of the solution. If you used a solution collector that collected more than one, then you would have to unpack each solution by its index.

Anyways... That was a long post of just my notes to myself about how to use google or-tools. Hope you found it useful! If you have any updates/corrections create an issue or pull request