Computer Science – Artificial Intelligence
Scientific paper
2009-07-29
Computer Science
Artificial Intelligence
8 pages, 9 figures
Scientific paper
We present two different methods for estimating the cost of solving SAT problems. The methods focus on the online behaviour of the backtracking solver, as well as the structure of the problem. Modern SAT solvers present several challenges to estimate search cost including coping with nonchronological backtracking, learning and restarts. Our first method adapt an existing algorithm for estimating the size of a search tree to deal with these challenges. We then suggest a second method that uses a linear model trained on data gathered online at the start of search. We compare the effectiveness of these two methods using random and structured problems. We also demonstrate that predictions made in early restarts can be used to improve later predictions. We conclude by showing that the cost of solving a set of problems can be reduced by selecting a solver from a portfolio based on such cost estimations.
Haim Shai
Walsh Toby
No associations
LandOfFree
Online Search Cost Estimation for SAT Solvers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Online Search Cost Estimation for SAT Solvers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Search Cost Estimation for SAT Solvers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-521151