Automaton Hum Drum

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

Summary

An analysis of scheduling project constraints using OR-Tools CP-SAT's `add_automaton` feature revealed significant performance issues despite initial optimism. The author attempted to model "call shift" rules, requiring days off post-shift, using multiple small DFAs per worker. While implementation was straightforward, a test with 65 users over 14 days resulted in a 31-second solution time (24s presolve, 7-8s solution). Furthermore, reducing users to 50 caused the solver to hit a 120-second time limit without finding a solution or determining infeasibility. Following advice from Laurent Perron, the author re-evaluated, switching to explicit implication constraints like `shift_a(day) => not(shift_a(day+1))`. This "new-old-way" approach solved the same 65-user problem in approximately 2 seconds and identified infeasibility for 50 users in 3.5 seconds, demonstrating superior performance.

Key takeaway

For Automation Engineers or Research Scientists developing complex scheduling solutions with OR-Tools CP-SAT, you should prioritize explicit constraint formulation over `add_automaton` for performance-critical problems. If your `add_automaton` models exhibit slow presolve times or struggle with feasibility checks, reconsider using direct implication constraints like `shift_a(day) => not(shift_a(day+1))`. This approach can drastically reduce solution times from minutes to seconds and improve infeasibility detection.

Key insights

`add_automaton` in OR-Tools CP-SAT can be a "blunt instrument" for complex scheduling, often outperformed by explicit constraints.

Principles

• Decomposing DFAs may not scale efficiently.
• Explicit implication constraints offer better performance.
• Consult project leads for software best practices.

Method

Model complex shift dependencies by defining indicator booleans for shift types and applying `model.add_implication` constraints, such as `today_is_setA => next_day_is_not_setDeny`, for specific shift classes and denial periods.

In practice

• Use `model.add_implication` for shift rules.
• Group shifts into "types" for constraints.
• Explicitly state "off" day requirements.

Topics

• OR-Tools CP-SAT
• Constraint Programming
• Scheduling Optimization
• Finite Automata
• Performance Tuning
• Boolean Logic

Best for: Software Engineer, Automation Engineer, Research Scientist

Related on AIssential

• Automatons in CP-SAT for Rostering — DFAs can model complex scheduling rules for CP-SAT solvers, enabling robust constraint enforcement.
• Hacking with the Automaton Constraint — Decomposing complex DFA constraints into layered, simpler automata simplifies implementation and debugging.
• NEW GPT 5.5 "Instant": ANY GOOD? — Time for strategic exploration significantly enhances AI model performance in complex reasoning tasks.
• Revisiting SAT-based Solvers: MaxSAT Rules and Core Sequences — New Core-guided MaxSAT solvers can be derived using Non-CNF MaxSAT and Extension rules.
• Petri Net Induced Heuristic Search for Resource Constrained Scheduling — RCPSP can be optimally solved via A* search on a TTPNR reachability graph using consistent combined heuristics.
• Why AI Still Can’t Solve Your Real Mathematical Optimization Problem — ORPilot's sequential, question-first AI agent approach bridges the gap between LLMs and real-world optimization problems.

Open in AIssential →

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