A Quadratic Propagator for the Inter-Distance Constraint

Claude-Guy Quimper, Alejandro López-Ortiz, Gilles PesantAAAI 2006

Abstract

In Constraint Programming (CP), the Inter-Distance constraint is a fundamental tool for modeling scheduling problems where tasks must maintain a minimum temporal separation. Historically, the most efficient algorithm for enforcing bound consistency on this constraint required $O(n^3)$ time. This paper introduces a novel propagator that reduces this complexity to $O(n^2)$ by identifying redundant calculations through a concept termed "dominance." Empirical evaluations demonstrate that this quadratic approach provides an order-of-magnitude speedup over previous state-of-the-art methods and significantly outperforms commercial solvers on large-scale scheduling benchmarks.

Introduction

Scheduling problems frequently involve resources that can only handle one task at a time, requiring a minimum gap $p$ between any two tasks $i$ and $j$. This requirement is formally expressed as the Inter-Distance constraint: $|X_i - X_j| \geq p$. While this can be decomposed into multiple binary constraints, a global propagator is preferred because it offers superior "pruning"—the ability to eliminate impossible start times early in the search process.

The gold standard for pruning in this context is "bound consistency." However, the computational cost of existing $O(n^3)$ algorithms has limited their applicability in large-scale industrial settings. This work addresses this bottleneck by streamlining the calculation of adjustment intervals, the core mechanism used to prune variable domains.

Methodology

The primary innovation of this work is the reduction of time complexity from cubic to quadratic through the elimination of redundant interval calculations.

Dominance and Redundancy

The authors define a dominance relationship between pairs of release times and deadlines. They prove that if one pair of time points dominates another, the pruning information provided by the dominated pair is already subsumed by the dominant one. By sorting deadlines and release times, the algorithm can identify these relationships and avoid re-computing overlapping adjustment regions. While there are $O(n^2)$ potential adjustment intervals, the authors demonstrate that their union can be efficiently computed by examining only $O(n)$ intervals in a single pass.

Implementation and Data Structures

To maintain the $O(n^2)$ complexity, the propagator employs several advanced data structures:

  • Doubly-Linked Lists: Used to manage and merge disjoint adjustment intervals efficiently.
  • Union-Find: This structure allows the algorithm to quickly skip over time points that have already been pruned or saturated, reducing the cost of updates to nearly constant time ($O(\alpha(n))$).

The algorithm also exploits symmetry: the logic used to prune "earliest start times" (lower bounds) is applied identically to "latest start times" (upper bounds), ensuring the search space is fully constrained from both directions.

Experimental Evaluation

The proposed propagator was evaluated against the previous state-of-the-art (Artiouchine-Baptiste) and commercial solvers (ILog Solver’s IlcBasic and IlcExtended).

Scalability and Performance

A synthetic scalability test was conducted to visualize the growth in execution time as the number of tasks $n$ increases. As shown in Figure 1, the quadratic propagator maintains a much lower growth rate compared to the cubic baseline, highlighting the practical impact of the theoretical complexity reduction.

Figure 1: Scalability test comparing the execution time of the $O(n^3)$ algorithm against the proposed $O(n^2)$ propagator.

In more realistic scenarios, such as the Runway Scheduling Problem (modeling airplane landings with safety gaps), the performance gains were even more pronounced. For a problem instance involving 90 airplanes, the new propagator solved the problem in 5.64 seconds, whereas the previous state-of-the-art required over 60 seconds.

Figure 4: Performance comparison across different problem sizes ($n$).

Discussion and Future Work

The reduction of the Inter-Distance constraint's complexity to $O(n^2)$ represents a significant advancement for CP-based scheduling. By leveraging dominance lemmas and efficient data structures, the authors have made large-scale global pruning computationally feasible.

However, several avenues for future research remain. The current algorithm assumes a fixed processing time $p$ for all tasks. Extending this to "cumulative" scheduling, where tasks have varying durations, would broaden the propagator's utility. Additionally, while $O(n^2)$ is a major improvement, the theoretical possibility of an $O(n \log n)$ algorithm remains an open question. Finally, generalizing the propagator to handle variable gaps (where $p$ is a decision variable) would allow for more complex optimization in dynamic scheduling environments.

Summary updated

BibTeX
@inproceedings{quimper2006quadratic,
  author = {Claude-Guy Quimper and Alejandro López-Ortiz and Gilles Pesant},
  title = {{A Quadratic Propagator for the Inter-Distance Constraint}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure