In the field of automated reasoning, scheduling and discrete decision-making have traditionally been treated as separate domains. Classical temporal reasoning often employs Disjunctive Temporal Problems (DTPs) to manage "either-or" temporal constraints, but these models typically assume that the time required between events is a fixed constant. In the AAAI-05 paper, "Augmenting Disjunctive Temporal Problems with Finite-Domain Constraints," Michael D. Moffitt, Bart Peintner, and Martha E. Pollack introduce a hybrid framework that bridges this gap.
The Problem: Conditional Temporal Constraints
In real-world scenarios, temporal constraints are frequently conditional. For instance, the travel time between two meetings depends entirely on which rooms are selected for those meetings. Modeling such dependencies in a standard DTP requires manually enumerating every possible combination of locations, leading to a combinatorial explosion. The authors address this by proposing a unified framework that reasons about temporal and non-temporal (finite-domain) constraints simultaneously.
The $DTP_{FD}$ Formalism
The authors introduce Disjunctive Temporal Problems with Finite-Domain Constraints ($DTP_{FD}$). In this system, variables are hybrid entities possessing both a temporal component ($x^t$) and a finite-domain component ($x^f$). A constraint is defined as:
$$x^t_{ij} - y^t_{ij} \leq B(x^f_{ij}, y^f_{ij})$$
Here, the bound $B$ is a function determined by the discrete assignments of the variables involved, rather than a static constant. This allows the model to capture spatial constraints (like travel time) or resource-dependent durations within a single mathematical structure.
Algorithmic Strategies
The paper evaluates three primary methods for solving $DTP_{FD}$:
- Brute-Force: Assigns all discrete values first, then solves the resulting standard DTP.
- Least-Commitment (LC): A "lazy" approach that uses the loosest possible bounds initially, only committing to specific discrete values once a valid temporal schedule is found under optimistic conditions.
- LC + Forward Checking and Bounds Propagation (FCBM): This advanced method allows the temporal and discrete solvers to communicate. If the temporal solver determines a minimum gap between events, the system prunes discrete assignments that cannot satisfy that gap.
By treating the travel-time matrix as a domain that can be pruned, the FCBM algorithm uses temporal logic as a powerful filter to eliminate non-temporal choices long before they are finalized.
Experimental Evaluation
To test these algorithms, the authors developed a custom random $DTP_{FD}$ generator. The performance was measured against variables such as the number of activities ($A$) and the probability of non-overlap constraints ($p_O$).
The results demonstrate a significant performance advantage for the hybrid approach. On highly constrained problems ($p_O = 90\%$), the LC + FCBM method achieved up to a 70x speedup over brute-force methods. As the number of activities increased to 13, the gap widened further: the 75th percentile for Brute-Force reached 152 seconds, while LC + FCBM completed the same tasks in just 2.19 seconds.
Conclusion and Future Work
The $DTP_{FD}$ framework provides a robust method for integrating discrete choices into temporal reasoning. While currently limited to pairwise dependencies between variables, the authors suggest future extensions could allow bounds to depend on the entire system state or decouple temporal and finite-domain variables for greater modeling flexibility. Despite these current limitations, the hybrid approach offers a dramatic improvement in efficiency and stability for complex scheduling problems.
Summary updated