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

The central issue in local search is the transition from one state to the successor state. As it is uncertain what kind of change improves a current state, lots of neighbor states are usually analyzed. There are no general rules here, the kind of neighborhood and successor selection being a heuristic matter.

The term heuristic already implies the existence of some domain knowledge for guidance. The heuristics of conventional local search mechanisms for CSPs, like GSAT [PUBLink] [PUBLink], can only exploit knowledge about their representation's special low-level structure, thus having to cope with self-produced complications instead of being able to incorporate higher-level domain knowledge. It is well known that there is a strong relation between a problem's representation and its computability, and it remains unclear to what kind of problems these low-level standardized representation approaches are suited. Consequently, there is often not enough information locally available to direct the search [PUBLink]. Larger variable domains than the binary ones normally used exacerbate the problem because information about qualitative differences is not directly available.

The concept of global constraints can help remedy this situation. To this end, we have to extend the notion of a global constraint:

A global constraint is a substitute for a set of lower-level constraints, additional domain knowledge allowing the application of specialized data representations and algorithms to guide and accelerate search.

A global constraint must feature a start function to construct its initial structures and inconsistency, an improvement procedure for determining a promising successor state, and an update function for its internal structures and the constraint's cost contribution in case of variable changes.

Heuristics for building neighbors and for selecting a successor can be directly encapsulated in the global constraints, where the appropriate domain knowledge is available. This is illustrated in the following sections using an example of a global constraint Permutation. The global constraint Permutation(A, X) has to ensure that the variables of set X are a permutation of the values of bag A. The costs of the constraint are to be determined by the minimal sum of the distances of the variables' current values to a valid assignment.

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek