💻 computer science

PyCSP3-Scheduling: A Scheduling Extension for PyCSP3

This paper introduces PyCSP3-Scheduling, a library that extends the PyCSP3 framework with native scheduling abstractions like interval and sequence variables, which compile down to standard constraints to maintain modeling-solver separation while demonstrating mixed performance results with significant speedups on some problem families and overhead-induced regressions on others.

Original authors: Sohaib Afifi

Published 2026-05-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sohaib Afifi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master chef trying to organize a massive, complex banquet. You have dozens of dishes to cook, limited stoves, specific cooking times, and strict rules about which dish must be ready before another can be plated.

The Problem: The "Manual" Kitchen
Currently, if you want to use the popular "PyCSP3" software (a powerful tool for solving complex logic puzzles), you have to describe your kitchen in very low-level terms. You have to manually list every single pot, every second of cooking time, and write out long, tedious rules like: "If Pot A is on the stove, Pot B cannot be on the stove unless Pot A is finished."

You have to build the entire schedule from scratch, brick by brick, using basic math. It works, but it's like trying to write a novel using only individual letters without any words or grammar rules. It's easy to make a mistake, and the instructions become a messy wall of text that is hard to read or change.

The Solution: PyCSP3-Scheduling
This paper introduces a new "kitchen assistant" called PyCSP3-Scheduling. Instead of making you write out every single rule about pots and timers, this tool gives you high-level "smart ingredients":

Interval Variables (The "Smart Pot"): Instead of just a number for time, you get a "Pot" object that knows its own start time, end time, and how long it needs to cook. It even knows if it's optional (maybe you don't need to cook that dish today).
Sequence Variables (The "Conveyor Belt"): You can group pots into a line. The tool automatically knows that if Pot A is on the belt, Pot B can't be there at the same time. It even handles "setup times" (like washing the pot between dishes) automatically.
The Translator: The best part is that this assistant doesn't try to replace the chef (the solver). It takes your high-level, easy-to-read instructions and translates them back into the low-level, messy math that the computer understands perfectly.

The Experiment: Did it work?
The author tested this new tool on 261 different "recipes" (scheduling problems) ranging from simple job shops to complex hospital staffing and tournament scheduling. They compared the "Manual" method against the "Smart Assistant" method.

Here is what they found:

The Results are Identical: When the computer solved the problem perfectly, both methods got the exact same answer. The translation was 100% accurate.
Speed is a Mixed Bag:
- The Wins: For some problems (like scheduling aircraft landings or theater rehearsals), the new tool was up to 5.8 times faster. It was like switching from a bicycle to a sports car.
- The Losses: For other problems (like certain types of manufacturing or flexible job shops), the new tool was actually slower.
- Why? The author explains that sometimes, the "translation" process adds too much extra baggage. For example, if a problem involves "optional" tasks, the tool sometimes has to write out thousands of extra "if/then" rules to cover every possibility, which slows the computer down. It's like packing a suitcase with extra layers of plastic wrap just to be safe; it protects the items, but makes the suitcase heavy.

The Takeaway
PyCSP3-Scheduling is a bridge. It lets humans write scheduling models in a natural, logical way (using "Intervals" and "Sequences") without breaking the connection to the powerful solvers that do the heavy lifting.

It's Open Source: Anyone can use it for free.
It's Safe: It doesn't lock you into one specific computer program; it translates your model into a standard format that any compatible solver can read.
It's Not a Magic Bullet: While it makes modeling much easier and faster for some problems, it doesn't automatically make every problem faster. In some cases, the extra "translation steps" add a little overhead.

In short, this tool makes the job of the "chef" (the modeler) much easier and less prone to error, even if the "kitchen" (the computer solver) sometimes takes a few extra steps to process the new instructions.

Technical Summary: PyCSP3-Scheduling

Problem Statement

While PyCSP3 offers a productive environment for modeling combinatorial problems and exporting them to the XCSP3 standard, it lacks native support for high-level scheduling abstractions. Currently, modelers must encode scheduling problems using low-level integer variables (start times, durations) and manually construct arithmetic precedence constraints and disjunctions for resource conflicts. Although PyCSP3 provides global constraints like NoOverlap and Cumulative on integer arrays, the modeler must explicitly manage arrays of start times, duration lists, and resource heights. This approach obscures the inherent scheduling structure, complicates the addition of features like optionality (tasks that may or may not occur) or sequence-dependent setup times, and requires rebuilding encodings from scratch for new models. Existing industrial tools (e.g., CP Optimizer) offer scheduling objects but often couple models to specific, sometimes commercial, solvers, while standalone languages like MiniZinc lack first-class interval variable types.

Methodology

The paper introduces PyCSP3-Scheduling, a library that extends PyCSP3 with a dedicated scheduling layer. The core methodology involves:

Abstraction Layer: The library introduces two primary variable types:
- IntervalVar: Represents a task with attributes for start, end, size (duration), and presence. It supports five variants: Fixed, Flexible, Optional, Bounded, and Scaled (coupling duration to intensity profiles).
- SequenceVar: Groups a list of interval variables into an ordered sequence, typically representing a disjunctive resource (e.g., a machine), supporting type-dependent transition times.
Compilation Scheme: The library does not introduce a new solver backend. Instead, it compiles these high-level abstractions down to standard PyCSP3 variables and constraints, which are then exported as standard XCSP3 instances.
- Direct Mapping: When patterns match existing global constraints (e.g., mandatory intervals without transitions), the library emits standard XCSP3 globals like noOverlap and Cumulative.
- Decomposition: For complex cases (e.g., optional intervals with presence guards or sequence-dependent setups), the library decomposes abstractions into primitive constraints. For instance, SeqNoOverlap with optional intervals falls back to $O(n^2)$ pairwise disjunctions guarded by presence literals, as the current XCSP3 standard does not support optional intervals in global constraints.
- Hybrid Modeling: The layer is embedded within PyCSP3, allowing modelers to mix high-level scheduling constructs with raw PyCSP3 constraints (e.g., using presence_of to trigger custom counting logic).
Expression System: The library provides accessors (start_of, end_of, presence_of, etc.) that return PyCSP3 expressions, enabling complex arithmetic and logical combinations directly on interval attributes.

Key Contributions

The paper makes three specific contributions:

A Scheduling API: A comprehensive API for PyCSP3 centered on interval and sequence abstractions, supporting optionality, intensity functions, and transition-aware sequencing.
A Compilation Scheme: A mechanism that lowers these abstractions to solver-independent PyCSP3/XCSP3 constraints while preserving satisfiability and optimality.
Empirical Evaluation: A rigorous comparison of 261 paired instances (classical PyCSP3 formulation vs. scheduling formulation) across 17 model families.

Results

The evaluation was conducted on 261 paired instances using the ACE solver with a 1200-second timeout. Key findings include:

Semantic Correctness: On the 72 instances where both formulations proved optimality, the objective values matched exactly (100%), confirming the compilation introduces no semantic divergence.
Solver Status Agreement: The two formulations agreed on solver status (Optimum, Sat, Unsat, Timeout) in 80.8% of pairs. Disagreements were primarily due to timeout-related search progress differences rather than logical errors.
Performance Variance: Runtime performance varied significantly across families:
- Gains: Three families showed clear speedups: MSPSP (5.82×), AircraftLanding (3.47×), and Rehearsal (3.31×). The MSPSP gain was attributed to variable ordering artifacts in the PyCSP3 variable declaration rather than the abstractions themselves, while AircraftLanding and Rehearsal benefited from reduced model size and better structural capture.
- Regressions: Three families regressed: LotSizing (0.29×), MRCPSP (0.61×), and FlexibleJobshopScen (0.89×).
  - MRCPSP regression was traced to the compilation of optional intervals falling back to pairwise disjunctions instead of emitting a global noOverlap constraint, preventing efficient propagation.
  - LotSizing regression was linked to constraint-level encoding issues and propagation strength under timeout.
  - FlexibleJobshopScen suffered from significant structural augmentation (variable and constraint explosion) due to duplicating optional decisions across scenarios.
Structural Impact: 8 of the 17 families showed negligible structural augmentation (<1% change). For others, the scheduling formulation sometimes reduced model size (e.g., BACP, Rehearsal) and sometimes increased it significantly (e.g., FlexibleJobshopScen +383.7% constraints).

Significance and Claims

The paper positions PyCSP3-Scheduling as the first scheduling layer to provide first-class IntervalVar and SequenceVar abstractions with optionality and transition-aware sequencing while compiling to a solver-independent standard (XCSP3).

The authors emphasize that the library preserves the complete separation between modeling and solving, a core tenet of the PyCSP3 ecosystem. This allows models to remain usable with a broad ecosystem of solvers (ACE, Choco, CoSoCo, OR-Tools, CP Optimizer, etc.) without modification.

The paper is modest regarding performance claims, noting that runtime gains are not universal and are often tied to specific problem structures or solver heuristics (e.g., variable ordering). The authors explicitly state that the significant speedup in MSPSP is likely an artifact of variable declaration patterns rather than the scheduling abstractions themselves. The primary value proposition is the expressiveness and maintainability of the scheduling formulation, which reduces code complexity (e.g., a 31% reduction in lines for a flexible job-shop model) and simplifies the addition of features like optionality, even if it occasionally incurs a compilation overhead that affects runtime performance on specific problem families.

Future work is identified as extending the compilation to emit XCSP3 global constraints with optionality support (to avoid pairwise decomposition) and refining compilation rules to reduce structural overhead in outlier families.