Skip to main content

2000 | OriginalPaper | Buchkapitel

Boosting Search with Variable Elimination

verfasst von : Javier Larrosa

Erschienen in: Principles and Practice of Constraint Programming – CP 2000

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Variable elimination is the basic step of Adaptive Consistency [4]. It transforms the problem into an equivalent one, having one less variable. Unfortunately, there are many classes of problems for which it is infeasible, due to its exponential space and time complexity. However, by restricting variable elimination so that only low arity constraints are processed and recorded, it can be effectively combined with search, because the elimination of variables, reduces the search tree size.In this paper we introduce VarElimSearch(S,k), a hybrid meta-algorithm that combines search and variable elimination. The parameter S names the particular search procedure and k controls the tradeoff between the two strategies. The algorithm is space exponential in k. Regarding time, we show that its complexity is bounded by k and a structural parameter from the constraint graph. We also provide experimental evidence that the hybrid algorithm can outperform state-of-the-art algorithms in binary sparse problems. Experiments cover the tasks of finding one solution and the best solution (Max-CSP). Specially in the Max-CSP case, the advantage of our approach can be overwhelming.

Metadaten
Titel
Boosting Search with Variable Elimination
verfasst von
Javier Larrosa
Copyright-Jahr
2000
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/3-540-45349-0_22

Premium Partner