Stumbling through or-tools

Posted in hacks and kludges on Friday, February 10 2017

The other day I pip installed 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 queens 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, IntVars, 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 IntExprs 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: Exprs don't have a value, only Vars 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 Vars 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 DecisionBuilders 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 DecisionBuilders 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 DecisionBuilders 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.

SearchLimits, 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