Abstract. This paper presents a Tabu Search (TS) algorithm for solving maximal constraint satisfaction problems. The algorithm was tested on a wide range of random instances (up to 500 variables and 30 values). Comparisons were carried out with a min-confl

300/30, 500/30). For each size, we choose one or several values for the couple (p1;p2) in such a way that the instances of the class are not easily satis able and have a cost value smaller than 30.

4.3 Parameter tuni

ng for TS and MCRWThe performance of TS and MCRW is greatly in uenced by some parameters: the size of tabu list tl and the random walk probability p. We use the following procedure to determine the appropriate values for these parameters for each class of instances. First, a preliminary study determined the following ranges of parameter values: 10 tl 35 and 0:02 p 0:1. Then, di erent discrete values between these ranges were further tested as follows. For TS (respectively MCRW) each of the values f10, 15, 20, 25, 30, 35, 40, 45g (f0.02, 0.03, 0.04, 0.05, 0.07, 0.1, 0.2, 0.3, 0.4g for MCRW) was used to run 50 times on the class (10 instances, 5 runs per instance, each run being limited to 50,000 moves) and the best value identi ed for the class.

4.4 ResultsProblem

tl cost value f

Tabu

50.10.10.60.0 15 50.10.10.70.0 15 50.10.30.30.0 15 50.10.30.35.0 15 50.10.50.20.0 15 100.15.10.40.0 15 100.15.10.45.0 25 100.15.10.50.0 30 100.15.30.15.0 10 100.15.30.20.0 20 250.25.03.55.0 40 250.25.07.30.0 30 250.25.10.21.0 25 250.25.10.22.0 30 250.25.10.23.0 35 300.30.03.50.0 45 300.30.05.35.0 35 300.30.07.25.0 25 500.30.04.25.0 30Table 1.

min avg max 4 4 4 0.05 14 14 14 0.05 5 5.08 6 0.05 15 15 15 0.05 8 8 8 0.05 0 1.2 2 0.03 8 9.72 12 0.03 20 21.62 24 0.03 0 0 0 0.03 19 20.78 23 0.03 6 8.42 12 0.02 7 11.68 14 0.03 3 4.88 7 0.03 8 10.86 14 0.03 15 19.18 22 0.02 5 10.1 15 0.03 9 13.96 17 0.02 1 3.48 6 0.02 0 1.56 3 0.02

p% cost value f42 35 38 33 36 35 30 26 27 25 28 34 33 34 32 28 28 32 36

MCRW

Tabu-MCRW avg 0 0 -0.42 -0.18 -0.26 -1.13 -1.3 -1.55 -0.06 -1.51 -3.93 -2.97 -2.02 -3.31 -3.77 -4.79 -4.04 -3.56 -4.41

min avg max min 4 4 4 0 14 14 14 0 5 5.5 6 0 15 15.18 16 0 8 8.26 9 0 1 2.33 4 -1 8 11.02 13 0 20 23.18 27 0 0 0.06 1 0 19 22.3 25 0 6 12.36 15 0 10 14.66 19 -3 3 6.9 10 0 10 14.17 19 -2 19 22.96 27 -4 8 14.9 22 -3 14 18 23 -5 4 7.04 11 -3 3 5.97 13 -3

Comparative results of TS and MCRW, maximum moves= 100,000

Table 1 gives a summary of the results of TS and MCRW for the instances we have tested in terms of quality of the solutions. To obtain these results, both algorithms were run 50 times on each instance, each run being given a maximum of 100,000 moves. The parameter of each algorithm (the size of tabu list tl and the random-walk probability p) is xed according to the best value found during the parametric study. For each algorithm, we give the minimum, average and maximum value of the cost function. For MCRW, we also give the