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

Aspiration function Solution evaluation and neighborhood examinationThe aspiration criterion consists of removing a tabu classi cation from a move when the move leads to a solution better than the best obtained so far.

For MCSP, it is possible to develop special data structures to nd quickly a best neighbor among the given neighborhood. The main idea, inspired by a technique proposed in 3], is based on a two dimensional table jX j*jDj: if v is the current value of V, then V; v] indicates the the current number of con icts for V; for each v' di erent from v, V; v] indicates the the number of con icts for V if v' is assigned to V . Each time a move is executed, only the a ected elements of the table are updated accordingly. In this way, the cost for each move is constantly available and a best move can be found quickly. This technique is also used by our MCRW algorithm to nd quickly a best move among the values of a given (con icting) variable. In particular, with this data structure, iterations which do not lead to a move will have a negligible cost. We give in Figure 2 the TS algorithm integrating the above elements.0

Tabu algorithm begin

Figure 2: The Tabu Search algorithm Each iteration of TS consists in examining all the values of all the con icting variables in the current solution s and then carrying out a best move. Unlike MCRW, each iteration modi es a variable and the number of moves carried out by the algorithm is exactly the same as the number of iterations. In this section, we present comparative results between TS and MCRW over several classes of MCSP instances.

end

generate a random con guration s nb iter:= 0 initialize randomly the tabu list while f(s)> 0 and nb iter< max iter do choose a move< V; v> with the best performance among the non-tabu moves and the moves satisfying the aspiration criteria introduce< V; v> in the tabu list, where v is the current value of V remove the oldest move from the tabu list assign v to V nb iter:= nb iter+ 1 output(s);0 0

4 Experimentation and Results