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

This algorithm is controlled by the random probability p, it should be clear that the value for this parameter has a big in uence on the performance of the algorithm. The tuning of this parameter is explained in Section 4.3. An iteration leading to a new con guration di erent from the current one is called a move. Note that for MCRW, many iterations do not lead to a move (see Section 4.1). An optimization is introduced as follows. If an iteration fails to lead to a move for a con icting variable V, V will not be uselessly considered for the next iterations until a move is e ectively carried out. There are other strategies to help MC to escape from local optima, we can mention for instance Breakout 15] and EFLOP 22]. Recently, some empirical studies have been reported which compare the above mentioned repair methods for solving constraint problems 7, 21]. Experimental evidence shows that MCRW is among the most powerful methods of the repair family. Consequently, MCRW is used in this paper as our reference to evaluate the performance of the TS algorithm.

3 Tabu Search for MCSPThis section gives a very brief review of Tabu Search (TS), emphasizing the most important features which have been implemented in our TS algorithm for MCSP. Instructive presentations of TS are given in 5], including many pointers to other applications. Like any LS method, TS needs three basic components: a con guration structure, a neighborhood function de ned on the con guration structure, and a neighborhood examination mechanism. The rst component de nes the search space S of the application, the second one associates with each point of the search space a subset of S while the third one prescribes the way of going from one con guration to another. A typical TS procedure begins with an initial con guration in the search space S and then proceeds iteratively to

visit a series of locally best con gurations following the neighborhood. At each iteration, a best neighbor s' 2 N(s) is sought to replace the current con guration s even if s' does not improve the current con guration in terms of the value of the cost function. This iterative process may su er from cycling and get trapped in local optima. To avoid the problem, TS introduces the notion of Tabu lists, one of the most important components of the method. A tabu list is a special short term memory that maintains a selective history H, composed of previously encountered solutions or more generally pertinent attributes of such solutions. A simple TS strategy based on this short term memory H consists in preventing solutions of H from being reconsidered for fonext k iterations (k, called tabu tenure, is problem dependent). Now, at each iteration, TS searches for a best neighbor from this dynamically modi ed neighborhood N(H,s), instead of from N(s) itself. Such a strategy prevents Tabu from being trapped in short term cycling and allows the search process to go beyond local optima.

3.1 Tabu Search