(PDF) Lars Hellsten, Gilles Pesant, and Peter van Beek. A domain consistency algorithm for the stretch constraint. Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming, Toronto, Ontario, 290-304, September, 2004.
The stretch constraint occurs in many rostering problems that arise in the industrial and public service sectors. In this paper we present an efficient algorithm for domain consistency propagation of the stretch constraint. Using benchmark and random instances, we show that this stronger consistency sometimes enables our propagator to solve more difficult problems than a previously proposed propagation algorithm for the stretch constraint. We also discuss variations of the stretch constraint that seem simple and useful, but turn out to be intractable to fully propagate.