

![0_image_0.png](0_image_0.png)

each decision variable of that constraint. In Section 3, we present experimental results establishing the practicality of our results, also in comparison to the prior approach of [12]. Finally, in Section 4, we summarise this work and discuss related as well as future work.

## 2 Incremental Violation Maintenance With Automata

In CBLS, three things are required of an implemented constraint: a method for calculating the violation of the constraint and each of its decision variables for the initial assignment (initialisation); a method for computing the differences of these violations upon a candidate local move (differentiability) to a neighbouring assignment; and a method for incrementally maintaining these violations when an actual move is made (incrementality). Intuitively, the higher the violation of a decision variable, the more can be gained by changing the value of that decision variable. It is essential to maintain incrementally the violations rather than recomputing them from scratch upon each local move, since by its nature a local search procedure will try many local moves to find one that ideally reduces the violation of the constraint or one of its decision variables.

Our running example is the following, for a simple work scheduling constraint. There are values for two work shifts, day (d) and evening (e), as well as a value for enjoying a day off (x). Work shifts are subject to the following three conditions: one must take at least one day off before a change of work shift; one cannot work for more than two days in a row; and one cannot have more than two days off in a row. A DFA for checking ground instances of this constraint is given in Figure 1. The start state 1 is marked by a transition entering from nowhere, while the success states 5 and 6 are marked by double circles.

Missing transitions, say from state 2 upon reading value e, are assumed to go to an implicit failure state, with a self-looping transition for every value (so that no success state is reachable from it).

## 2.1 Violations Of A Constraint

To define and compute the violations of a constraint described by an automaton, we first introduce the notion of a segmentation of an assignment:
Definition 1 (Segmentation) *Given an assignment V* = hd1,...,dni, a segmentation is a possibly empty sequence of non-empty sub-strings (referred to here as segments) σ1,...,σℓ *of d*1 ···dn *such that for each* σj = dp ···dq and σj+1 = dr···ds *we have that r* > q.

For example, a possible segmentation of the assignment V = hx,e,d,e,x,xi is hx,ei,he,x,xi; note that the third character of the assignment is not part of any segment. In general, an assignment has multiple possible segmentations. We are interested in segmentations that are accepted by an automaton, in the following sense: