On the Integration of Metaheuristic Strategies in Constraint Programming

In a recent paper, Focacci, Laburthe and Lodi (2002) surveyed the integration between Local Search and Constraint Programming which seems to be suitable to address real-world combinatorial optimization problems. In this paper, we focus on the integration of the machinery developed in the Tabu Search context into incomplete global search algorithms based on CP. The main issue is to reinterpret the techniques developed within Tabu Search for complete solutions so as to apply them to internal nodes of a tree search, i.e., to partial solutions.