
## Acknowledgements

The authors are supported by grant 2007-6445 of the Swedish Research Council (VR), and Jun He is also supported by grant 2008-611010 of China Scholarship Council and the National University of Defence Technology of China. Many thanks to Magnus Agren (SICS) for some useful discussions on this work, ˚
and to the anonymous referees of both LSCS'09 and the Doctoral Programme of CP'09, especially for pointing out the existence of [12, 6].

## References

[1] Magnus Agren, Pierre Flener & Justin Pearson (2007): ˚ *Generic incremental algorithms for local search*.

Constraints 12(3), pp. 293–324. (Collects the results of papers at CP-AI-OR'05, *CP'05*, and *CP'06*, published in LNCS 3524, 3709, and 4204).

[2] Nicolas Beldiceanu, Mats Carlsson & Thierry Petit (2004): Deriving filtering algorithms from constraint checkers. In: Mark Wallace, editor: Proceedings of CP'04, LNCS 3258. Springer-Verlag, pp. 107–122.

[3] Nicolas Beldiceanu, Mats Carlsson & Jean-Xavier Rampon (2007): Global constraint catalogue: Past, present, and future. Constraints 12(1), pp. 21–62. Dynamic on-line version at **www.emn.fr/x-info/** sdemasse/gccat. Long version as Technical Report T2005:08, Swedish Institute of Computer Science, November 2005.

[4] St´ephane Bourdais, Philippe Galinier & Gilles Pesant (2003): *HIBISCUS: A constraint programming application to staff scheduling in health care*. In: Francesca Rossi, editor: Proceedings of CP'03, LNCS 2833.

Springer-Verlag, pp. 153–167.

[5] Kenil C. K. Cheng & Roland H. C. Yap (2008): *Maintaining generalized arc consistency on ad hoc r-ary* constraints. In: Peter J. Stuckey, editor: Proceedings of CP'08, LNCS 5202. Springer-Verlag, pp. 509–523.

[6] Willem-Jan van Hoeve, Gilles Pesant & Louis-Martin Rousseau (2006): On global warming: Flow-based soft global constraints. Journal of Heuristics 12(4-5), pp. 347–373.

[7] Mikael Z. Lagerkvist (2008): *Techniques for Efficient Constraint Propagation*. Technical Report, KTH - The Royal Institute of Technology, Stockholm, Sweden. Licentiate Thesis.

[8] Gilbert Laporte (1999): *The art and science of designing rotating schedules*. Journal of the Operational Research Society 50(10), pp. 1011–1017.

[9] Laurent Michel & Pascal Van Hentenryck (1997): *Localizer: A modeling language for local search*. In: Gert Smolka, editor: Proceedings of CP'97, LNCS 1330. Springer-Verlag, pp. 237–251.

[10] Gilles Pesant (2001): *A filtering algorithm for the stretch constraint*. In: Toby Walsh, editor: Proceedings of CP'01, LNCS 2239. Springer-Verlag, pp. 183–195.

[11] Gilles Pesant (2004): *A regular language membership constraint for finite sequences of variables*. In: Mark Wallace, editor: Proceedings of CP'04, LNCS 3258. Springer-Verlag, pp. 482–495.

[12] Benoit Pralong (2007): *Implementation de la contrainte Regular en Comet* ´ . Master's thesis, Ecole Polytech- ´
nique de Montr´eal, Canada.

[13] Jean-Charles R´egin (1996): *Generalized arc-consistency for global cardinality constraint*. In: Proceedings of AAAI'96. AAAI Press, pp. 209–215.

[14] Pascal Van Hentenryck & Laurent Michel (2005): *Constraint-Based Local Search*. The MIT Press. [15] Pascal Van Hentenryck & Laurent Michel (2006): *Differentiable invariants*. In: Fr´ed´eric Benhamou, editor:
Proceedings of CP'06, LNCS 4204. Springer-Verlag, pp. 604–619.

[16] Pascal Van Hentenryck, Laurent Michel & Liyuan Liu (2004): Constraint-based combinators for local search. In: Mark Wallace, editor: Proceedings of CP'04, LNCS 3258. Springer-Verlag, pp. 47–61.

[17] Pascal Van Hentenryck, Vijay Saraswat & Yves Deville (1993): *Design, implementation, and evaluation of* the constraint language cc(FD). Technical Report CS-93-02, Brown University, Providence, USA. Revised