Automatons in CP-SAT for Rostering 2026-04-27

I have a long-term client who needs to schedule doctors according to their capabilities, but also according to a complex set of rules. I developed a working solver years ago using OR-Tools and CP-SAT. Everytime they ask for some small improvement, I take the opportunity to revisit my core abstractions to see if I can’t figure out a more elegant way to approach the problem.

Recently I’ve been studying a published example of nurse rostering that uses the add_automaton() function from CP-SAT. I believe this is a good approach that will fix all the things, so I am writing this series of blog posts. In the end, I think I’ve unvented something relating to the DFA graph’s dual, but we’ll see if that has legs.

Nurse Rostering using a DFA

I found out about using a deterministic finite automaton (DFA) to solve a scheduling problem when I was reading through some of Hakan Kjellerstrand’s excellent set of worked examples at https://github.com/hakank/hakank. In that repository he has several versions of the nurse rostering problem that come from the minizinc tutorial at https://docs.minizinc.dev/en/stable/predicates.html#regular. This example states that there are three possible shifts for nurses: a day shift (D), a night shift (N), and an off shift (O). Each nurse must have one off shift every 4 days, and no nurse can work three nights in a row. These rules can be expressed using the following graph.

While I had a hard time coming up with this graph on my own when I first read the problem, it isn’t too difficult to see what it is doing by tracing the nodes. Starting with state 1, there are three outbound links representing each of the possible shifts. If shift “d” is assigned, the current state moves from 1 to 2. If shift “n” is assigned, the state moves from 1 to 3. And if shift “o” is assigned, the state loops from 1 back to 1. In fact, if shift “o” is ever assigned, the state always reverts back to state 1.

Working from state 2, if “d” or “n” are assigned, the state moves to state 4, and from there to state 6. Once reaching state 6 from 2 and 4, it must be true that three shifts have been assigned–one day shift, followed by any of 2 night shifts, a day and a night, or two day shifts. This means that the next shift assigned must be “o” or off, meaning the state must loop back to state 1.

If the first assigned shift is a night shift (state 3), then the path forward is a little bit more complicated. This is because three night shifts in a row is not allowed. This is tracked as follows. From state 3, both a day shift and a night shift are possible. If a “d” is assigned, the state moves to state 4, as the sequence of night shifts is broken. On the other hand, if “n” is assigned, then that means there have been two night shifts in a row, and we move to state 5. Because another night shift is not allowed, state 5 only allows a day shift and an off shift. Assigning “d” moves the state to 6, where the only possible assignment is off and back to state 1.

Converting the DFA to code

In Mr. Kjellerstrand’s implementation, he uses the add_automaton() API call to encode this graph. The doc string for the add automaton call is as follows:

An automaton constraint takes a list of affine expressions (a * var + b) (of size n), an initial state, a set of final states, and a set of transitions. A transition is a triplet (tail, transition, head), where tail and head are states, and transition is the label of an arc from head to tail, corresponding to the value of one expression in the list of expressions.

This automaton will be unrolled into a flow with n + 1 phases. Each phase contains the possible states of the automaton. The first state contains the initial state. The last phase contains the final states.

Between two consecutive phases i and i + 1, the automaton creates a set of arcs. For each transition (tail, transition, head), it will add an arc from the state tail of phase i and the state head of phase i + 1. This arc is labeled by the value transition of the expression expressions[i]. That is, this arc can only be selected if expressions[i] is assigned the value transition.

A feasible solution of this constraint is an assignment of expressions such that, starting from the initial state in phase 0, there is a path labeled by the values of the expressions that ends in one of the final states in the final phase.

Following this definition, the arcs in the graph represent the transitions. Since everything in OR-Tools is an integer, these transitions must be coded as an integer variable (IntVar) as follows:

# The different shifts
day_shift   = 1
night_shift = 2
off_shift   = 3
shifts = [day_shift, night_shift, off_shift]

# Transitions for AddAutomaton
transitions = [
  (1,off_shift,1),
  (1,day_shift,2),
  (1,night_shift,3),
  (2,off_shift,1),
  (2,day_shift,4),
  (2,night_shift,4),
  (3,day_shift,4),
  (3,off_shift,1),
  (4,day_shift,6),
  (4,off_shift,1),
  (4,night_shift,6),
  (5,day_shift,6),
  (5,off_shift,1),
  (6,off_shift,1),
]

x = {}
for i in range(num_nurses):
  for j in range(num_days):
    x[i, j] = model.NewIntVar(min(shifts), max(shifts), 'x[%i,%i]' % (i, j))

In words, a shift assignment occurs each day for each nurse. This shift assignment is a transition arc in the graph. This transition is coded by an integer between 1 and 3. What needs to be done next is to constrain this sequence of shift assignments to obey the rules of the automaton graph.

initial_state = 1
accepting_states = [1, 2, 3, 4, 5, 6]

for i in range(num_nurses):
  y = [x[i, j] for j in range(num_days)]
  model.add_automaton(y, initial_state, accepting_states, transitions)

Here the add_automaton() call tells the solver that for each nurse i, the sequence of assigned shifts y must obey the automaton rules encoded in the transitions list. Two additional items are that the automaton starts at state 1, and the allowed final states are any of the possible states, 1 through 6.

Next steps

So this is great, but I have many questions. First and foremost, how can I create a similiar graph structure to represent my use case? Related, how is it that the simple nurse rostering rules were used to create this graph structure. I mean, it is easy enough to figure out the graph by trial and error, but I want to do it programmatically. I plan to write a series of posts exploring these questions. But in the spirit of publishing more and more often, I am going to cut the scroll here and post this. Hopefully it will help guide somebody to how to use the automaton constrain in their own applications.