Online Estimation of SAT Solving Runtime
  We 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.
