Consider a scheduling problem, where there are eight variables A, B, C, D, E, F, G, H each with domain {1, 2, 3, 4}. Suppose the constraints are: A > G, A H, |F B| = 1, G < H, |G C| = 1, H C is even, H 6= D, D > G, D 6= C, E 6= C, E < D 1, E 6= H 2, G 6= F, H 6= F, C 6= F, D 6= F, |E F| is odd. Show how stochastic local search can be used for the scheduling problem of this. Make sure that it tries 2000 steps before termination.

(a) For one particular run, where you select a variable that is involved in the most conflicts, and select a value that results in the minimum number of conflicts, explain which element is changed at each step and what was the resulting number of unsatisfied arcs. (You only need to show the first 5 steps). Again, explain this at a level for one of your peers to understand if this is the first time they have seen local search. (Try to make the example interesting as if you were explaining it.)

(b) Compare and explain the result of the following settings:

(i) select a variable involved in the maximum number of unsatisfied constraints, and either its best value or a random value (but tell us which one)

(ii) select any variable which is involved in unsatisfied constraints, and either its best value or a random value

(iii) a probabilistic mix of the (i) and (ii), such as with probability 0.4 select a variable involved in the most conflicts, otherwise select variable in any conflict, and either select its best value or a random value. Try a few probabilities and report on the best one found You must show and explain the runtime distributions and describe what you observe (in particular, tell us which curves correspond to which settings, when one algorithm better than another, and how often each setting does not find solutions; be specific). You should use multiple runs for each setting in the comparisons.

(c) Does a random restart help for any of these cases? Explain.

(d) Based on this experience suggest good settings for the parameters that control which algorithms is run (e.g., which method is chosen, and the probabilities that different choices are made). Justify your choice.