www.ai-center.com

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.
Abstract	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: Using Global Constraints for Local Search Global Constraints Global Constraints from a Local Search Perspective Internal Structures Improvement Heuristics Granularity Global Search Control A Case Study: Dynamic Job-Shop Scheduling Realization Global Action Resource Constraints Global Task Constraints Results Constraint Weights Susceptibility to Local Minima and Plateaus Randomization Random Walks Tabu Lists Extending the Constraints More Knowledge Aggressive Heuristics Conclusion