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

average percentage of iterations that lead e ectively to moves (column%). The last two columns indicate the di erence between the cost function of Tabu and MCRW, in minimum and average. From the data of Table 1, the following observations may be made. For small instances, both methods obtain the same minimum for the cost function. For medium and large instances, TS obtains better results for 4 out of 10 instances (a smaller cost value, -1 to -4). For the 4 very large instances, TS obtains much better results (-

3 to -5). If we look at the average cost of the two algorithms, we see that TS obtains better results than MCRW for 17 out of 19 instances and the same results for the 2 others (seemingly easy ones). Finally, note that less than half (25-42%) of MCRW iterations lead to moves (column%). Table 2 gives more details about the performance of TS and MCRW. This table shows di erent values of the cost function together with the number of successful runs, the minimal, average and maximal number of moves (for the successful runs). The last column gives the ratio between the average number of moves between MCRW and TS, and hence indicates how much TS is faster than MCRW (in terms of number of moves). For instance, the rst line means that both algorithms reach the cost f=15 at each of 50 runs, but TS needs on average a number of moves 3.49 times smaller than MCRW. Note that although only one instance is showed here, other instances have very similar behaviors.Problem f succ. 50 50 50 50 50 50 50 50 50 50 49 40 26 10 1 0 300.30.07.25.0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Tabu MCRW MCRW/Tabu#moves succ.#moves#moves min avg max min avg max avg 1656 4299.7 7850 50 6013 15022.2 33009 3.49 1918 4864.6 9731 50 6324 17051.6 39896 3.5 2010 5622.5 11330 50 6367 21506.4 40769 3.82 2018 6755.7 15415 50 8694 25244.7 68226 3.73 3326 8545 24332 50 8701 33708.5 75467 3.94 4513 10039.8 25924 49 9399 41296.3 96774 4738 12156.1 26545 45 9438 46655.4 99023 6293 15773.7 39941 37 17335 53922.2 98593 6306 22562.5 59051 34 20969 63521.8 95867 10722 31382.2 70505 20 29033 69506.3 99111 12764 43022.3 93673 9 51662 70315.4 88173 18585 52437.2 99010 4 76503 85380 96824 20799 64812.5 96686 0 57146 79492.5 97850 0 94525 94525 94525 0 0 -

Table 2. More detailed comparative results of TS and MCRW, maximum moves= 100,000 for TS and MCRW

In order to see if MCRW can catch up with TS if MCRW is given more moves, a second experiment was performed with MCRW on 2 medium and 2 large instances. In this experiment, the number of moves is extended from 100,000 to 500,000. Table 3 shows the results of this experiment for 300:30:07:25:0 as in Table 2. From Table 2, we may make the following remarks about this instance. The minimum cost value that an algorithm can reach at each run is 6 for TS and 11 for MCRW. The minimum cost value reached (at least once) is 1 for TS and 4