Toward an automaton Constraint for Local Search

Jun He
(Uppsala University)
Pierre Flener
(Uppsala University)
Justin Pearson
(Uppsala University)

We explore the idea of using finite automata to implement new constraints for local search (this is already a successful technique in constraint-based global search). We show how it is possible to maintain incrementally the violations of a constraint and its decision variables from an automaton that describes a ground checker for that constraint. We establish the practicality of our approach idea on real-life personnel rostering problems, and show that it is competitive with the approach of [Pralong, 2007].

In Yves Deville and Christine Solnon: Proceedings 6th International Workshop on Local Search Techniques in Constraint Satisfaction (LSCS 2009), Lisbon, Portugal, 20 September 2009, Electronic Proceedings in Theoretical Computer Science 5, pp. 13–25.
Published: 8th October 2009.

ArXived at: https://dx.doi.org/10.4204/EPTCS.5.2 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org