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

This new algorithm, that we called Steepest Descent Random Walk (SDRW), proceeds as follows. At each iteration, it performs a random walk with probability p, and a"Steepest Descent" with probability 1? p, i:e:, it seeks a best possible move among those which do not increase the cost function. The SDRW algorithm was tested on the ve instances of size n= 100 in the same conditions as for TS and MCRW. Results are presented in Table 4.Problem

tl cost value f p% cost value fmin avg max 0 1.2 2 0.45 8 9.72 12 0.45 20 21.62 24 0.45 0 0 0 0.35 19 20.78 23 0.40 90 90 89 73 80

Tabu

SDRW

Tabu-SDRW avg -2.9 -4.52 -5.33 -0.6 -5.44

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 20Table 4.

min avg max min 1 4.1 7 1 10 14.24 18 2 22 26.95 30 2 0 0.6 2 0 21 26.22 29 2

Comparative results of TS and SDRW, max

imum moves= 100,000

From Table 4, we observe that the results of SDRW are much worse than those of TS. If we compare these results with those of MCRW (Table 1), it is easy to see that SDRW gives even worse results than MCRW does. These results show that the high performance of the TS algorithm is e ectively due to the tabu memory. Table 5 gives information about the running time on a Sun SPARCstation 5 (32 RAM, 75MHz) of the TS and MCRW algorithms2. The second and third two columns (time) indicate the average running time in seconds of TS and MCRW for carrying out 100,000 moves.Problem 50.10.10.60.0 50.10.10.70.0 50.10.30.30.0 50.10.30.35.0 50.10.50.20.0 100.15.10.40.0 100.15.10.45.0 100.15.10.50.0 100.15.30.15.0 100.15.30.20.0Table 5.

Tabu MCRW Problem

time time64 80 73 89 90 84 111 154 124 142 61 70 72 81 86 96 111 127 121 142

Tabu MCRW

250.25.03.55.0 250.25.07.30.0 250.25.10.21.0 250.25.10.22.0 250.25.10.23.0 300.30.03.50.0 300.30.05.35.0 300.30.07.25.0 500.30.04.25.0

time time190 200 183 206 226 231 234 205 255 196 178 190 183 193 226 239 215 279

Running times of TS and MCRW for 100,000 moves

From Table 5, we observe that the running time for TS is only about 15% more important than MCRW (more for small size instances, less for large size instances) even if TS searches more larger neighborhood at each iteration. Taking into account Tables 4 and 1, we see that TS is much more e cient than MCRW.2

Both TS and MCRW are implemented in C++.