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

If the Permutation constraint is to be modeled by low-level constraints, linear inequalities can be used. A particular problem, e.g., Permutation(<1, 7, 4, 3>, {A, B, C, D}), can be expressed by the following CSP:

A, B, C, D {1, 3, 4, 7}
n {1, 3, 4, 7}:   An, Bn, Cn, Dn {0, 1}

A = A1 + 3 × A3 + 4 × A4 + 7 × A7
B = B1 + 3 × B3 + 4 × B4 + 7 × B7
C = C1 + 3 × C3 + 4 × C4 + 7 × C7
D = D1 + 3 × D3 + 4 × D4 + 7 × D7

A1 + A3 + A4 + A7 = 1
B1 + B3 + B4 + B7 = 1
C1 + C3 + C4 + C7 = 1
D1 + D3 + D4 + D7 = 1

A1 + B1 + C1 + D1 = 1
A3 + B3 + C3 + D3 = 1
A4 + B4 + C4 + D4 = 1
A7 + B7 + C7 + D7 = 1

The permutation problem is very hard to recognize now. And not even the global constraint's distance measure is included in the upper solution. In contrast to the low-level formulation, the statement of a global Permutation constraint is highly declarative and easy to understand.

A local search method that is based on a low-level problem representation cannot make use of domain knowledge and is not able to recognize the low-level constraints' interactions, e.g., that it is inadvisable to compensate a change from A7 = 1 to A7 = 0 with respect to the constraint A = ...   by an activation of A3 = 1 and A4 = 1 in order to keep the constraint satisfied. The lack of a general overview and of heuristic knowledge makes the low-level approach less efficient and susceptible to cycling and getting stuck in local minima.

A low-level representation also has advantages, though. A wide variety of problems can be modeled using the general low-level representation, whereas modeling using global constraints presupposes the availability of suitable global constraints. For example, if the problem is to find an assignment such that the variables of set X are a permutation of a subset of the values of bag A, the low-level representation can easily be adapted. But a solution based on the global Permutation constraint would require a considerable effort to adapt the constraint's internal structures and heuristics, if not a redesign from scratch.

A comparison of global constraints and monolithic solutions is straightforward, regarding the global constraints as a low-level representation and the monolithic solutions as a single highly global constraint. Again, the higher-level (monolithic) system is faster as it makes better improvement decisions because of its superior overview, but it is difficult to reuse because of its specialization.

Global constraints are a compromise between the generality of low-level CSP-based local search and the efficiency of monolithic problem-tailored local search encodings (see figure below). Finding the right granularity for global constraints is up to the designer. Only very general rules apply, which are comparable to the problems of object-oriented design (see Gamma et al. [PUBLink] for a discussion and general guidelines).

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek