🧩 Constraint Solving POTD:Problem of the Day: Temporal Constraint Satisfaction Problem (Temporal CSP)

[github-actions[bot]]

Problem Statement

A Temporal Constraint Satisfaction Problem models relationships and constraints between time points and intervals. Given a set of temporal events (time points or intervals), you must assign concrete time values to each such that all temporal constraints are satisfied.

A Concrete Example

Imagine planning a manufacturing workflow with these tasks:

• Task A: Must start at time 0 and last 5 time units (ends at time 5)
• Task B: Must start after Task A ends; duration 3 units
• Task C: Must happen between Task A and Task B (temporal inequality)
• Task D: Must finish before time 20; can start anytime

Constraints:

• Task B must start at least 1 time unit after Task A ends: start[B] ≥ end[A] + 1
• Task C must occur between Task A's end and Task B's start: end[A] ≤ start[C] ≤ start[B]
• Task D must finish by time 20: end[D] ≤ 20
• All durations are non-negative integers

Task: Find valid start times for all tasks (B, C, D given A's fixed start).

Input/Output Specification

Input:

• A set of time points or intervals: P = {P1, P2, ..., Pn}
• Temporal constraints: Pi ⊕ c Pj where ⊕ is a relation (<, ≤, =, ≠, >, ≥) and c is an integer offset

Output:

• Assignments: time[Pi] = ti for each point Pi, or an interval [start[Ij], end[Ij]] for each interval Ij
• Verify all constraints are satisfied, or report "No solution"

---

Why It Matters

Project Management & Scheduling: Temporal CSP underpins tools like PERT charts and critical path analysis. Companies use these models to coordinate deadlines, dependencies, and resource availability across complex projects.

AI Planning & Robotics: Temporal constraints allow autonomous systems to schedule actions with ordered execution, resource conflicts, and synchronization points. A robot's task sequence—pick up part A, assemble, test—inherently relies on temporal reasoning.

Medical & Legal Workflows: Healthcare and legal processes often require events to happen in strict temporal order with minimum/maximum durations between steps (e.g., follow-up appointments, evidence discovery timelines).

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Decision Variables:

• For each time point Pi: Ti ∈ [min_bound, max_bound] (continuous or discrete integer)
• For each interval: S_j, E_j representing start and end times

Constraints:

• Temporal relations: Ti + c ≤ Tj (simple inequality constraints)
• Interval semantics: E_j = S_j + duration[j]
• Global constraints: element/2, cumulative/4 (for resource usage across intervals)

Advantages:

• Expressive; easy to add new constraint types
• Propagation algorithms (arc consistency) work well on linear temporal constraints
• Natural for mixed discrete/continuous time

Trade-offs:

• May require specialized algorithms (like Simple Temporal Network algorithms) for efficiency
• Large domains or many constraints can slow general-purpose CP solvers

Example Model (MiniZinc pseudo-code)

% Temporal CSP with tasks and precedence constraints
int: n = 4; % number of time points
int: max_time = 100;

var 0..max_time: t[1..n];  % time assignments

% Task durations
int: dur_A = 5;
int: dur_B = 3;

% Start times (indexed for simplicity)
% t[1] = start[A], t[2] = start[B], t[3] = start[C], t[4] = start[D]

constraint t[1] = 0;                              % A starts at 0
constraint t[2] >= t[1] + dur_A + 1;             % B starts after A ends + 1
constraint t[1] + dur_A <= t[3];                 % C starts after A ends
constraint t[3] <= t[2];                         % C starts before B
constraint t[4] + 3 <= 20;                       % D finishes by time 20

solve satisfy;

Approach 2: Interval Graphs & Shortest-Path Algorithms (STN)

Model: Build a directed constraint graph where:

• Each node represents a time point
• Each edge (Pi, Pj) has a weight w representing the constraint Pj - Pi ≤ w

Solving:

• Use Bellman-Ford or Floyd-Warshall to detect negative cycles (infeasibility)
• Extract a feasible solution from the shortest-path tree
• This is called Simple Temporal Network (STN) solving

Advantages:

• Highly efficient: O(n3) for all-pairs, O(n·m) for single-source
• Linear constraints only (no disjunctions or multiplication)
• Clear geometric interpretation

Trade-offs:

• Limited expressiveness: no general nonlinear constraints
• Cannot handle disjunctive constraints natively (e.g., "A before B OR C before D")

---

Key Techniques

1. Arc Consistency (AC-3, AC-4)

Iteratively removes domain values that cannot be part of any solution. For temporal constraints, specialized versions like Temporal Arc Consistency work directly on temporal bounds, pruning infeasible time assignments efficiently without enumerating all possibilities.

2. Simple Temporal Network (STN) Shortest-Path Algorithms

For linear difference constraints (the most common case in temporal reasoning), reducing the constraint graph to a shortest-path problem gives polynomial-time solvability. This is orders of magnitude faster than general CSP solvers for temporal-only instances.

3. Constraint Relaxation & Slack Variables

When strict feasibility is too restrictive, introduce slack variables to soften constraints (e.g., allow some deadlines to be violated with penalties). This shifts the problem to Soft Constraint Satisfaction or Weighted CSP, enabling trade-offs between competing objectives (minimize lateness vs. minimize idle time).

4. Disjunctive Constraints & Branching

When tasks cannot overlap (mutual exclusion in time), add disjunctive constraints: end[i] ≤ start[j] ∨ end[j] ≤ start[i]. Solve via branch-and-bound: try each disjunct and propagate, backtracking if infeasibility emerges.

---

Challenge Corner

Question for You:
Consider a Disjunctive Temporal CSP where some tasks have optional execution: you may choose not to run task C at all (skipping it saves 2 time units elsewhere). How would you model this using a standard Temporal CSP solver? Can you introduce a binary variable to enable/disable constraints?

Hint: Think about how to "deactivate" a set of constraints. What solver features or encoding tricks would help?

---

References

1. Dechter, R., Meiri, I., & Pearl, J. (1991). "Temporal Constraint Networks." Artificial Intelligence, 49(1–3), 61–95.

   • The seminal paper on Simple Temporal Networks and polynomial-time solvability of linear temporal constraints.

2. Rossi, F., van Beek, P., & Walsh, T. (2006). "Handbook of Constraint Programming." Elsevier.

   • Chapter 12 covers temporal constraints and scheduling in depth.

3. Barták, R. (1998). "Constraint Programming: In Search of a Killer App." (Section on Temporal Scheduling)

   • Accessible introduction to real-world temporal CSP applications in manufacturing and project planning.

4. OR-Tools Scheduling Guide: (developers.google.com/redacted)

   • Practical examples and libraries for interval-based scheduling problems.

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 · 8.1 AIC · ⌖ 5.77 AIC · ⊞ 5.8K · ◷

• expires on Aug 10, 2026, 4:39 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #50239.