Global Propagation Improves Difference Constraint Solving in AI.

Difference constraints, expressed as $x - y \leq d$, are fundamental in various computational problems and are well-understood due to their connection to shortest path algorithms. However, traditional finite domain propagation algorithms in constraint programming typically process these constraints individually, which can lead to slower solving times despite guaranteeing completeness. This research proposes a novel approach: a bounds-consistent global propagator designed to handle all difference constraints simultaneously. While SAT modulo theory solvers have long incorporated theory solvers for difference constraints, the requirements for a global propagator within a constraint programming context are distinct. A key contribution is demonstrating how to explain propagations generated by this global difference constraint propagator, enabling its effective use within lazy clause generation solvers. Experimental results indicate that this global treatment of difference constraints can substantially outperform standard propagation methods, leading to significant speed improvements in constraint satisfaction problems.