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

11. S. Kirkpatrick, C.D. Gelatt Jr. and M.P. Vecchi,\Optimization by simulated annealing",Science No.220, pp671-680, 1983. 12. J. Larrosa and P. Meseguer,\Optimization-based heuristics for maximal constraint satisfaction", Proc. of CP-95, pp190-194, Cassis, France, 1995. 13. A.K. Mackworth,\Constraint satisfaction", in S.C. Shapiro (Ed.) Encyclopedia on Arti cial Intelligence, John Wiley& Sons, NY, 1987. 14. S. Minton, M.D. Johnston and P. Laird,\Minimizing con icts: a heuristic repair method for constraint satisfaction and scheduling problems", Arti cial Intelligence, Vol.58(1-3), pp161-206, 1992. 15. P. Morris,\The Breakout method for escaping from local minima", Proc. of AAAI93, pp40-45, 1993. 16. C.H. Papadimitriou and K. Steiglitz,\Combinatorial optimization - algorithms and complexity", Prentice Hall, 1982. 17. B. Selman and H.Kautz,\Domain-independent extensions to GSAT: solving large structured satis ability problems", Proc. of IJCAI-93, Chambery, France, 1993. 18. B.M. Smith,\Phase transition and the mushy region in constraint satisfaction problems", Proc. of ECAI94, pp100-104, 1994. 19. E. Tsang,\Foundations of constraint satisfaction", Academic Press, 1993. 20. R.J. Wallace,\Enhancements of branch and bound methods for the maximal constraint satisfaction problem", Proc. of AAAI-96, pp188-196, Portland, Oregon, USA, 1996. 21. R.J. Wallace,\Analysis of heuristics methods for partial constraint satisfaction problems", Proc. of CP-96, LNCS 1118, pp308-322, Cambridge, MA, USA, 1996. 22. N. Yugami, Y. Ohta and H. Hara,\Improving repair-based constraint satisfaction methods by value propagation", Proc. of AAAI-94, pp344-349, Seattle, WA, 1994.

a This article was process

ed using the L TEX macro package with LLNCS style