Some tips and tricks for the CP-SAT solver.

## Type hints

Autocompletion of protobuf generated scripts.

``````pip install ortools-stubs
``````

``````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.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
# p => (x and y)
``````

## If-Then-Else

Using intermediate boolean variables.

``````b = model.NewBoolVar('b')

# Implement b == (x >= 5).

# First, b implies (y == 10 - x).
# Second, not(b) implies y == 0.
``````

## 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.Maximize(x + 2 * y + 3 * z)

# Solution hinting: x <- 1, 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')
``````

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

Tags:

Updated: