Opening book details…
Can I read A Decomposition-based Implementation of Search Strategies on EtoBox?
A Decomposition-based Implementation of Search Strategies by Laurent Michel; Pascal Van Hentenryck is a Computer Science article available to read on EtoBox.
What is A Decomposition-based Implementation of Search Strategies about?
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 sche
Who reads A Decomposition-based Implementation of Search Strategies?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Laurent Michel; Pascal Van Hentenryck
- Publisher
- Association for Computing Machinery; Association for Computing Machinery (ACM) (ISSN 1529-3785)
- Published
- 2004
- Language
- EN
- Field
- Computer Science (Physical Sciences)