Two Circuit Constraints

2026-06-27 · Source: Blog on Activimetrics LLC · Field: Technology & Digital — Software Development & Engineering, Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Advanced, long

Summary

An analysis of OR-Tools' CP-SAT solver, specifically the `bus_driver_scheduling_sat` example, investigates whether replacing custom circuit logic with the official `model.add_circuit(arcs)` API improves performance. Initial attempts to integrate `add_circuit` for individual drivers yielded similar results but were slightly slower, with tiny instances taking over 2 seconds compared to under 2 seconds, and small instances averaging around 45 seconds versus under 45 seconds. A more invasive change to use a single `model.add_multiple_circuit(arcs)` for all drivers initially resulted in an infeasible solution due to the constraint's nature, then worked but was consistently slower, with small instances running at approximately 60 seconds instead of 40 seconds. Subsequent attempts to reintroduce redundant constraints or nest circuit calls also failed to improve solver speed.

Key takeaway

For optimization engineers developing scheduling solutions with OR-Tools' CP-SAT solver, if you are considering replacing custom circuit logic with `add_circuit` or `add_multiple_circuit` for performance gains, this analysis suggests it may not yield speed improvements and could even slow down solutions like bus driver scheduling. Prioritize alternative problem formulations, such as those focusing on break placements, for potential performance benefits rather than direct API replacements.

Key insights

Directly replacing custom circuit logic with OR-Tools' CP-SAT `add_circuit` or `add_multiple_circuit` did not improve solver performance for bus driver scheduling.

Principles

• CP-SAT circuit constraints require exactly one incoming and one outgoing selected arc per node.
• The `add_multiple_circuit` allows multiple outgoing arcs from the source node.
• Redundant constraints may not always improve solver speed or efficiency.

Method

The author modified an existing `bus_driver_scheduling_sat` program by replacing custom circuit logic with `model.add_circuit` and later `model.add_multiple_circuit`, populating `arcs` with (source, destination, literal) tuples and linking arc literals to `performed` variables.

In practice

• Use positive integers for node indices, reserving 0 for the source/sink node.
• Link arc literals with `performed` variables using `model.add_implication` for logical consistency.
• Consider `model.add_multiple_circuit` for problems requiring multiple paths originating from a single source node.

Topics

• OR-Tools
• CP-SAT Solver
• Circuit Constraint
• Bus Driver Scheduling
• Constraint Programming
• Optimization Performance

Code references

• google/or-tools

Best for: Software Engineer, AI Engineer, Research Scientist

Related on AIssential

• Two Scheduling Examples — Explicitly modeling shift order and cumulative state within a solver's network is crucial for complex temporal scheduling constraints like mandatory breaks.
• Automatons in CP-SAT for Rostering — DFAs can model complex scheduling rules for CP-SAT solvers, enabling robust constraint enforcement.
• MINLP instead of indicator constraints? — Replacing indicator constraints with direct multiplication creates competitive MINLP models.
• Towards Efficient Constraint Handling in Neural Solvers for Routing Problems — CaR efficiently handles complex VRP constraints by jointly training construction and lightweight refinement modules with shared representations.
• Transforming Constraint Programs to Input for Local Search — Automatically generating local search neighborhoods from constraint specifications by linking symmetry properties reduces human intervention in combinatorial optimization.
• Petri Net Induced Heuristic Search for Resource Constrained Scheduling — RCPSP can be effectively solved via A* search on a Petri Net reachability graph using a consistent combined heuristic.

Open in AIssential →

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