Automatons in CP-SAT for Rostering

2026-04-27 · Source: Blog on Activimetrics LLC · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Software Development & Engineering · Depth: Intermediate, medium

Summary

This article explores using the `add_automaton()` function within Google OR-Tools' CP-SAT solver for complex rostering problems, specifically drawing from a nurse rostering example. The author, who previously developed a doctor scheduling solver, is revisiting core abstractions to improve elegance and functionality. The nurse rostering problem involves three shifts (day, night, off) with rules like one off-shift every four days and no three consecutive night shifts. These rules are encoded into a deterministic finite automaton (DFA) graph, which is then translated into CP-SAT code using integer variables for shifts (1=day, 2=night, 3=off) and a list of state transitions. The `add_automaton()` function constrains a sequence of shift assignments for each nurse to adhere to the DFA's rules, starting from an initial state (1) and allowing any state (1-6) as a final state.

Key takeaway

For AI Engineers or Operations Researchers building complex scheduling or rostering systems, understanding CP-SAT's `add_automaton()` is crucial. This function allows you to directly encode intricate sequential rules, like those found in nurse or doctor rostering, into your optimization models. You should consider designing your rule sets as deterministic finite automata to leverage this powerful constraint, potentially simplifying your model and improving solver performance for sequence-dependent problems.

Key insights

DFAs can model complex scheduling rules for CP-SAT solvers, enabling robust constraint enforcement.

Principles

• Complex rules can be represented as DFA state transitions.
• CP-SAT's `add_automaton()` enforces DFA-based sequence constraints.

Method

Define shifts as integers, map scheduling rules to a DFA graph, then encode DFA states and transitions into CP-SAT's `add_automaton()` function with an initial and accepting states.

In practice

• Use `add_automaton()` for sequential constraint problems.
• Map shift types to integer variables for CP-SAT.
• Visualize DFA graphs to design complex rule sets.

Topics

• CP-SAT
• OR-Tools
• Rostering
• Deterministic Finite Automaton
• Constraint Programming

Code references

• hakank/hakank

Best for: Software Engineer, AI Engineer, Consultant

Related on AIssential

• More Automaton Fun — Deterministic Finite Automata effectively model complex temporal constraints for scheduling problems.
• Automaton Hum Drum — `add_automaton` in OR-Tools CP-SAT can be a "blunt instrument" for complex scheduling, often outperformed by explicit constraints.
• Exploiting Search in Symbolic Numeric Planning with Patterns — Dynamic pattern recomputation and refinement in symbolic numeric planning guides search more efficiently.
• Scheduling That Speaks: An Interpretable Programmatic Reinforcement Learning Framework — ProRL offers interpretable, programmatic reinforcement learning for scheduling, combining heuristics with Bayesian optimization.
• Revisiting SAT-based Solvers: MaxSAT Rules and Core Sequences — New Core-guided MaxSAT solvers can be derived using Non-CNF MaxSAT and Extension rules.
• Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version — A practical, polynomial compilation translates PDDL 2.1 durative actions into PDDL+ while preserving semantics.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Blog on Activimetrics LLC.