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

4.1 Comparison CriteriaIn this study, we choose two criteria to compare TS and MCRW. The rst one is the quality of solution measured by the best cost value, i.e. the number of violated constraints, that a method can nd. The second criterion is the computing e ort needed by an al

gorithm to nd its best solutions or solutions of a given quality. This second criterion is measured by the number of moves and the running time. Note that the number of moves instead of iterations is used in the second criterion. The reason for this choice is the following. For TS, each move coincides with an iteration. But for MCRW, the number of moves is in general much lower than the number of iterations, because an iteration of MCRW does not lead to a move if the current value of the chosen variable is picked. In our implementation, the data structure shared by TS and MCRW has the property that an iteration which does not lead to a move is much less costly than an iteration leading to a move. Therefore, counting iterations instead of moves, will put MCRW at a disadvantage, especially if the iterations which do not lead to a move are frequent. As we explain later, this is indeed the case for MCRW.

4.2 MCSP InstancesLet us note that a satisfaction problem (such as CSP and SAT) is very different from an optimization problem (such as MCSP and MAX-SAT). There exist some interesting results such as the phase transition phenomenon which seperates under-constrained problems and over-constrained ones 1, 9, 18, 2]. Under-constrained problems tend to have many solutions. Therefore, it is usually easy to nd a satis able assignment which is also an optimal solution for the optimization problem. Over-constrained problems tend to be easy to be proven unsatis able. This means only that they are easy from the point of view of satis ability, but nothing is known about the di culty of nding a minimal cost solution from the point of view of optimization. In summary, for the satisfaction problem, hard instances tend to be around the phase transition. However, for the optimization problem, it is not possible to determine whether a given instance is di cult to solve or not except for under-constrained instances. In our expriments, we choose a classical and simple binary MCSP model and evaluate the algorithms with instances coming from su ciently diversi ed classes. More precisely, the MCSP model used depends on 4 parameters: the number n of variables, the size d of domains (all domains have the same size), the density p1 and the tightness p2 of constraints. A quadruple (n; d; p1; p2) de nes a particular class. An instance of a given class is built by choosing randomly p1:n:(n? 1)=2 constraints among the n:(n? 1)=2 di erent pairs of variables and, for each constraint, p2:d2 forbidden tuples among the d2 possible tuples. Di erent instances of a same class can be generated using di erent random seeds. Classes used in this work are taken from the following sizes: small (n/d= 50/10), medium (n/d= 100/15), large (n/d= 250/25) and very large (n/d=