A Decomposition-Based Implementation of Search Strategies

摘要

Search strategies, that is, strategies that describe how to explore search trees, have raised much interest for constraint satisfaction in recent years. In particular, limited discrepancy search and its variations have been shown to achieve significant improvements in efficiency over depth-first search for some classes of applications. This article reconsiders the implementation of discrepancy search, and of search strategies in general, for applications where the search procedure is dynamic, randomized, and/or generates global cuts (or nogoods) that apply to the remaining search. It illustrates that recomputation-based implementations of discrepancy search are not robust with respect to these extensions and require special care which may increase the memory requirements significantly and destroy the genericity of the implementation. To remedy these limitations, the article proposes a novel implementation scheme based on problem decomposition, which combines the efficiency of the recomputation-based implementations with the robustness of traditional iterative implementations. Experimental results on job-shop scheduling problems illustrate the potential of this new implementation scheme, which, surprisingly, may significantly outperform recomputation-based schemes.