Toward an automaton Constraint for Local Search

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.