Tabu search for maximal constraint satisfaction problems(3)

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

A typical repair method for MCSP begins with an inconsistent complete assignment, often generated randomly, and then repairs iteratively the current solution. To carry out a repair, a two step process is usually used: rst choose a variable and then choose a new value for the chosen variable. Many heuristics are possible for both choices leading thus to di erent repair methods 7]. One example for choosing a value for a given variable is the Min-Con icts (MC) heuristic 14].{ Min-Con icts Heuristic: For a given con icting variable1, pick a value which minimizes the number of violated constraints (break ties randomly); if no such value exists, pick randomly one value that does not increase the number of violated constraints (the current value of the variable is picked only if all the other values increase the number of violated constraints). A MC-based repair algorithm may consist simply in iterating the MC heuristic. The solving power of such a MC a

lgorithm is limited because it cannot go beyond a local optimum. However, its performance can be largely improved when some noise strategies are introduced in MC. This is exempli ed by MCRW which is a MC algorithm combined with the random-walk strategy 17]: for a given con icting variable, pick randomly a value with probability p, apply the MC heuristic with probability 1? p. More precisely, a MCRW algorithm can be de ned as in Figure 1.

MCRW algorithm begin

generate a random con guration s nb iter:= 0 nb moves:= 0 while f(s)> 0 and nb moves< max moves do

if probability p veri ed then else

choose randomly a variable V in con ict choose randomly a value v for V0 0

Figure 1: The MCRW algorithm1

end

choose randomly a variable V in con ict choose a value v that minimises the number of con icts for V (the current value is chosen only if all the other values increase the number of violated constraints) if v is di erent from the current value of V then assign v to V nb moves:= nb moves+ 1 nb iter:= nb iter+ 1 output(s);0 0

A variable is said con icting if it is involved in some unsatis ed constraints.