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

tion criterion consists of removing a tabu classi cation from a move when the move leads to a solution better than that obtained so far. Aspiration constitutes an important element of exibility in TS. TS uses an aggressive search strategy to exploit its neighborhood. Therefore, it is crucial to have special data structures which allow a fast updating of move evaluations, and reduce the e ort of nding best moves. Without this kind of technique, the e ciency of TS may be compromised. There are other interesting and important techniques available such as intensi cation and diversi cation. In this paper, we show that a TS algorithm based on the above mentioned elements may be very e cient and robust for MCSP.

Tabu restrictions may be overridden under certain conditions, called aspiration criteria. Aspiration criteria de ne rules that govern whether a solution may be included in N(H,s) if the solution is classi ed tabu. One widely used aspira-

3.2 A TS Algorithm for MCSP De nition of the neighborhoodWe choose for the TS algorithm the following neighborhood function N: S ! 2S: for each con guration s in S, s 2 N(s) if and only if s and s are di erent at the value of a single con icting variable. In other words, a neighbor of a con guration s can be obtained by changing the current value of a con icting variable in s. Note that the size of this neighborhood jN(s)j varies during the search according to the number of con icting variables in s.0 0

Tabu list and de nition of attributesA move for MCSP corresponds to changing the value v of a con icting variable V to another value v, and therefore can be characterized by a couple (attribute)< variable; value>. Consequently, when the solution s moves to s 2 N(s) by replacing the current value v of V with a new one v, the< V; v> is classi ed tabu for the next k iterations. In other words, the value v is not

allowed to be re-assigned to V during this period. Like the random probability p for the MCRW algorithm, the tabu tenure k has a big in uence on the performance of the TS algorithm. The tuning of this parameter is explained in Section 4.3. In order to implement the tabu list, we use a jX j*jDj matrix T. Each element of T corresponds to a possible move for the current con guration. When a move is done, the corresponding element of the matrix is set to the current number of iterations plus the tabu tenure k. In this way, it is very easy to know if a move is tabu or not by simply comparing the current number of iterations with that memorized in T.0 0 0