
## 2 S. Haim And T. Walsh

model using a subset of problems T ⊂ E. For every training example t ∈ T **, we**
create a feature vector xt = {xt,1, xt,2**, . . . , x**t,k}**. We select features by removing**
those with the smallest standardised coefficient until no improvement is observed based on the standard AIC (Akaike Information Criterion). We then search for and eliminate co-linear features in the set.

Using ridge linear regression, we fit our coefficient vector w **to create a linear**
predictor fw (xi) = w T xi**. We chose ridge regression since it is quick and simple,**
and generally yields good results. We predict the log of the number of **conflicts**
as runtimes vary significantly. Since the feature vector is computed online, we do not want it to add significant cost to search. It therefore only contains features that can be calculated in (amortized) constant time. We define the **observation** window **to be that part of search where data is collected. At the end of the** observation window, the feature vector is computed and the model queried for an estimation.

Table 1. **The feature vector used by linear regression to construct prediction models**

F eature init **Observation Window**

![0_image_0.png](0_image_0.png)

Number of variables (var)√ Number of clauses (cls)√ cls/var √ √ √ √ √ √ var/cls √ √ √ √ √ √ Fraction of Binary Clauses √ √ √ √ Fraction of Ternary Clauses √ √ √ √

Avg. Clause Size √ √ √ √

Search Depth (from assignment stack) √ √ √

Search Depth (in corresponding binary tree)a √ √ √

Backjump Size √ √ √

Learnt Clause Size √ √ √ √

Conflict Clause Size √ √ √ √ Fraction of assigned vars before backtracking (abb)√ √ √ √ Fraction of assigned vars after backtracking (aab)√ √ √ √

aab.mean/abb.mean √ √ √ √

abb.mean/aab.mean √ √ √ √ log(**W BE**)√ √ √ √ √

a

**see [3] for further details**

The feature vector measures both problem structure and search behaviour.

Since data gathered at the beginning of a restart tends to be noisy, we do not open the observation window immediately. To keep the feature vector of reasonable size, we use statistical measures of features (that is, the minimum over the observation window, the maximum, the mean, the standard deviation and the last value recorded). The list of features is shown in Table 1. The only **feature** that takes more than constant time to calculate is the log(WBE) feature. This is