Online Estimation of SAT Solving Runtime

Simple item page
dc.creatorHaim, Shai
dc.creatorWalsh, Toby
dc.date2009-03-04
dc.date.accessioned2026-07-07T12:48:59Z
dc.date.available2026-07-07T12:48:59Z
dc.descriptionWe present an online method for estimating the cost of solving SAT problems. Modern SAT solvers present several challenges to estimate search cost including non-chronological backtracking, learning and restarts. Our method uses a linear model trained on data gathered at the start of search. We show the effectiveness of this method using random and structured problems. We demonstrate that predictions made in early restarts can be used to improve later predictions. We also show that we can use such cost estimations to select a solver from a portfolio.
dc.description6 pages, 3 figures. Proc. of the 11th International Conf. on Theory and Applications of Satisfiability Testing, Guangzhou, China, May 2008
dc.identifierhttps://arxiv.org/abs/0903.0695
dc.identifierhttp://arxiv.org/abs/0903.0695
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/222248
dc.subjectArtificial Intelligence
dc.titleOnline Estimation of SAT Solving Runtime
dc.typetext

Files

Collections

arXiv