Input

Problem given in CSP form

• a set of variables V = {V₁, V2,..., V_n} with associated domains of values
• a set of constraints C = {C₁, C₂, ..., C_k} with associated error functions
• a combination function to project constraint errors on variables
• a (positive) cost function to minimize

Output

a sequence of moves (modification of the value of one of the variables) that will lead to a solution of the CSP (configuration where all constraints are satisfied) if the CSP is satisfied or to a partial solution of minimal cost otherwise.

Algorithm

Start from a random assignment of variables in V

Repeat

1. Compute errors of all constraints in C and combine errors on each variable by considering for a given variable only the constraints on which it appears
2. select the variable X (not marked as Tabu) with highest error and evaluate costs of possible moves from X
3. if no improving move exists
   then mark X tabu for a given number of iterations
   else select the best move (min - conflict) and change the value of X accordingly

until a solution is found or a maximal number of iterations is reached