A Quadratic Propagator for the Inter-Distance Constraint
Abstract
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.
Cite
Text
Quimper et al. "A Quadratic Propagator for the Inter-Distance Constraint." AAAI Conference on Artificial Intelligence, 2006.Markdown
[Quimper et al. "A Quadratic Propagator for the Inter-Distance Constraint." AAAI Conference on Artificial Intelligence, 2006.](https://mlanthology.org/aaai/2006/quimper2006aaai-quadratic/)BibTeX
@inproceedings{quimper2006aaai-quadratic,
title = {{A Quadratic Propagator for the Inter-Distance Constraint}},
author = {Quimper, Claude-Guy and López-Ortiz, Alejandro and Pesant, Gilles},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2006},
pages = {123-128},
url = {https://mlanthology.org/aaai/2006/quimper2006aaai-quadratic/}
}