
Modelling a school timetable with CP-SAT: a worked example in Python
A runnable model for developers and the operations-research community: one Boolean per lesson and start, hard rules, weighted soft rules, how to get names out of an infeasible result, and how to stream progress while the solver runs.
To model a school timetable in Google OR-Tools CP-SAT, create one Boolean for each lesson and each time it could start. Require exactly one start per lesson, and allow at most one lesson per teacher, class and room in any period. Turn each preference into a penalty literal with a weight, and minimise their sum. Put each rule you want to be able to name behind an assumption literal, so that an infeasible result can say which rules collide. Publish every improved solution from a callback, so that people can watch the run and stop it.
The rest of this post builds that on a two-class school. It is written for developers and for people who work in operations research, and everything below runs on OR-Tools 9.15. We use CP-SAT in Bildena Scheduler, but this is a teaching model written for this post, not code from our engine. For the planner's view, see our earlier posts on what provably optimal means, why timetables become impossible and the layers of the product.
The problem
A week has a grid of days and periods. Each lesson needs a place in that grid, and teachers, classes and rooms can only be in one place at a time. Even, Itai and Shamir showed in 1976 that a very restricted version of this is NP-complete, so there is no formula to look for. The research community compares methods on XHSTT, a benchmark format with instances from real schools in several countries.
CP-SAT suits this shape of problem. Most decisions are yes or no, most rules touch only a few variables, and the solver gives you a proof of optimality or infeasibility when it can find one. If you are new to it, Dominik Krupke's CP-SAT Primer is a good companion to this post.
The instance
Two classes, three teachers, a five-day week of six periods, and one double Science lesson per class. Ben does not work on Fridays. We call a class a form in the code, because class is a keyword.
from collections import defaultdict
from dataclasses import dataclass
from ortools.sat.python import cp_model
DAYS, PERIODS = range(5), range(6)
@dataclass(frozen=True)
class Lesson:
id: str
form: str # the class; "class" is taken in Python
subject: str
teacher: str
length: int = 1 # 2 means a double
lessons = []
for form in ("7a", "7b"):
lessons += [Lesson(f"{form}-maths-{n}", form, "Maths", "Ada") for n in range(4)]
lessons += [Lesson(f"{form}-english-{n}", form, "English", "Ben") for n in range(4)]
lessons.append(Lesson(f"{form}-science", form, "Science", "Cal", length=2))
by_id = {l.id: l for l in lessons}
not_available = {"Ben": {(4, p) for p in PERIODS}} # Ben does not work on Fridays
Variables: one Boolean per lesson and start
model = cp_model.CpModel()
starts = {} # (lesson id, day, period) -> Boolean
options = defaultdict(list) # lesson id -> its possible starts
teacher_at = defaultdict(list) # (teacher, day, period) -> starts that occupy that cell
form_at = defaultdict(list) # (form, day, period) -> starts that occupy that cell
for l in lessons:
for d in DAYS:
for p in PERIODS:
cells = [(d, p + i) for i in range(l.length)]
if cells[-1][1] > PERIODS[-1]:
continue # a double cannot start in the last period
if any(c in not_available.get(l.teacher, ()) for c in cells):
continue # no variable, no possibility
v = model.new_bool_var(f"{l.id}@{d}.{p}")
starts[l.id, d, p] = v
options[l.id].append(v)
for day, period in cells:
teacher_at[l.teacher, day, period].append(v)
form_at[l.form, day, period].append(v)
Three choices here matter more than they look:
- No variable, no possibility. Ben's Friday is not a constraint. The variables simply do not exist. This is the cheapest rule you can write, and it has a cost that we come back to below.
- A double is one decision. It is not two lessons that have to be adjacent. One variable occupies two cells, so the adjacency cannot fail, and there is no linking constraint to write.
- Index by cell.
teacher_atandform_atlist which starts occupy each cell. Every rule below reads from them.
Interval variables with add_no_overlap are the obvious alternative, and they are a good fit when durations vary a lot. We use Booleans here because a school week has few cells and most rules in this domain are about a specific cell.
Hard rules
Every lesson happens once:
for vs in options.values():
model.add_exactly_one(vs) # every lesson happens once
And nobody is in two places:
for cell in (*teacher_at.values(), *form_at.values()):
model.add_at_most_one(cell) # nobody is in two places
A room type with several rooms is the same rule with a capacity: model.add(sum(vs) <= number_of_labs). What makes a rule hard is that it has no weight. It removes solutions from the problem, so no setting of the objective can buy a clash.
Soft rules: penalties with a weight
A teacher's gap is a free period between two lessons on the same day. CP-SAT has no such concept, so we build one from two running flags: started says a lesson has happened by this period, and ahead says one is still to come.
penalties = [] # (weight, literal)
def gap_literals(who, cells):
"""A gap is a free period with a lesson before it and a lesson after it."""
for d in DAYS:
busy = [sum(cells[who, d, p]) for p in PERIODS]
started = [model.new_bool_var("") for _ in PERIODS]
ahead = [model.new_bool_var("") for _ in PERIODS]
for p in PERIODS:
model.add(started[p] >= busy[p])
model.add(ahead[p] >= busy[p])
if p > 0:
model.add(started[p] >= started[p - 1])
if p < PERIODS[-1]:
model.add(ahead[p] >= ahead[p + 1])
gap = model.new_bool_var("")
model.add(gap >= started[p] + ahead[p] - busy[p] - 1)
yield gap
The constraints here only push one way: started can be forced true, but nothing forces it false. That is enough, because gap appears in a minimised objective with a positive weight, so the solver has no reason to set it unless it has to. This one-sided reification keeps the model smaller. It only works in this direction, though, so if you reuse gap in a hard rule, you need both directions.
Now add a penalty for the same subject twice on one day, and set the objective:
penalties += [(3, g) for t in ("Ada", "Ben", "Cal") for g in gap_literals(t, teacher_at)]
penalties += [(10, g) for f in ("7a", "7b") for g in gap_literals(f, form_at)]
same_day = defaultdict(list)
for (lesson_id, d, p), v in starts.items():
l = by_id[lesson_id]
same_day[l.form, l.subject, d].append(v)
for vs in same_day.values():
twice = model.new_bool_var("")
model.add(twice >= sum(vs) - 1)
penalties.append((5, twice))
model.minimize(sum(w * lit for w, lit in penalties))
The weights 10, 5 and 3 are invented, and that is the point: they are policy, not mathematics. Here a gap for a class costs more than a gap for a teacher. Optimality is only ever relative to these numbers. If one concern must strictly dominate another, a weighted sum is the wrong tool. Solve for the first objective, fix its value with a constraint, and then solve for the second.
Read the status before you read the timetable
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 60
status = solver.solve(model)
if status == cp_model.OPTIMAL:
print("the best timetable under these weights")
elif status == cp_model.FEASIBLE:
print(f"valid, cost {solver.objective_value}, bound {solver.best_objective_bound}")
elif status == cp_model.INFEASIBLE:
print("no timetable exists")
else:
print("out of time, with neither a timetable nor a proof")
The four outcomes mean different things, and a user interface should keep them apart. OPTIMAL means proved best for these weights. FEASIBLE means valid, with a known distance to the proved bound. INFEASIBLE means no timetable exists. UNKNOWN means the time ran out with no timetable and no proof, which says nothing about whether one exists. Reporting UNKNOWN as "impossible" is the bug to avoid here.
On this toy the answer is OPTIMAL at cost 0 straight away. That tells you nothing about a real school.
Check the answer without the solver
A bug in a model does not crash. It produces a good-looking timetable that quietly breaks a rule. So keep a checker that knows the rules and shares no code with the model:
def check(timetable):
"""Knows the rules. Knows nothing about the solver."""
seen = set()
for lesson_id, (d, p) in timetable.items():
l = by_id[lesson_id]
for i in range(l.length):
cell = (d, p + i)
assert cell not in not_available.get(l.teacher, ()), f"{lesson_id}: teacher away"
for who in (l.teacher, l.form):
assert (who, cell) not in seen, f"{who} double-booked at {cell}"
seen.add((who, cell))
assert len(timetable) == len(lessons), "a lesson is missing"
check({k: (d, p) for (k, d, p), v in starts.items() if solver.value(v)})
Run it on every result. It catches a rule that never reached the model, as soon as a timetable breaks that rule. The reverse test is just as useful: build an input that must break a rule, and require INFEASIBLE. We describe that in Inside the scheduling engine.
Why some timetables cannot exist, and how to name the reason
Many impossible timetables can be found by counting, and our post on infeasibility lists the usual families. The rest only show up when several rules interact. CP-SAT can prove those too, but INFEASIBLE is a proof without a sentence. A timetabler needs the sentence.
The tool for this is assumptions. Put each rule behind a literal, enforce the rule only if that literal is true, and tell the solver to assume all of them. If the model is infeasible, the solver reports a subset of the assumptions that is enough to cause it.
Here is a small impossible week: five Maths lessons, at most one a day, no Maths on Friday. The fourth rule is there as a distraction, because it plays no part in the clash.
def impossible_week(active):
"""Five Maths lessons, at most one a day, none on Friday: only four days are left."""
m = cp_model.CpModel()
x = {(n, d, p): m.new_bool_var("") for n in range(5) for d in DAYS for p in PERIODS}
week = lambda n: sum(x[n, d, p] for d in DAYS for p in PERIODS)
day = lambda d: sum(x[n, d, p] for n in range(5) for p in PERIODS)
rules = {
"5 lessons a week": [week(n) == 1 for n in range(5)],
"at most one a day": [day(d) <= 1 for d in DAYS],
"no Maths on Friday": [day(4) == 0],
"Monday period 6 free": [sum(x[n, 0, 5] for n in range(5)) == 0],
}
names = {}
for name in active:
lit = m.new_bool_var(name)
names[lit.index] = name
m.add_assumptions([lit])
for constraint in rules[name]:
m.add(constraint).only_enforce_if(lit)
return m, names
ALL = ["5 lessons a week", "at most one a day", "no Maths on Friday", "Monday period 6 free"]
m, names = impossible_week(ALL)
solver = cp_model.CpSolver()
solver.parameters.num_workers = 1
if solver.solve(m) == cp_model.INFEASIBLE:
print([names[i] for i in solver.sufficient_assumptions_for_infeasibility()])
Be careful with what comes back. The proto file says of this field: "Currently, this is minimized only in single-thread and if the problem is not an optimization problem, otherwise, it will always include all the assumptions." So use one worker and no objective. Even then, the result is only "enough", not "minimal". On our run this printed all four rules, including the Monday distraction. When we added a rule about another class, the solver did leave that one out, but the Monday rule stayed.
If you want to show a person the smallest explanation, shrink the set yourself with a deletion filter. Remove one rule at a time, and keep it out if the rest is still infeasible:
def minimal_core(rules):
core = list(rules)
for name in list(core):
without = [r for r in core if r != name]
m, _ = impossible_week(without)
if cp_model.CpSolver().solve(m) == cp_model.INFEASIBLE:
core = without # still impossible, so this rule was not needed
return core
print(minimal_core(ALL))
This prints the three rules that really collide. Two practical notes:
- It costs one solve per rule. Give each solve a time limit, and on
UNKNOWNkeep the rule, because you have not shown it is unnecessary. - A minimal set is one explanation, not the only one. A timetable can be impossible for several independent reasons. Fix one, and the next appears.
Now the cost we promised. Ben's Friday had no variable, so it can never appear in a core: anything you compile away disappears from your explanations. A practical way out is to keep two models. The optimisation model stays lean, and a separate diagnosis model, with no objective, states each rule explicitly behind a named literal. Group the literals at the level a person thinks at, such as "Ada's availability", and not one per cell.
Live progress
A solve can run for a while, and nobody should have to stare at a spinner. CP-SAT calls you back on every improved solution, and tells you about the bound as well.
import queue
events = queue.SimpleQueue()
class Progress(cp_model.CpSolverSolutionCallback):
def on_solution_callback(self):
events.put({
"cost": self.objective_value,
"bound": self.best_objective_bound,
"seconds": round(self.wall_time, 1),
})
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 60
solver.best_bound_callback = lambda bound: events.put({"bound": bound})
status = solver.solve(model, Progress())
On our run the stream began with {"bound": 0.0}, followed by costs of 157, 104 and so on down to 0. Keep three things in mind:
- Keep the callback short. It runs inside the solve. Put a message on a queue, and let another thread do the network call.
- Use both callbacks. The solution callback only fires when a better solution appears. On a long run the bound can move for a long time in between, and the gap is the number people care about.
- Do not invent a percentage. Nobody knows how much of a search is left. Publish what is true: the cost, the bound and the time.
The stop button is one call. stop_search stops the search asynchronously, so you can call it from another thread:
import threading
solver = cp_model.CpSolver()
threading.Timer(5, solver.stop_search).start() # in real life, the Stop button
status = solver.solve(model, Progress())
If a solution exists when you stop, the status is FEASIBLE, and solver.value reads the best one found. In our run, stopping right after the first solution gave cost 104, bound 0 and a timetable that passed check. If you stop before the first solution, the status is UNKNOWN, and there is nothing to keep. Inside the callback, self.stop_search() does the same job, which is useful for a "good enough" rule.
That leaves one gap: before the first solution, the callback has nothing to say, and on a tight school that can be the longest and most worrying part of the run. One generic way out is two phases. In the first, a lesson may stay unplaced at a cost, so every solution is a real, clash-free partial timetable, and the published number is how many lessons are still out. The second phase requires full placement and starts from the first phase's answer as a hint:
unplaced = {}
for lesson_id, vs in options.items():
unplaced[lesson_id] = model.new_bool_var(f"unplaced {lesson_id}")
model.add_exactly_one(vs + [unplaced[lesson_id]]) # replaces the first rule above
model.minimize(sum(unplaced.values()))
solver = cp_model.CpSolver()
solver.solve(model, Progress()) # the published cost now counts unplaced lessons
model.add(sum(unplaced.values()) == 0)
for v in starts.values():
model.add_hint(v, solver.value(v))
model.minimize(sum(w * lit for w, lit in penalties))
solver.solve(model, Progress()) # second phase: the quality search
Note that minimize replaces the earlier objective. On this toy the first solution already places everything, so there is no falling number to see. On a harder instance, this pattern gives people something to watch from the start.
Two habits before you ship
Break symmetry. The four Maths lessons of 7a are interchangeable, so every timetable appears in 4! relabelled versions, and the solver may spend time telling them apart. CP-SAT looks for some symmetry on its own (see symmetry_level), but stating it yourself is cheap. Give identical lessons an order:
def position(lesson_id):
return sum(
(d * len(PERIODS) + p) * v
for (k, d, p), v in starts.items()
if k == lesson_id
)
for form in ("7a", "7b"):
for subject, count in (("maths", 4), ("english", 4)):
for n in range(count - 1):
model.add(position(f"{form}-{subject}-{n}") < position(f"{form}-{subject}-{n + 1}"))
Decide what reproducible means. A wall-clock limit depends on the machine and its load, so two runs can end in different places. For regression tests, random_seed and max_deterministic_time are the settings to look at, together with interleave_search, which the parameter file describes as deterministic "independently of num_workers" and marks as experimental.
What the toy leaves out
A real school adds a lot to this: A/B weeks, joint lessons across classes, two buildings, room types, part-time patterns and individual student choices. Repairing a timetable after one change is a different question from building it. We make no promise here about how this toy scales: the model above is a starting point for learning, and how long it takes on a real school depends on the school.
How this looks in Bildena Scheduler
Bildena Scheduler runs on CP-SAT. Hard rules are guaranteed and preferences are weighted, and when a timetable is impossible, Bildena names the rules that clash. A solve is a job on the server that continues if you leave the page. The browser subscribes to that job over SignalR and receives an update at every improved solution, and the Stop button keeps the best timetable so far. You can also start a solve from the assistant's chat: it shows the run on a card, nothing runs until you press Yes, and it follows the run for you. The assistant is free for every school, and the school can switch it off. The model behind the engine is our own and is not shown here.
Want to see a solve run live? In the free month of Bildena Scheduler a sample school is preloaded, every feature is on, and no card is needed. If you find a mistake in this post, write to info@bildena.com.


