Combining local and global search in a constraint programming environment

This paper presents several case studies which illustrate how constraint pr ogramming can benefit from the combination of global and local search techn iques, offering a flexible and efficient platform for the design of combina torial optimisation applications. For job-shop scheduling, we relate experi ments with local search procedures that use global search to intensively ex plore a given neighbourhood, in the spirit of "shuffle" methods. For preemp tive job-shop scheduling, two basic search strategies, Depth-First Search a nd Limited Discrepancy Search, are compared. For Vehicle Routing we report an Incremental Local Optimisation heuristic, combined with Limited Discrepa ncy Search. Finally, we show how ad hoc algebras can considerably enhance t he design of heuristics based on local and global search within a constrain t-programming environment. Experiments on vehicle routing will enlighten ho w such a language for "search and insert" control can enable automated tuni ng and discovery of new strategies adapted to the instances typology of the problem at stake.