A quadratic propagator for the inter-distance constraint
Claude-Guy Quimper, Alejandro López-Ortíz, Gilles Pesant · 2006
We present a new propagator achieving bound consistency for the INTER-DISTANCE constraint. This constraint ensures that, among a set of variables X1,...,Xn, the difference be-tween two variables is at least p. This restriction models, in particular, scheduling problems in which tasks require p con-tiguous units of a resource to be completed. Until now, the best known propagator for bound consistency had time com-plexity O(n3). In this work we propose a quadratic propaga-tor for the same level of consistency. We then show that this theoretical gain gives savings of an order of magnitude in our benchmark of scheduling problems.