Exploiting Stochasticity in Systematic Search: Results on a Highly Structured Domain
Abstract
We introduce a new benchmark domain for hard computational problems that bridges the gap between purely random instances and highly structured problems. We show how to obtain interesting search problems by introducing random perturbations into a structured domain, and how such problems can be used to study the robustness of search control mechanisms. Our experiments demonstrate that the performance of search strategies designed to mimic direct constructive methods degrade surprisingly quickly in the presence of even minor perturbations. On the other hand, our experiments show that by adding a random element to a complete search procedure we can dramatically improve the performance of deterministic methods. These results apply both for the case of finding consistent models as well as for the case of proving inconsistency, complementing the well known success of using randomness in incomplete model find procedures. We pushed the idea of exploiting stochasticity one step further by combining algorithms that exhibit competing behavior into portfolios. Our results show that a portfolio approach can have a dramatic impact in terms of the overall performance, in comparison to the performance of each of its component algorithms. An interesting special case is when the best strategy consists of combining copies of the same algorithm. This portfolio is analogous to the practice of 'restarts' for stochastic procedures, where the same algorithm is run repeatedly with different seeds, a common practice in the theorem proving community. Combining copies of the same algorithm into a portfolio might be a good strategy, especially in the cases that one algorithm dominates for a given class of problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1997
- Accession Number
- ADA339333
Entities
People
- Carla Gomes
Organizations
- Calspan-University of Buffalo Research Center