
## 4 The Soft Cfg Constraint

We can use the WCFG constraint to encode a soft version of CFG constraint which is useful for modelling over-constrained problems. The soft CFG(G, z, [X1**, . . . , X**n])
constraint holds iff the string [X1**, . . . , X**n] is at most distance z from a string in G. We consider both Hamming and edit distances. We encode the soft CFG(G, z, [X1**, . . . , X**n])
constraint as a weighted CFG(G′, W, z, [X1**, . . . , X**n]) constraint. For Hamming distance, for each production A → a ∈ G, we introduce additional unit weight productions to simulate substitution:
{A → b, W[A → b] = 1|A → a ∈ G, A → b /∈ **G, b** ∈ Σ}
Existing productions have zero weight. For edit distance, we introduce additional productions to simulate substitution, insertion and deletion:
{A → b, W[A → b] = 1|A → a ∈ G, A → b /∈ **G, b** ∈ Σ}∪
{A → ε, W[A → ε**] = 1**|a ∈ Σ}∪
{A → Aa, W[A → Aa**] = 1**|a ∈ Σ}∪
{A → aA, W[A → aA**] = 1**|a ∈ Σ}
To handle ε productions we modify Alg. 1 so loops in lines (13),(23) run from 0 to j.

## 5 Experimental Results

We evaluated these propagation methods on shift-scheduling benchmarks [2,1]. A personal schedule is subject to various regulation rules, e.g. a full-time employee has to have a one-hour lunch. This rules are encoded into a context-free grammar augmented with restrictions on productions [7,5]. A schedule for an employee has n **= 96** slots represented by n variables. In each slot, an employee can work on an activity (ai), take a break (b), lunch (l) or rest (r). These rules are represented by the following grammar:
S → RP R, fP (i, j) ≡ 13 ≤ j ≤ 24, P → W bW, L → lL|l, fL(i, j) ≡ j = 4 S → RF R, fF (i, j) ≡ 30 ≤ j ≤ 38, R → rR|r, W → Ai, fW (**i, j**) ≡ j ≥ 4 Ai → aiAi|ai, fA(i, j) ≡ open(i), F → **P LP**
where functions f(**i, j**) are restrictions on productions and **open**(i) is a function that returns 1 if the business is opened at ith slot and 0 otherwise. To model labour demand for a slot we introduce Boolean variables b(**i, j, a**k), equal to 1 if jth employee performs activity ak at ith time slot. For each time slot i and activity ak we post a constraint Pm j=1 x(i, j, ak) > d(**i, a**k), where m is the number of employees. The goal is to minimize the number of slots in which employees worked.

We used Gecode 2.0.1 for our experiments and ran them on an Intel Xeon 2.0Ghz with 4Gb of RAM 1. In the first set of experiments, we used the weighted CFG(G, zj , X),
j = 1**, . . . , m** with zero weights. Our monolithic propagator gave similar results to the 1 We would like to thank Claude-Guy Quimper for his help with the experiments