A constraint programming framework for local search methods

We propose in this paper a novel integration of local search algorithms wit hin a constraint programming framework for combinatorial optimization probl ems, in an attempt to gain both the efficiency of local search methods and the flexibility of constraint programming while maintaining a clear separat ion between the constraints of the problem and the actual search procedure. Each neighborhood exploration is performed by branch-and-bound search, who se potential pruning capabilities open the door to more elaborate local mov es, which could lead to even better approximate results. Two illustrations of this framework are provided, including computational results for the tra veling salesman problem with time windows. These results indicate that it i s one order of magnitude faster than the customary constraint programming a pproach to local search and that it is competitive with a specialized local search algorithm.