Tabu search for maximal constraint satisfaction problems(10)

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

for MCRW. For the values that both methods could reach at each run (f 11), TS is on average about 3 to 4 times faster than MCRW (in terms of number of moves). For the values between 10 and 4, TS has always a higher number of successful runs than MCRW. Recall that for MCRW, only iterations leading to a real move are counted. Since such iterations leading to a move represent only 25-50% according to the instance (see Table 1), MCRW requires a number of iterations 10 to 15 times higher than that of TS. Data similar to those of Table 2 are available for all the other instances. From the data, we observe very similar behavior.

TS is on average 3 to 5 times faster (in terms of number of moves) than MCRW to reach a given cost value and this factor remains stable across all instances and for di erent cost values of a given instance.Problem f succ. 50 50 50 50 50 50 49 40 26 10 1 0 300.30.07.25.0 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 3326 8545 24332 50 11739 28242 77551 3.3 4513 10039.8 25924 50 11789 39613.3 104638 3.94 4738 12156.1 26545 50 15019 48761 107704 4.01 6293 15773.7 39941 50 15027 63067.7 132980 3.99 6306 22562.5 59051 50 15308 86265.8 227572 3.82 10722 31382.2 70505 50 16239 133856 355128 4.26 12764 43022.3 93673 47 33298 178486 415849 18585 52437.2 99010 35 85267 236837 461983 20799 64812.5 96686 25 106969 304038 493080 57146 79492.5 97850 12 132130 339752 484847 94525 94525 94525 1 425855 425855 425855 0 -

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

From Table 3, we observe that MCRW (with a maximum of 500,000 moves) obtains solutions comparable to those of TS (with a maximum of 100,000 iterations) in terms of quality. In terms of moves required by MCRW and TS, the ratio remains the same as before, i.e. around 3.5 to 4. Other experiments have been carried out where the two algorithms were run 5 times each with a much larger number of moves (2,000,000) on these instances. Similar results have been observed. Recall that there are two big di erences between the TS and MCRW algorithms. The rst one is that TS uses a tabu list while MCRW performs random walks. The second one is that the two algorithms examine the neighborhood according to two di erent strategies: TS looks at all the con icting variables while MCRW looks only at a single variable. In other words, MCRW examines much fewer neighbor solutions than TS does at each iteration. Therefore, one may ask if this second factor is responsible for the di erence of performance between these two algorithms. In order to see if this is the case, we tested a third algorithm which examines at each iteration all the con icting variables like in TS.