Recipes for Google OR-Tools

3 minute read

Some tips and tricks for the CP-SAT solver.

Type hints

Autocompletion of protobuf generated scripts.

pip install ortools-stubs

Multithreading

solver.parameters.num_search_workers = 8

Search for all optimal solutions

You can’t use SearchForAllSolutions if you have an objective, so you have to do it in two steps:

# Get the optimal objective value
model.Maximize(objective)
solver.Solve(model)

# Set the objective to a fixed value
# use round() instead of int()
model.Add(objective == round(solver.ObjectiveValue()))
model.Proto().ClearField('objective')

# Search for all solutions
solver.SearchForAllSolutions(model, cp_model.VarArraySolutionPrinter([x, y, z]))

Non-contiguous Intvar

Alternatives to model.NewIntVar:

# List of values
model.NewIntVarFromDomain(
    cp_model.Domain.FromValues([1, 3, 4, 6]), 'x'
)

# List of intervals
model.NewIntVarFromDomain(
    cp_model.Domain.FromIntervals([[1, 2], [4, 6]]), 'x'
)

# Exclude [-1, 1]
model.NewIntVarFromDomain(
    cp_model.Domain.FromIntervals([[cp_model.INT_MIN, -2], [2, cp_model.INT_MAX]]), 'x'
)

# Constant
model.NewConstant(154)

Iff, equivalence, boolean product

p <=> (x and y)

# (x and y) => p, rewrite as not(x and y) or p
model.AddBoolOr([x.Not(), y.Not(), p])

# p => (x and y)
model.AddImplication(p, x)
model.AddImplication(p, y)

Implications

# a => b (both booleans)
model.AddImplication(a, b)

# a <=> b (better remove one of them)
model.Add(a == b)

# a or b or c => d
model.AddImplication(a, d)  # model.Add(d == 1).OnlyEnforceIf(a)
model.AddImplication(b, d)
model.AddImplication(c, d)

# a and b and c => d
model.Add(d == 1).OnlyEnforceIf([a, b, c])
or
model.AddBoolOr([a.Not(), b.Not(), c.Not(), d])

If-Then-Else

Using intermediate boolean variables.

b = model.NewBoolVar('b')

# Implement b == (x >= 5).
model.Add(x >= 5).OnlyEnforceIf(b)
model.Add(x < 5).OnlyEnforceIf(b.Not())

# First, b implies (y == 10 - x).
model.Add(y == 10 - x).OnlyEnforceIf(b)
# Second, not(b) implies y == 0.
model.Add(y == 0).OnlyEnforceIf(b.Not())

Solution hint / Warm start

It may speed up the search.

num_vals = 3
x = model.NewIntVar(0, num_vals - 1, 'x')
y = model.NewIntVar(0, num_vals - 1, 'y')
z = model.NewIntVar(0, num_vals - 1, 'z')

model.Add(x != y)

model.Maximize(x + 2 * y + 3 * z)

# Solution hinting: x <- 1, y <- 2
model.AddHint(x, 1)
model.AddHint(y, 2)

Storing Multi-index variables

I recommend using dictionary comprehensions:

employee_works_day = {
    (e, day): model.NewBoolVar(f"{e} works {day}")
    for e in employees
    for day in days
}

Variable product (Non linear)

You have to create an intermediate variable:

xy = model.NewIntVar(0, 8*5, 'xy')
model.AddMultiplicationEquality(xy, [x, y])

Load model Proto

This allows you to use different machines.

from google.protobuf import text_format
from ortools.sat.python import cp_model

model = cp_model.CpModel()
a = model.NewIntVar(0, 10, "a")
b = model.NewIntVar(0, 10, "b")
model.Maximize(a + b)

new_model = cp_model.CpModel()
text_format.Parse(str(model), new_model.Proto())

solver = cp_model.CpSolver()
status = solver.Solve(new_model)

print(solver.StatusName(status))
print(solver.ObjectiveValue())

Circuit constraint (ordering)

Ordering the numbers from 1 to 10 so that we maximize the distance between between numbers:

from itertools import permutations
from ortools.sat.python import cp_model

model = cp_model.CpModel()
solver = cp_model.CpSolver()

literals = {}
all_arcs = []
nodes = range(1, 11)

for i in nodes:
    # We use 0 as a dummy nodes as we don't have an actual circuit
    literals[0, i] = model.NewBoolVar(f"0 -> {i}")  # start arc
    literals[i, 0] = model.NewBoolVar(f"{i} -> 0")  # end arc
    all_arcs.append([0, i, literals[0, i]])
    all_arcs.append([i, 0, literals[i, 0]])

for i, j in permutations(nodes, 2):
    # this booleans will be true if the arc is present
    literals[i, j] = model.NewBoolVar(f"{i} -> {j}")
    all_arcs.append([i, j, literals[i, j]])

model.AddCircuit(all_arcs)
# model.Minimize(sum(literals[i, j] * abs(i - j) for i, j in permutations(nodes, 2)))
model.Maximize(sum(literals[i, j] * abs(i - j) for i, j in permutations(nodes, 2)))
solver.Solve(model)

node = 0
print(node, end="")
while True:
    for i in nodes:
        if i != node and solver.Value(literals[node, i]):
            print(f" -> {i}", end="")
            node = i
            break
    else:
        break
print(" -> 0")

Fairness, distribute items evenly

  • Maximize the minimum value
  • Minimize delta to the average value

Multiobjective optimization

Two ways to achieve that:

  • Add a weight to each objective
  • Solve with the first objective, constraint the objective with the solution, hint and solve with the new objective.

Leave a comment