The Python API Layer: Protobuf, CP-SAT Model, and Solver Parameters

Open ortools/sat/python/cp_model.py and you find that CpModel has almost no logic of its own. Its constructor creates one object:

class CpModel:
    def __init__(self):
        self.__model = cp_model_pb2.CpModelProto()

cp_model_pb2.CpModelProto is the Python class auto-generated from ortools/sat/cp_model.proto. Every method you call on CpModel — NewIntVar, AddAllDifferent, Minimize — appends to fields of that single proto object.

model = CpModel()
x = model.NewIntVar(0, 4, "x")

def NewIntVar(self, lb, ub, name):
    index = len(self.__model.variables)
    var_proto = self.__model.variables.add()     # append to repeated field
    var_proto.domain.extend([lb, ub])            # [min, max] domain encoding
    var_proto.name = name
    return IntVar(self.__model, index, name)     # thin handle, not a value

When you call solver.Solve(model), the very first step is:

response_proto = pywrap_sat.SolveWithParameters(
    model.Proto().SerializeToString(),   # bytes
    parameters.SerializeToString(),      # bytes
)

model.Proto() returns the CpModelProto directly. .SerializeToString() is the standard Protobuf API — it encodes the proto as a compact binary byte string. Those bytes are handed to a C extension (pywrap_sat) that deserialises them back into a C++ CpModelProto and calls SolveCpModel().

sequenceDiagram
  participant PY as Python
  participant PB as Protobuf (bytes)
  participant CC as C++ SolveCpModel

  PY->>PB: model.Proto().SerializeToString()
  PB->>CC: deserialise → CpModelProto&
  Note over CC: Presolve → Trail → Propagators → CDCL+LP
  CC->>PB: CpSolverResponse.SerializeToString()
  PB->>PY: deserialise → CpSolverResponse

Why Protobuf instead of a direct C-API with Python ctypes or shared memory?

variables {
  domain: [0, 1]   # Boolean: teacher A, room 1, slot 1
  name: "assign_A_R1_T1"
}
# ... 7 more variable entries ...
constraints {
  exactly_one { literals: [0, 1] }   # Teacher A in exactly one slot
}
constraints {
  exactly_one { literals: [2, 3] }   # Teacher B in exactly one slot
}
# ... more constraints ...
objective {
  vars: [0, 1, 2, 3, 4, 5, 6, 7]
  coeffs: [10, 10, 10, 10, 10, 10, 10, 10]
  offset: 0
}

Once SolveCpModel() receives the deserialised CpModelProto, it runs a pipeline whose stages map directly onto the machinery from earlier lessons. ^{[OR-Tools CP-SAT source: ortools/sat/cp_model_solver.cc (SolveCpModel)]}

flowchart TD
  A[CpModelProto&] --> B[Presolve
variable elimination
constraint simplification
symmetry detection]
  B --> C[Model Expansion
build SatSolver trail
instantiate CpPropagators
register GenericLiteralWatcher]
  C --> D[Portfolio Worker Setup
N independent SatSolvers
shared clause database subset
or independent DBs]
  D --> E[CDCL + CP + LP Solve Loop
from the Propagator Architecture lesson]
  E --> F[Collect best response
fill CpSolverResponse]
  F --> G[CpSolverResponse&]
  style B fill:#1e3a5f,color:#cbd5e1
  style C fill:#4c1d95,color:#ddd6fe
  style D fill:#065f46,color:#a7f3d0
  style E fill:#7f1d1d,color:#fca5a5
  style F fill:#374151,color:#d1d5db

Presolve is the most opaque phase. The solver applies a battery of rewriting rules:

• Domain propagation at level 0 — run all propagators before any branch decision. Constraints that become unit implications are resolved immediately.
• Variable elimination — if a variable appears in only a few constraints, substitute it away algebraically, reducing the model size.
• Constraint simplification — detect tautologies (always-true constraints) and contradictions; fold constants.
• Symmetry detection — find permutations of variables that leave the constraint set invariant; add symmetry-breaking clauses so the solver explores only one representative of each symmetric class.

After presolve, the surviving proto fields are expanded into the C++ data structures you know: the assignment trail, the two-watched-literal index, and the CpPropagator registry (including Glop as the LP propagator, as discussed in “Optimization in CP-SAT”).

When the solve completes, C++ fills a CpSolverResponse proto and serialises it back to Python. solver.Solve(model) returns the status enum, but all the detail is in the response object:

solver = CpSolver()
status = solver.Solve(model)

# Status
print(solver.StatusName(status))       # "OPTIMAL", "FEASIBLE", "INFEASIBLE", etc.

