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

5 ConclusionIn this paper, we presented a basic TS algorithm for solving the maximal constraint satisfaction problem. This algorithm was tested and compared on random instances of various sizes (ranging from n/d= 50/10 to n/d= 500/30). Empirical evidence shows that the TS algorithm always nds solutions of better quality, i.e. solutions having smaller number of violated constraints. Moreover, the TS algorithm is about 3 to 5 times faster than the MCRW algorithm to nd solutions of the same quality, in terms of number of moves but also of running time. This study shows clearly that the TS algorithm is very competitive compared with one of the best repair methods. More generally, Tabu Search has other important features such as intensi cation and diversi cation which may improve further the performance of the algorithm. Therefore, TS should be considered to be very promising for solving the MCSP. Several points are worthy of further studies. First, we do not know if the results of this study would remain valid on instances of other classes or models of MCSP. Moreover, it will be interesting to compare Tabu Search with the most e cient complete algorithms for solving satis able instances of CSP.

AcknowledgmentsWe would like to thank the referees of this paper for their useful comments.

References1. P. Cheeseman, B. Kanefsky and W.M. Taylor,\Where the really hard problems are", Proc. of the 12th IJCAI'90, pp163-169, 1991. 2. D.A. Clark, J. Frank, I.P. Gent, E. MacIntyre, N. Tomov, T. Walsh,\L

ocal search and the number of solutions", Proc. of CP97, pp119-133, 1996. 3. C. Fleurent and J.A. Ferland,\Genetic and hybrid algorithms for graph coloring", to appear in G. Laporte, I. H. Osman, and P. L. Hammer (Eds.), Special Issue Annals of Operations Research,"Metaheuristics in Combinatorial Optimization". 4. E.C. Freuder and R.J. Wallace,\Partial constraint satisfaction", Arti cial Intelligence, Vol.58(1-3) pp21-70, 1992. 5. F. Glover and M. Laguna,\Tabu Search", in C. R. Reeves (Ed.), Modern heuristics for combinatorial problems, Blackwell Scienti c Publishing, Oxford, GB, 1993. 6. J.K. Hao and R. Dorne,\Empirical studies of heuristic local search for constraint solving", Proc. of CP-96, LNCS 1118, pp194-208, Cambridge, MA, USA, 1996. 7. P. Hensen and B. Jaumard,\Algorithms for the maximum satis ability problem", Computing Vol.44, pp279-303, 1990. 8. A. Hertz and D. de Werra,\Using Tabu search techniques for graph coloring". Computing Vol.39, pp345-351, 1987. 9. T. Hogg, B.A. Huberman and C.P. Williams, Arti cial Intelligence, Special Issue on the Phase Transition and Complexity. Vol 82, 1996. 10. D.S. Johnson, C.H. Papadimitriou and M. Yannakakis,\How easy is local search?" Journal of Computer and System Sciences, Vol.37(1), pp79-100, Aug. 1988.