Tabu search for maximal constraint satisfaction problems(2)

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

repair techniques constitute an interesting alternative to deal with instances of very large size although neither optimality nor completeness is guaranteed. Repair methods belong in fact to a more general class of methods called Local Search (LS). Local search, which is based on the notion of neighborhood, constitutes a powerful approach for tackling hard optimization problems 16, 10]. Starting with an initial con guration, a typical local search method replaces iteratively the current con guration or solution by one of its neighbors until some stop criteria are satis ed; for example, a xed number of iterations is reached or a su ciently good solution is found. Well-known examples of LS methods incl

ude various hill-climbers, simulated annealing (SA) 11] and Tabu search (TS) 5]. TS is generally considered to be one of the most promising methods in combinatorial optimization and already shows its power for solving many hard problems including the maximal satis ability 6] and graph-coloring problem 8, 3]. In this study, we are interested in applying TS to solve MCSP and try to answer the following question: is TS a competitive method for this problem? This paper presents a TS algorithm for solving MCSP. In order to evaluate the e ectiveness of the TS algorithm, extensive experiments are carried out on a wide range of random instances (up to 500 variables and 30 values). Experimental results were compared with a min-con icts algorithm combined with random walk (MCRW), which is considered to one of the most successful method for MCSP 21]. The paper is organized as follows: after a brief review of repair methods (Section 2), we present Tabu Search and its adaptation to MCSP (Section 3). Then we de ne the context and method of the experimentation, followed by comparative results between TS and MCRW (Section 4). We conclude the paper with some conclusions and indications about our ongoing work (Section 5).

2 Repair Methods for MCSPAn instance of an optimization problem (S; f) is de ned by a set S (search space) of con gurations and a cost function f: S ! R (R being the set of real numbers). Solving such an instance consists in nding a con guration s 2 S that has the minimal (or maximal) value of the cost function f. Given a CN< X; D; C> representing respectively the set of distinct variables, value domains, and constraints, MCSP is the optimization (minimization) problem de ned by:

{ The set of con gurations S is the set of all the complete assignments s de ned by s= f< Vi; vi> j Vi 2 X and vi 2 Di g. Clearly the cardinality of the search space S is equal to the product of the sizes of the domains, i.e. Qn jDij. i=1{ The cost f(s) of a con guration s is the number of constraints violated bys.