[ 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])

Many successful applications of local search gain their power from efficient updates of the inconsistency information rather than from recomputations from scratch. For this purpose, additional structures often have to be maintained. In the case of the Permutation constraint, three lists can be used as additional support structures: list la with the sorted values of bag A, list lx with the variables of X sorted by their current assignments, and list lc with the ith element being the distance between the ith value of la and the value of the ith variable of lx. The costs of the Permutation constraint can be computed by summing the values of lc.

For Permutation(<1, 7, 4, 3>, {A, B, C, D}) and a current assignment of A=2, B=6, C=2 and D=7, the structures are constructed in the following way:

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

Note that by changing a variable all global constraints involving this variable must be called to update their internal structures. For the Permutation constraint, there must be a reordering of the variable in lx with a corresponding update of lc and the resulting cost sum. For example, if B changes from 6 to 9:

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

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek