
| optimisation time (ms)   | number of iterations   |              |            |              |      |      |      |      |
|--------------------------|------------------------|--------------|------------|--------------|------|------|------|------|
| instance                 | our method             | regular [12] | our method | regular [12] |      |      |      |      |
| avg                      | σ                      | avg          | σ          | avg          | σ    | avg  | σ    |      |
| (2d,1e,1n,2x)· 1         | 2                      | 3            | 44         | 26           | 11   | 9    | 10   | 7    |
| (2d,1e,1n,2x)· 2         | 12                     | 12           | 182        | 65           | 34   | 46   | 22   | 9    |
| (2d,1e,1n,2x)· 3         | 25                     | 13           | 478        | 201          | 46   | 29   | 41   | 17   |
| (2d,1e,1n,2x)· 4         | 51                     | 27           | 834        | 254          | 72   | 49   | 56   | 18   |
| (2d,1e,1n,2x)· 5         | 79                     | 42           | 1546       | 876          | 106  | 61   | 87   | 51   |
| (2d,1e,1n,2x)· 6         | 135                    | 76           | 2414       | 1233         | 156  | 101  | 113  | 59   |
| (2d,1e,1n,2x)· 7         | 188                    | 123          | 4517       | 3276         | 189  | 140  | 181  | 134  |
| (2d,1e,1n,2x)· 8         | 233                    | 112          | 4473       | 1958         | 202  | 113  | 160  | 71   |
| St Louis Police          | 3990                   | 4012         | 67159      | 55632        | 5389 | 5598 | 3949 | 3159 |

Table 6: Comparison between our method and *regular* [12]: average and standard deviation of optimisation times (in milliseconds) and numbers of iterations to the first solutions; rotating nurse schedules
(100 runs) and the St Louis Police instance (50 runs), from *non-random* initial assignments.

enjoy a day off. Any number of consecutive workdays must be between three and eight, and any change in work shift can only occur after two to seven days off. The problem has other vertical constraints; for example, no team can work in the same shift on four consecutive Mondays. Further, the problem has complex *pattern* constraints that limit possible changes of work shifts; for example, only the patterns
(d,x,d), (e,x,e), (n,x,n), (d,x,e), (e,x,n), and (n,x,d) are allowed. For this hard real-life problem, our method still works well: experimental results can also be found in Tables 5 and 6.

It is possible to post (see Figure 3) the constraints of the rotating nurse problem using the differentiable invariants [15] of *Comet*. This is possible in general for any automaton by encoding all the paths to a success state by using *Comet*'s conjunction and disjunction combinators. As the automata get larger, these expressions can become too large to post, and even when it is possible to post these expressions our current experiments show that our approach is more efficient.

## 4 Conclusion

In summary, we have shown that the idea of describing novel constraints by automata can be successfully imported from classical (global search) constraint programming to constraint-based local search (CBLS).

Our violation algorithms take time linear in the number of decision variables, whereas the propagation algorithms take amortised time linear in the number of arcs of the unrolled automaton [2, 11]. We have also experimentally shown that our approach is competitive with the CBLS approach of [12].

There is of course a trade-off between using an automaton to describe a constraint and using a handcrafted implementation of that constraint. On the one hand, a hand-crafted implementation of a constraint is normally more efficient during search, because properties of the constraint can be exploited, but it may take a lot of time to implement and verify it. On the other hand, the (violation or propagation) algorithm processing the automaton is implemented and verified once and for all, and our assumption is that it takes a lot less time to describe and verify a new constraint by an automaton than to implement and verify its algorithm. We see thus opportunities for rapid prototyping with constraints described by automata: once a sufficiently efficient model, heuristic, and meta-heuristic have been experimentally determined with