[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publications: [PUBLink] [PUBLink])

What is a good heuristic for building the successor state may depend on the other constraints involved as well as on the current state of the search. Thus, a global constraint should provide various heuristics, e.g., one with a complete revision of the violated variables, one with a minimal change of just one variable, one with a randomized successor selection, and one with random walks.

For the Permutation constraint, the list lc gives us quantified information about the variables' violation of the constraint. A heuristic with a cautious strategy can reset only one variable - according to the highest element in lc - to the corresponding value of la. Following the last assignment of A=2, B=9, C=2 and D=7, the variable D would be changed to 4:

lc = [1, 1, 3, 2]
la = [1, 3, 4, 7]
lx = [A(2), C(2), D(7), B(9)]
lx' = [A(2), C(2), D(4), B(9)]
Permutationcosts = 7 + (- 3 + 0) = 4

The range of heuristics to be applied to a specific problem should be customizable by the user. During search, a constraint-internal function has to decide on the concrete heuristic to be applied. This decision can be taken at random, be dependent on the current search state, or be subject to learning mechanisms.

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek