An automaton Constraint for Local Search

Issue title: RCRA 2009 Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion

Article type: Research Article

Authors: He, Jun | Flener, Pierre | Pearson, Justin

Affiliations: Department of Information Technology, Uppsala University, Box 337, SE-751 05 Uppsala, Sweden. {Jun.He; Pierre.Flener; Justin.Pearson}@it.uu.se

Note: [] Address for correspondence: Department of Information Technology, Uppsala University, Box 337, SE-751 05 Uppsala, Sweden

Abstract: We explore the idea of using automata to implement new constraints for local search. This is already a successful approach in constraint-based global search. We show how to maintain the violations of a constraint and its variables via a deterministic finite automaton that describes a ground checker for that constraint. We extend the approach to counter automata, which are often much more convenient than finite automata, if not more independent of the constraint instance. We establish the practicality of our approach on several real-life combinatorial problems.

Keywords: Automaton constraint, Counter automaton, Local search

DOI: 10.3233/FI-2011-401

Journal: Fundamenta Informaticae, vol. 107, no. 2-3, pp. 223-248, 2011