# Toward An Automaton Constraint For Local Search

```
Jun He Pierre Flener Justin Pearson
        Department of Information Technology
   Uppsala University, Box 337, SE - 751 05 Uppsala, Sweden
         Firstname.Lastname@it.uu.se
                         

```

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 [12].

## 1 Introduction

When a high-level constraint programming (CP) language lacks a (possibly global) constraint that would allow the formulation of a particular model of a combinatorial problem, then the modeller traditionally has the choice of (1) switching to another CP language that has all the required constraints, (2) formulating a different model that does not require the lacking constraints, or (3) implementing the lacking constraint in the low-level implementation language of the chosen CP language. This paper addresses the core question of facilitating the third option, and as a side effect often makes the first two options unnecessary.

The user-level extensibility of CP languages has been an important goal for over a decade. In the traditional global search approach to CP (namely heuristic-based tree search interleaved with propagation),
higher-level abstractions for describing new constraints include indexicals [17]; (possibly enriched) deterministic finite automata (DFAs) via the *automaton* [2] and *regular* [11] generic constraints; and multivalued decision diagrams (MDDs) via the mdd [5] generic constraint. Usually, a generic but efficient propagation algorithm achieves a suitable level of local consistency by processing the higher-level description of the new constraint. In the more recent local search approach to CP (called constraint-based local search, CBLS, in [14]), higher-level abstractions for describing new constraints include invariants [9]; a subset of first-order logic with arithmetic via combinators [16] and differentiable invariants
[15]; and existential monadic second-order logic for constraints on set decision variables [1]. Usually, a generic but incremental algorithm maintains the constraint and variable violations by processing the higher-level description of the new constraint.

In this paper, we revisit the description of new constraints via automata, already successfully tried within the global search approach to CP [2, 11], and show that it can also be successfully used within the local search approach to CP. The significance of this endeavour can be assessed by noting that 108 of the currently 313 global constraints in the *Global Constraint Catalogue* [3] are described by DFAs that are possibly enriched with counters and conditional transitions [2] (note that DFA generators can easily be written for other constraints, such as the *pattern* [4] and *stretch* [10] constraints, taking the necessarily ground parameters as inputs), so that all these constraints will instantly become available in CBLS once we show how to implement fully the enriched DFAs that are necessary for some of the described global constraints.

The rest of this paper is organised as follows. In Section 2, we present our algorithm for incrementally maintaining both the violation of a constraint described by an automaton, and the violations of