Algorithm 1 Computation and update of the current segmentation from position s 1: **procedure** *calcSegment*(s : 1,...,n)
2: let ℓ be the number of segments picked for hV1,...,Vs−1i at the previous run; assume ℓ = 0 at the first run 3: node[1] ← 1; *inSegment* ← **true**
4: **for all** i ← s to n do 5: if the current value, say a, of Viis the label of an arc from *node*[i] to some node t **then**
6: **if not** *inSegment* **then**
7: ℓ ← ℓ+1; σℓ ← ε; *inSegment* ← **true** {c}reate a new segment 8: **end if**
9: σℓ ← σℓ· a 10: *Violation*[i] ← 0 11: **else**
12: *inSegment* ← **false** 13: *Violation*[i] ← 1 14: pick a successor t of *node*[i] with probability nbrPaths[i+1,t] / nbrPaths[i,*node*[i]]
15: **end if**
16: *node*[i+1] ← t 17: **end for**
For example, in Figure 2, with the initial assignment V = hx,e,d,e,x,xi and a first call to Algorithm 1 with s = 1, the first segment will be hx,ei (the red path). Next, the assignment V3 = d triggers a violation of 1 for decision variable V3 (we say that it is a *violated variable*) because there is no arc labelled d that connects the current node 4 in layer 3 with any nodes in layer 4. However, node 4 in layer 3 has two out-going arcs, namely to nodes 3 and 5 in layer 4 (in blue). In layer 4, there are 4 paths from node 3 to the last layer, compared to 2 such paths from node 5, so node 3 is picked with probability 46 and node 5 is picked with probability 26
(where the 2, 4, and 6 are the purple numbers by those nodes), and we assume that node 3 in layer 4 is picked. From there, we get the second segment he,x,xi (the green path), which stops at success node 5 in the last layer. The violation of the constraint is thus 1, because the value of one decision variable does not participate in any segment.

Continuing the example, we assume now that decision variable V3 is changed to value e, and hence we call Algorithm 1 with s = 3. Only ℓ = 1 segment can be kept from the previous segmentation picked for hV1,V2i, namely hx,ei (the red path). Since there is an arc labelled e from the current node 4 in layer 3, namely to node 5 in layer 4, segment ℓ is extended (line 9) to hx,e,ei. However, with decision variable V4 still having value e, this segment cannot be extended further, since there is no arc labelled e from node 5 in layer 4, and hence V4 is violated. Similarly, decision variables V5 = x and V6 = x are violated no matter which successors are picked, so no new segment is ever created. The violation of the constraint is thus 3 because the value of three decision variables do not participate in any segment.

Hence changing decision variable V3 from value d to value e would not be considered a good local move, as the constraint violation increases from 1 to 3. Changing decision variable V3 to value x instead would be a much better local move, as the first segment hx,ei is then extended to the entire current assignment hx,e,d,e,x,xi, without detecting any violated variables, so that the violation of the constraint is then 0, meaning that a satisfying assignment was found.

In Section 3, we experiment with a deterministic method [12] for picking the next node and experimentally show that our random pick is computationally quicker at finding solutions.