# Objective bounds
print(solver.ObjectiveValue())         # best integer objective found
print(solver.BestObjectiveBound())     # dual lower bound — from the LP relaxation

# Solution values (only valid if status is OPTIMAL or FEASIBLE)
print(solver.Value(assign_A_R1_T1))   # 0 or 1

# Solver statistics
print(solver.NumBooleans())            # Boolean variables after presolve
print(solver.NumConflicts())           # conflicts resolved by CDCL
print(solver.NumBranches())            # branch decisions taken
print(solver.WallTime())               # elapsed seconds
print(solver.UserTime())               # CPU seconds (sum across workers)

The gap between ObjectiveValue() and BestObjectiveBound() is the integrality gap from the previous lesson — how far the best found integer solution is from the proven lower bound. When both are equal, the solution is proven optimal and status == OPTIMAL. When the solver times out with a gap remaining, status == FEASIBLE and you can compute how close you are:

gap_pct = (solver.ObjectiveValue() - solver.BestObjectiveBound()) / abs(solver.ObjectiveValue()) * 100
print(f"Within {gap_pct:.1f}% of optimal")

solver.Value(var) decodes a variable’s solution value by looking up var’s index in response.solution:

# Simplified from cp_model.py
def Value(self, var: IntVar) -> int:
    return self.__solution[var.Index()]

If you call Value() when the status is INFEASIBLE, self.__solution is empty and you get an IndexError. Always guard on status.

SolverParameters is another auto-generated Protobuf message, from ortools/sat/sat_parameters.proto. Setting a parameter on the Python side serialises it along with the model and is read by the C++ solver at startup.

solver = CpSolver()
solver.parameters.max_time_in_seconds = 30.0
solver.parameters.num_workers = 8
solver.parameters.log_search_progress = True
status = solver.Solve(model)

The table below maps each parameter to the internal mechanism it controls — the same mechanisms from earlier lessons:

#  ... objective:42  bound:38  #conflicts:12847  #branches:38291  time:29.1s

Let’s trace a minimal school-timetabling model end to end, from Python lines to proto fields to response statistics.

Problem: 2 teachers (A, B), 2 rooms (R1, R2), 2 time slots (T1, T2). Each teacher must be assigned exactly one (room, slot) pair. No room may have two teachers in the same slot. Minimise total room switches (a soft objective).

from ortools.sat.python.cp_model import CpModel, CpSolver

model = CpModel()

# 8 Boolean assignment variables: teacher × room × slot
assign = {}
for teacher in ["A", "B"]:
    for room in ["R1", "R2"]:
        for slot in ["T1", "T2"]:
            assign[teacher, room, slot] = model.NewBoolVar(
                f"assign_{teacher}_{room}_{slot}"
            )

# Each teacher in exactly one (room, slot)
for teacher in ["A", "B"]:
    model.AddExactlyOne(
        assign[teacher, room, slot]
        for room in ["R1", "R2"]
        for slot in ["T1", "T2"]
    )

# No room conflict: at most one teacher per (room, slot)
for room in ["R1", "R2"]:
    for slot in ["T1", "T2"]:
        model.AddAtMostOne(
            assign[teacher, room, slot] for teacher in ["A", "B"]
        )

# Soft objective: prefer teachers in the same room (minimise room switches)
room_switches = model.NewIntVar(0, 2, "room_switches")
# (simplified — a real model would build this from the assignment variables)
model.Minimize(room_switches)

solver = CpSolver()
solver.parameters.max_time_in_seconds = 10.0
solver.parameters.num_workers = 4
solver.parameters.log_search_progress = True
solver.parameters.linearization_level = 1   # default LP usage
solver.parameters.random_seed = 42          # reproducible

status = solver.Solve(model)
print(f"Status: {solver.StatusName(status)}")
print(f"Objective: {solver.ObjectiveValue()}")
print(f"Dual bound: {solver.BestObjectiveBound()}")
print(f"Conflicts: {solver.NumConflicts()}")
print(f"Branches:  {solver.NumBranches()}")
print(f"Wall time: {solver.WallTime():.3f}s")

for teacher in ["A", "B"]:
    for room in ["R1", "R2"]:
        for slot in ["T1", "T2"]:
            if solver.Value(assign[teacher, room, slot]):
                print(f"  Teacher {teacher} → {room} {slot}")

Tracing the proto fields this creates:

Reading the statistics: After solving, NumConflicts() tells you how many first-UIP cuts the CDCL engine resolved. For this tiny 8-variable problem, it will be near zero — the problem is trivially small. On a 200-teacher, 50-room, 40-slot timetable, NumConflicts() in the tens of thousands is normal, and WallTime() may exceed your time limit — which is exactly when relative_gap_limit becomes valuable.