Reference: nareyek-01-cplocal

Reference Nareyek, A. 2001.
Using Global Constraints for Local Search.
In Freuder, E. C., and Wallace, R. J. (eds.), Constraint Programming and Large Scale Discrete Optimization, American Mathematical Society Publications, DIMACS Volume 57, 9-28.

Conventional ways of using local search are difficult to generalize. The increased efficiency is the mere goal, generality often being disregarded. This manifests in the highly monolithic encodings of complex problems and the application of highly specific satisfaction methods.

Other approaches take the declarative constraint programming framework as starting point and try to introduce local search methods for the constraint satisfaction. These methods frequently fail because they have only a very limited view of the unknown search-space structure.

The present work attempts to overcome the drawbacks of these two approaches by using global constraints. The use of global constraints for local search allows to revise a current state on a more global level with domain-specific knowledge, while preserving features like declarativeness, reusability, and maintenance. The proposed strategy is demonstrated on a dynamic job-shop scheduling problem.

Download Rules and Regulations     [PDF; 675 KB]     [download viewer]
Online Content

The article includes content from the AI Center pages below. Please note that the online pages may contain updated/revised versions, and probably do not cover the complete article: