Introduction
Temporal Constraint Satisfaction Problems (TCSPs) are essential for modeling time-dependent tasks in automated reasoning, ranging from satellite scheduling to circuit verification. While simple temporal problems—where events are separated by a single time interval—are computationally tractable, real-world scenarios often involve "disjunctions." These are "OR" constraints, such as "Event B happens 1 to 2 hours OR 4 to 5 hours after Event A." This paper introduces Upper-Lower Tightening (ULT), a polynomial-time algorithm designed to handle these complex disjunctions efficiently.
The Challenge of Disjunctions
The primary difficulty in TCSPs arises from the combinatorial explosion caused by disjunctive constraints. Standard path-consistency algorithms, which work well for discrete problems, become exponentially slow when applied to continuous temporal gaps. As the number of variables and intervals increases, the search space for a valid schedule grows beyond practical limits.
As shown in the figure above, a TCSP can be represented as a directed graph where nodes are time points and edges are labeled with sets of possible intervals. Managing these sets during consistency checking is the core computational bottleneck.
The ULT Algorithm: A Polynomial-Time Approximation
To address this complexity, the authors propose the ULT (Upper-Lower Tightening) algorithm. Rather than attempting to solve the full disjunctive problem directly, ULT approximates path-consistency by "sandwiching" complex constraints between their absolute minimum and maximum possible values.
The Relaxation Process
The first step in ULT is Relaxation. The algorithm simplifies the TCSP into a Simple Temporal Problem (STP) by replacing each set of disjoint intervals with a single "convex hull" interval. For example, the disjunction {[1, 2], [3, 4]} is relaxed to the single interval [1, 4].
By transforming the problem into a distance graph, the algorithm can leverage efficient graph-based distance algorithms to find the minimal network of the simplified version.
Tightening and Iteration
Once the simplified STP is solved, ULT applies the resulting tightened bounds back to the original disjunctive problem. If an original interval falls entirely outside these new bounds, it is pruned. This process repeats until no further intervals can be removed. This iterative approach is guaranteed to converge in polynomial time, providing a predictable and scalable alternative to traditional methods.
Key Results and Insights
The researchers evaluated ULT using randomly generated problem instances, varying parameters like the number of variables, intervals per constraint, and connectivity.
- 10x Performance Boost: When used as a preprocessing step for backtracking search, ULT achieved a 10-fold speedup compared to existing methods like Directional Path Consistency (DPC) or standard PC-2.
- Preprocessing as a Filter: The most significant insight is that ULT serves as an excellent filter. By pruning impossible "branches" of the search tree early, it dramatically reduces the workload for subsequent exact solvers.
- Accuracy vs. Efficiency: While ULT is an approximation, it remains remarkably accurate for problems with high connectivity. Its polynomial nature ensures it remains efficient even as problem size scales.
Conclusion
ULT offers a powerful tool for managing the complexity of disjunctive temporal constraints. By prioritizing approximation and preprocessing, it makes previously intractable scheduling problems solvable in reasonable timeframes. Future research will explore its application to qualitative temporal networks and even larger, more diverse datasets.
Summary updated