A Quadratic Propagator for the Inter-Distance Constraint

Claude-Guy Quimper, Alejandro Lopez-Ortiz, Gilles Pesant

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 between two variables is at least p. This restriction models, in particular, scheduling problems in which tasks require p contiguous units of a resource to be completed. Until now, the best known propagator for bound consistency had time complexity O(n3). In this work we propose a quadratic propagator 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.

Subjects: 15.2 Constraint Satisfaction; 1.12 Scheduling

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.