Using global constraints for local search
Alexander Nareyek · DIMACS series in discrete mathematics and theoretical computer science · 2001
. Conventional ways of using local search are difficult to generalize. Increased efficiency is the only goal, generality often being disregarded. This is manifested in the highly monolithic encodings of complex problems and the application of highly specific satisfaction methods. Other approaches take the general constraint programming framework as a starting point and try to introduce local search methods for constraint satisfaction. These methods frequently fail because they have only a very limited view of the unknown search-space structure. The present paper attempts to overcome the drawbacks of these two approaches by using global constraints. The use of global constraints for local search allows us to revise a current state on a more global level with domainspecific knowledge, while preserving features like reusability and maintenance. The proposed strategy is demonstrated on a dynamic job-shop scheduling problem. 1. Introduction The use of local search has become v...