Tabu search for maximal constraint satisfaction problems

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

Tabu Search for Maximal Constraint Satisfaction ProblemsPhilippe Galinier and Jin-Kao HaoLGI2P EMA-EERIE Parc Scienti que Georges Besse F-30000 N^mes France email: fgalinier, haog@eerie.fr

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-con icts+random-walk (MCRW) algorithm. Empirical evidence shows that the TS algorithm nds results which are better than that of the MCRW algorithm.the TS algorithm is 3 to 5 times faster than the MCRW algorithm to nd solutions of the same quality. Keywords: Tabu search, constraint solving, combinatorial optimization.

1 IntroductionA nite Constraint Network (CN) is composed of a nite set X of variables, a set D of nite domains and a set C of constraints over subsets of X. A constraint is a subset of the Cartesian product of the domains of the variables involved that speci es which combinations of values are compatible. A CN is said to be binary if all the constraints have 2 variables. Given a CN, the Constraint Satisfaction Problem (CSP) consists in nding one or more complete assignments of values to the variables that satisfy all the constraints 13] while the Maximal Constraint Satisfaction Problem (MCSP) is an optimization problem consisting in looking for an assignment that satis es the maximal number of constraints 4]. Known to be NP-complete (NP-hard) in general, both MCSP and CSP are of great importance in practice. In fact, many applications related to allocation, assignment, scheduling and so on can be modeled as a CSP or a MCSP. Methods for solving CSP include many complete algorithms based on backtracking and ltering techniques 19] and incomplete ones based on repair heuristics such as Min-con icts 14]. Similarly,methods for solving MCSP include exact algorithms based on branch-and-bound techniques 4, 12, 20] and approximation ones based on the above mentioned repair heuristics 21]. The main advantage of an exact (complete for CSP) method is its guarantee of optimality (completeness for CSP). The main drawback of such a method remains the time necessary to compute large scale instances. On the contrary,