---
abstract: 'It is well known that different solution strategies work well for different types of instances of hard combinatorial problems.  As a consequence, most solvers for the propositional satisfiability problem (SAT) expose parameters that allow them to be customized to a particular family of instances.  In the international SAT competition series, these parameters are ignored: solvers are run using a single default parameter setting (supplied by the authors) for all benchmark instances in a given track.  While this competition format rewards solvers with robust default settings, it does not reflect the situation faced by a practitioner who only cares about performance on one particular application and can invest some time into tuning solver parameters for this application.  The new Configurable SAT Solver Competition (CSSC) compares solvers in this latter setting, scoring each solver by the performance it achieved after a fully automated configuration step.  This article describes the CSSC in more detail, and reports the results obtained in its two instantiations so far, CSSC 2013 and 2014.' 
address:
- 'University of Freiburg, Germany'
- 'University of Ulm, Germany'
- 'University of British Columbia, Vancouver, Canada'
author:
- Frank Hutter
- Marius Lindauer
- Adrian Balint
- Sam Bayless
- Holger Hoos
- 'Kevin Leyton-Brown'
bibliography:
- 'local.bib'
- 'lib.bib'
- 'proc.bib'
title: 'The Configurable SAT Solver Challenge (CSSC)'
---

Propositional satisfiability ,algorithm configuration ,empirical evaluation ,competition

Introduction
============

The propositional satisfiability problem (SAT) is one of the most prominent problems in AI.  It is relevant both for theory (having been the first problem proven to be NP-hard [@cook-stoc71]) and for practice (having important applications in many fields, such as hardware and software verification [@biere-dac99; @prasad-jsttt05a; @clarke2004tool], test-case generation [@stephan-ieee96; @cadar2008klee], AI planning [@kautz-aaai96a; @kautz-ijcai99], scheduling [@crawford-aaai94], and graph colouring [@gelder-color02]).  The SAT community has a long history of regularly assessing the state of the art via competitions [@Jarvisalo-aij12].  The first SAT competition dates back to the year 2002 [@simon-amai05a], and the event has been growing over time: in 2014, it had a record participation of 58 solvers by 79 authors in 11 tracks [@satchallenge14].  In practical applications of SAT, solvers can typically be adjusted to perform well for the specific type of instances at hand, such as software verification instances generated by a particular static checker on a particular software system [@babic-cav07], or a particular family of bounded model checking instances [@zarpas-sat05a].  To support this type of customization, most SAT solvers already expose a range of command line *parameters* whose settings substantially affect most parts of the solver.  Solvers typically come with robust default parameter settings meant to provide good all-round performance, but it is widely known that adjusting parameter settings to particular target instance classes can yield orders-of-magnitude speedups [@hutter-fmcad07a; @khudabukhsh-ijcai09a; @tompkins-sat11].  Current SAT competitions do not take this possibility of customizing solvers into account, and rather evaluate solver performance with default parameters. 

Unlike the SAT competition, the *Configurable SAT Solver Challenge (CSSC)* evaluates SAT solver performance *after* application-specific customization, thereby taking into account the fact that effective algorithm configuration procedures can automatically customize solvers for a given distribution of benchmark instances.  Specifically, for each type of instances $T$ and each SAT solver $S$, an automated fixed-time offline configuration phase determines parameter settings of $S$ optimized for high performance on $T$. Then, the performance of $S$ on $T$ is evaluated with these settings, and the solver with the best performance wins. 

To avoid a potential misunderstanding, we note that for winning the competition, only solver performance after configuration counts, and that it does *not* matter how much performance was improved by configuration.  As a consequence, in principle, even a parameterless solver could win the CSSC if it was very strong: it would not benefit from configuration, but if it nevertheless outperformed all solvers that were specially configured for the instance families in a given track, it would still win that track. ( In practice, we have not observed this, since the improvements resulting from configuration tend to be large.) 

The competition conceptually most closely related to the CSSC is the learning track of the international planning competition (IPC, see, e.g., the description by [@fern-ml11 [@fern-ml11]]{}[^1], which also features an offline time-limited learning phase on training instances from a given planning domain and an online testing phase on a disjoint set of instances from the same domain.  The main difference between this IPC learning track and the CSSC (other than their focus on different problems) is that in the IPC learning track every planner uses its own learning method, and the learning methods thus vary between entries.  In contrast, in the CSSC, the corresponding customization process is part of the competition setup and uses the same algorithm configuration procedure for each submitted solver.  Our approach to evaluating solver performance after configuration could of course be transferred to any other competition. ( In fact, the 2014 IPC learning track for non-portfolio solvers was won by FastDownward- [@seipp-ipc14a], a system that employs a similar combination of general algorithm configuration and a highly parameterized solver framework as we do in the CSSC.) 

In the following, we first describe the criteria we used for the design of the CSSC (Section \[sec:design\_criteria\]).  Next, we provide some background on the automated algorithm configuration methods we used when running the competition (Section \[sec:algoconf\]).  Then, we discuss the two CSSCs we have held so far (in 2013 and 2014); we discuss each of these competitions in turn (Sections \[sec:cssc2013\] and \[sec:cssc2014\]), including the specific benchmarks used, the participating solvers, and the results.  We describe two main insights that we obtained from these results:

1.   In many cases, automated algorithm configuration found parameter settings that performed much better than the solver defaults, in several cases yielding average speedups of several orders of magnitude. 

2.   Some solvers benefited more from automated configuration than others; as a result, the ranking of algorithms after configuration was often substantially different from the ranking based on the algorithm defaults (as, e.g., measured in the SAT competition). 

Finally, we analyze various aspects of these results (Section \[sec:discussion-of-results\]) and discuss the implications we see for future algorithm development (Section \[sec:conclusion\]). 

Design Criteria for the CSSC {#sec:design_criteria}
============================

We organized the CSSC 2013 and 2014 in coordination with the international SAT competition and presented them in the competition slots at the 2013 and 2014 SAT conferences (as well as in the 2014 FLoC Olympic Games, in which all SAT-related competitions took part).  We coordinated solver submission deadlines with the SAT competition to minimize overhead for participants, who could submit their solver to the SAT competition using default parameters and then open up their parameter spaces for the CSSC. 

We designed the CSSC to remain close to the international SAT competition’s established format; in particular, we used the same general categories: *industrial*, *crafted*, and *random*, and, in 2014 also *random satisfiable*.  Furthermore, we used the same input and output formats, the SAT competition’s mature code for verifying correctness of solver outputs (only for checking models of satisfiable instances; we did not have a certified UNSAT track), and the same scoring function (number of instances solved, breaking ties by average runtime). 

The main way our setup differed from that of the SAT competition was that we used a relatively small budget of five minutes per solver run.  We based this choice partly on the fact that many solvers have runtime distributions with rather long tails (or even heavy tails [@gomes-jar00a]), and that practitioners often use *many instances* and relatively *short runtimes* to benchmark solvers for a new application domain.  There is also evidence that SAT competition results would remain quite similar if based on shorter runtimes, but not if based on fewer instances [@HutHooLey10].  Therefore, in order to achieve more robust performance within a fixed computational budget, we chose to use many test instances (at least 250 for each benchmark) but relatively low runtime cutoffs per solver run (five minutes). ( We also note that a short time limit of five minutes has already been used in the agile track of the 2014 International Planning Competition.)  Due to constraints imposed by our computational infrastructure, we used a memory limit of 3GB for each solver run. 

To simulate the situation faced by practitioners with limited computational resources, we limited the computational budget for configuring a solver on a benchmark with a given configuration procedure to two days on 4 or 5 cores (in 2014 and 2013, respectively).  Our results are therefore indicative of what could be obtained by performing configuration runs over the weekend on a modern desktop machine. 

Controlled Execution of Solver Runs {#sec:controlled_execution}
-----------------------------------

Since all configuration procedures ran in an entirely automated fashion, they had to be robust against any kind of solver failure (segmentation faults, unsupported combinations of parameters, wrong results, infinite loops, etc.).  We handled all such conditions in a generic wrapper script that used Olivier Roussel’s runsolver tool [@olivier-jsat11a] to limit runtime and memory, and counted any errors or limit violations as timeouts at the maximum runtime of 300 seconds.  We also kept track of the rich solver runtime data we gathered in our configuration runs and made it publicly available on the competition website. 

Choice of Configuration Pipeline
--------------------------------

To avoid bias arising from our choice of algorithm configuration method, we independently used all three state-of-the-art methods applicable for runtime optimization ( [@hutter-jair09a],  [@ansotegui-cp09a], and  [@hutter-lion11a], as described in detail in Section \[sec:algoconf\]).  We evaluated the configurations resulting from all configuration runs on the entire training data set and selected the configuration with the best training performance.  We then executed only this configuration on the test set to determine the performance of the configured solver.  Except where specifically noted otherwise, all performance data we report in this article is for this optimized configuration on previously unseen test instances from the respective benchmark set. 

Pre-submission Bug Fixing
-------------------------

As part of the submission package, we provided solver authors with our configuration pipeline, so that they could run it themselves to identify bugs in their solver before submission (e.g., problems due to the choice of non-default parameters).  We also provided some trivial benchmark sets for this pre-submission preparation, which were not part of the competition. 

We did not offer a bug fixing phase after solver submission, except that we ran a very simple configuration experiment (10 minutes on trivial instances) to verify that the setup of all participants was correct. 

Choice of Benchmarks
--------------------

We chose the benchmark families for the CSSC to be relatively homogeneous in terms of the origin and/or construction process of instances in the same family.  Typically, we selected benchmark families that are neither too easy (since speedups are less interesting for easy instances), nor too hard (so that solvers could solve a large fraction of instances within the available computational budgets).  We aimed for benchmark sets of which at least 20-40% could be solved within the maximum runtime on a recent machine by the default configuration of a SAT solver that would perform reasonably well in the SAT competition.  We also aimed for benchmark sets with a sufficient number of instances to safeguard against over-tuning; in practice, the smallest datasets we used had 500 instances: 250 for training and 250 for testing. [ We did not disclose which benchmark sets we used until the competition results were announced.  While we encouraged competition entrants to also contribute benchmarks, we made sure to not substantially favor any solver by using such contributed benchmarks.]{} 

Automated Algorithm Configuration Procedures {#sec:algoconf}
============================================

The problem of finding performance-optimizing algorithm parameter settings arises for many computational problems.  In recent years, the AI community has developed several dedicated systems for this general *algorithm configuration* problem [@hutter-jair09a; @ansotegui-cp09a; @lopez-ibanez-tech11a; @hutter-lion11a]. 

We now describe this problem more formally.  Let $A$ be an algorithm having $n$ parameters with domains $\Theta_1, \dots, \Theta_n$. Parameters can be *real-valued* (with domains $[a,b]$, where $a,b \in \mathds{R}$ and $a < b$), *integer-valued* (with domains $[i,j]$, where $i,j \in \mathds{Z}$ and $i < j$), or *categorical* (with finite unordered domains, such as {red, blue, green}).  Parameters can also be *conditional* on an instantiation of other (so-called *parent*) parameters; as an example, consider the parameters of a heuristic mechanism $h$, which are completely ignored unless $h$ is chosen to be used by means of another, categorical parameter.  Finally, some combinations of parameter instantiations can be labelled as *forbidden*. 

Algorithm $A$’s *configuration space* ${{\bm{\Theta}}}$ then consists of all possible combinations of parameter values: ${{\bm{\Theta}}}= \Theta_1 \times \cdots \times \Theta_n$. We refer to elements ${{\bm{\theta}}}= \langle{}\theta_1, \dots, \theta_n\rangle{}$ of this configuration space as *parameter configurations*, or simply *configurations*.  Given a benchmark set $\Pi$ and a performance metric $m({{\bm{\theta}}},\pi)$ capturing the performance of configuration ${{\bm{\theta}}}\in{{\bm{\Theta}}}$ on problem instance $\pi\in\Pi$, the algorithm configuration problem then aims to find a configuration ${{\bm{\theta}}}\in{{\bm{\Theta}}}$ that minimizes $m$ over $\Pi$, [*i.e.*]{}, that minimizes[^2] $$\label{eqn:f}f({{\bm{\theta}}}) = \frac{1}{|\Pi|} \cdot \sum_{\pi\in\Pi} m({{\bm{\theta}}},\pi).$$

In the CSSC, the specific metric $m$ we optimized was *penalized average runtime (PAR-10)*, which counts runs that exceed a maximal cutoff time $\kappa_{max}$ without solving the given instance as $10 \cdot \kappa_{max}$. We terminated individual solver runs as unsuccessful after $\kappa_{max} = 300$ seconds. 

We refer to an instance of the algorithm configuration problem as a *configuration scenario* and to a method for solving the algorithm configuration problem as a *configuration procedure* (or a *configurator*), in order to avoid confusion with the solver to be optimized (which we refer to as the *target algorithm*) and the problem instances the solver is being optimized for. 

Algorithm configuration has been demonstrated to be very effective for optimizing various SAT solvers in the literature.  For example, @hutter-fmcad07a configured the algorithm Spear [@BabHut07] on formal verification instances, achieving a 500-fold speedup on software verification instances generated with the static checker Calysto [@babic-cav07] and a 4.5-fold speedup on IBM bounded model checking instances by @zarpas-sat05a.  Algorithm configuration has also enabled the development of general frameworks for stochastic local search SAT solvers that can be automatically instantiated to yield state-of-the-art performance on new types of instances; examples for such frameworks are SATenstein [@khudabukhsh-ijcai09a] and Captain Jack [@tompkins-sat11]. 

While all of these applications used the local-search based algorithm configuration method  [@hutter-jair09a], in the CSSC we wanted to avoid bias that could arise from commitment to one particular algorithm configuration method and thus used all three existing general algorithm configuration methods for runtime optimization: ,  [@ansotegui-cp09a], and  [@hutter-lion11a].[^3] We refer the interested reader to \[app:conf-proc-details\] for details on each of these configurators.  Here, we only mention some details that were important for the setup of the CSSC:

-   does not natively support parameters specified only as real- or integer-valued intervals, but requires all parameter values to be listed explicitly; for simplicity, we refer to the transformation used to satisfy this requirement as *discretization*.  When multiple parameter spaces were available for a solver, we only ran on the discretized version, whereas we ran and on both the discretized and the non-discretized versions. 

-   and have been shown to benefit substantially from multiple independent runs, [since they are randomized algorithms]{}.  Given $k$ cores, the usual approach is simply to execute $k$ independent configurator runs and pick the configuration from the one with best performance on the training set. ,  on the other hand, can use multiple cores on a single machine, and in fact requires these to run effectively.  Therefore, given $k$ available cores per configuration approach, we used $k$ independent runs of each and , and one run using all $k$ cores for . 

-   could not handle the complex parameter conditionalities found in some solvers; for those solvers, we only ran and . 

The Configurable SAT Solver Challenge 2013 {#sec:cssc2013}
==========================================

The first CSSC[^4] was held in 2013.  It featured three tracks mirroring those of the SAT competition: , , and .  Table \[tab:benchmarks-2013\] lists the benchmark families we used in each of these tracks, all of which are described in detail in \[app:benchmarks\].  Within each track, we used the same number of test instances for each benchmark family, thereby weighting each equally in our analysis. 

Participating Solvers and Their Parameters {#sec:cssc2013-solvers}
------------------------------------------

Table \[tab:solvers2013\] summarizes the solvers that participated in the CSSC 2013, along with information on their configuration spaces.  The eleven submitted solvers ranged from complete solvers based on conflict-directed clause learning (CDCL; [@cdcl]) to stochastic local search (SLS; [@SLS]) solvers.  The degree of parameterization varied substantially across these submitted solvers, from 2 to 241 parameters.  We briefly discuss the main features of the solvers’ parameter configuration spaces, ordering solvers by their number of parameters. 

[ \
**and** ]{} [@gnovelty] are closely related SLS solvers.  Both have two numerical parameters: the probability of selecting false clauses randomly and the probability of smoothing clause weights.  The parameters were pre-discretized by the solver developer to 11 and 10 values, yielding 110 possible combinations. 

[ \
**]{} [@gnovelty] is an SLS solver with five parameters: one binary parameter (determining whether the stagnation path is dynamic or static) and four numerical parameters: the length of the stagnation path, the size of the time window storing stagnation paths, the probability of smoothing stagnation weights, and the probability of smoothing clause weights.  All numerical parameters were pre-discretized to ten values each by the solver developer, yielding 20000 possible combinations. 

[ \
**]{} [@han2012simpsat] is a CDCL solver based on  [@cryptominisat], which adds additional strategies for explicitly handling XOR constraints [@han2012boolean].  It has five numerical parameters that govern both these XOR constraint strategies and the frequency of random decisions.  All parameters were pre-discretized by the solver developer, yielding 2400 possible combinations. 

[ \
**]{} [@leberre-sat4j] is full-featured library of solvers for Boolean satisfiability and optimization problems.  For the contest, it applied its default CDCL SAT solver with ten exposed parameters: four categorical parameters deciding between different restart strategies, phase selection strategies, simplifications, and cleaning; and six numerical parameters pre-discretized by its developer. [  \
**]{} [@solver43] is a CDCL solver with 12 parameters: three categorical parameters concerning sorting heuristics used in bounded variable eliminiation, in definitions and in adding blocked clauses; and nine numerical parameters concerning various frequencies, factors, and limits.  All parameters were pre-discretized by the solver developer. 

[ \
**]{} [@forlnodrup] is a CDCL solver with 44 parameters.  Most notably, these control variable selection, Boolean propagation, restarts, and learned clause removal.  About a third of the parameters are numerical (particularly most of those concerning restarts and learned clause removal); all parameters were pre-discretized by the solver developer. 

[ \
**]{} [@clasp] is a solver for the more general answer set programming (ASP) problem, but it can also solve SAT, MAXSAT and PB problems.  As a SAT solver, is a CDCL solver with $83$ parameters: $7$ for pre-processing, $14$ for the variable selection heuristic, $18$ for the restart policy, $34$ for the deletion policy, and 10 for a variety of other uses.  The configuration space is highly conditional, with several top-level parameters enabling or disabling certain strategies.  exposes both a mixed continuous/discrete parameter configuration space and a manually-discretized one. 

[ \
**]{} [@riss3g] is a CDCL solver with 125 parameters.  These include 6 numerical parameters from MiniSAT [@minisat], 10 numerical parameters from Glucose [@glucose], 17 mostly numerical Riss3G parameters, and 92 parameters controlling preprocessing/inprocessing performed by the integrated Coprocessor [@manthey2012coprocessor].  The inprocessor parameters resemble those in  [@biere-tech13a], emphasizing blocked clause elimination [@BCE], bounded variable addition [@Mbva], and probing [@probing].  About 50 of the parameters are Boolean, and most others are numerical parameters pre-discretized by the solver developer.  The parameter space is highly conditional, with inprocessor parameters dependent on a switch turning them on alongside various other dependencies.  Indeed, there are only 18 unconditional parameters.  Finally, there are also seven forbidden parameter combinations that ascertain various switches are turned on if inprocessing is used. [  \
**]{} [@riss3g] is an experimental extension of .  It exposes all of the parameters previously discussed for , along with an additional 11 Riss3G parameters and 57 inprocessing parameters.  Its developer implemented all of these extensions in one week and did not have time for extensive testing before the CSSC; therefore, he submitted as closed source, making it ineligible for medals.  We discuss the results of this closed-source solver separately, in \[sec:riss3ext-discussion\]. 

[ \
**]{}[@biere-tech13a] is a CDCL solver with 241 parameters (making it the solver with the largest configuration space in the CSSC 2013).  102 of these parameters are categorical, and the remaining 139 are integer-valued (76 of them with the trivial upper bound of max-integer, $2^{31}-1$).  parameterizes many details of the solution process, including probing and look-ahead (about 25 mostly numerical parameters), blocked clause elimination and bounded variable elimination (about 20 mostly categorical parameters each), glue clauses (about 15 mostly numerical parameters), and a host of other mechanisms parameterized by about 5–10 parameters each.  exposes its full parameter space, a discretized version of all parameters, and a subspace of only the categorical parameters (102 of them). 

Configuration Pipeline {#sec:cssc2013-pipeline}
----------------------

We executed this competition on the QDR partition of the Compute Canada Westgrid cluster Orcinus.  Each node in this cluster was provisioned with 24 GB memory and two 6-core, 2.66 GHz Intel Xeon X5650 CPUs with 12 MB L2 cache each, and ran Red Hat Enterprise Linux Server 5.5 (kernel 2.6.18, glibc 2.5). 

In this first edition of the CSSC, we were unfortunately unable to run .  This was because it requires multiple cores for effective runtime minimization, and the respective multiple-core jobs we submitted on the Orcinus cluster were stuck in the queue for months without getting started. ( Single-core runs, on the other hand, were often scheduled within minutes.) 

[We thus limited ourselves to using for the discretized parameter space of each of the 11 solvers and for each of the parameter spaces that solver authors submitted (as discussed above, 9 submissions with one parameter space, 1 submission with two, and 1 submission with three, i.e., 14 in total).  For each of the nine benchmark families, this gave rise to 11 configuration scenarios for and 14 for , for a total of 225 configuration scenarios.  Since our budget for each configuration procedure was two CPU days on five cores (five independent runs of and , respectively), the competition’s configuration phase required a total of 2250 CPU days (just over 6 CPU years).  Thanks to a special allocation on the Orcinus cluster, we were able to complete this phase within a week. ]{} 

Following standard practice, we then evaluated the configurations resulting from all configuration runs on the entire training data set and selected the configuration with the best training performance.  We then executed only this configuration on the test set to assess the performance of the configured solver. [ This evaluation phase required much less time than the configuration phase.]{} 

[We note that all scripts we used for performing the configuration and analysis experiments were written in Ruby and are available for download on the competition website.]{} 

Results {#sec:cssc2013-results}
-------

  Rank             
  ---------- -- -- --
  1$^{st}$         
  2$^{nd}$         
  3$^{rd}$         

  : Winners of the three tracks of CSSC 2013.\[tab:results13\]

For each the three tracks of CSSC 2013, we configured each of the eleven submitted solvers for each of the benchmark families within the track and aggregated results across the respective test instances.  We show the winners in Table \[tab:results13\] and discuss the results for each track in the following sections.  Additional details, tables, and figures are provided in an accompanying technical report [@hutter-tech14a]. 

[We remind the reader that the CSSC score only depends on how well the configured solver did and *not* on the difference between default and configured performance.  We nevertheless still cover default performance prominently in the following results, in order to emphasize the impact configuration had and the difference between the CSSC and standard solver competitions (e.g., the SAT competition).]{} 

### Results of the Track {#sec:cssc2013-results-indu}

Our track consisted of the four industrial benchmarks detailed in \[sec:benchmarks-indu\]:  [@biere-misc07a],  [@brummayer-sat10a],  [@zarpas-sat05a], and  [@babic-hvc07].  Figure \[fig:indu13:lingeling\] visualizes the results of the configuration process for the winning solver on these four benchmark sets.  It demonstrates that even , a highly competitive solver in terms of default performance, can be configured for improved performance on a wide range of benchmarks.  We note that for the easy benchmark , configuration sped up by a factor of $20$ (average runtime 3.3s [*vs*]{} 0.16s), and that for the harder instances, it nearly halved the number of timeouts (39 [*vs*]{} 20).  The improvements were smaller for more traditional hardware verification instances ( and ) similar to those used to determine ’s default parameter settings. 

Table \[tab:indu13\] summarizes the results of the ten solvers that were eligible for medals.  From this table, we note that, like , many other solvers benefited from configuration.  Indeed, some solvers (in particular and ) benefited much more from configuration on the instances, largely because their default performance was worse on this benchmark.  On the other hand, featured stronger default performance than but did not benefit as much from configuration.  Table \[tab:indu13\] also aggregates results across the four benchmark families to yield the overall results for the track.  These results show that many solvers benefited substantially from configuration, and that some benefited more than others, causing the CSSC ranking to differ substantially from the ranking according to default solver performance; for instance, based on default performance, the overall winning solver, , would have only ranked fourth. 

### Results of the Track {#sec:cssc2013-results-crafted}

The track consisted of the two crafted benchmarks detailed in \[sec:benchmarks-crafted\]: and . 

Figure \[fig:clasp-crafted-2013\] visualizes the improvements algorithm configuration yielded for the best-performing solver on these benchmarks.  Improvements were particularly large on the instances, where algorithm configuration decreased the number of timeouts from 42 to 6.  Table \[tab:crafted2013\] summarizes the results we obtained for all solvers on these benchmarks, showing that configuration also substantially improved the performance of many other solvers.  The table also aggregates results across both benchmark families to yield overall results for the track.  While showed the best default performance and benefited substantially from configuration (\#timeouts reduced from 135 to 98), improved even more (\#timeouts reduced from 139 to 96). 

### Results of the Track {#sec:cssc2013-results-random}

The track consisted of three random benchmarks detailed in \[sec:benchmarks-random\]: , , and .  The instances in were all satisfiable, those in all unsatisfiable, and those in were mixed. 

Table \[tab:random2013\] summarizes the results for these benchmarks.  It shows that the benchmark set was very easy for complete solvers (although configuration still yielded up to 4-fold speedups), that the benchmark was also quite easy for the best solvers, and that only the SLS solvers could tackle benchmark , with configuration making a big difference to performance. 

Here again, our aggregate results demonstrate that rankings were substantially different between the default and configured versions of the solvers: the three solvers with top default performance were ranked 4th to 6th in the CSSC, and vice versa.  Figure \[fig:random-2013\] visualizes the very substantial speedups achieved by configuration for the winning solver on and , and for the SLS solver on . 

The Configurable SAT Solver Challenge 2014 {#sec:cssc2014}
==========================================

The second CSSC[^5] was held in 2014.  Compared to the inaugural CSSC in 2013, we improved the competition design in several ways:

-   We used a different computer cluster,[^6] enabling us to run as one of the configuration procedures. 

-   We added a track to facilitate comparisons of stochastic local search solvers. 

-   We dropped the (too easy) SWV benchmark family and introduced four new benchmark families, yielding a total of three benchmark families in each of the four tracks, summarized in Table \[tab:benchmarks-2014\] and described in detail in \[app:benchmarks\]. 

-   We let solver authors decide which tracks their solver should run in. 

-   For fairness, for each solver, we performed the same number of configuration experiments. ( This is in contrast to 2013, where we performed the same number of configuration runs *for every configuration space* of every solver, which lead to a larger combined configuration budget for solvers submitted with multiple configuration spaces). 

-   We kept track of all of the (millions of) solver runs performed during the configuration process and made all information about errors available to solver developers [after the competition.]{} 

Participating Solvers {#sec:cssc2014-solvers}
---------------------

The ten solvers that participated in the CSSC 2014 are summarized in Table \[tab:solvers2014\]; they included CDCL, SLS and hybrid solvers.  These solvers differed substantially in their degree of parameterization, with the number of parameters ranging from 1 to 323.  We briefly discuss the main features of each solver’s parameter configuration space, ordering solvers by their number of parameters. 

[ \
**]{} [@dccsat] combines the SLS solver DCCASat with the CDCL solver march-rw.  It was submitted to the track.  Its only (continuous) parameter is the time ratio of the SLS solver.  This parameter was pre-discretized to nine values. 

[ \
**]{} [@csccat1; @dccsat] is an SLS solver based on configuration checking and dynamic local search methods.  It was submitted to the track.  It features 3 continuous parameters that were pre-discretized to 7, 9, and 9 values each, giving rise to a total configuration space of 567 possible parameter configurations.  The parameters control the weighting of the dynamic local search part and the probabilities for the linear make functions used in the random walk steps. 

[ \
**]{} [@probSAT] is a simple SLS solver based on probability distributions that are built from simple features, such as the make and break of variables [@probSAT].  ’s 9 parameters control the type and the parameters of the probability distribution, as well as the type of restart.  was submitted to the track. [  \
**]{} [@minisat_hack] is a CDCL solver; it was submitted to all tracks.  It has one categorical parameter (whether or not to use the Luby restarting strategy) and 9 numerical parameters fine-tuning the Luby and geometric restart strategies, as well as controlling clause removal and the treatment of glue clauses.  3 of these 9 numerical parameters are conditional on the choice of the Luby restart strategy, and all numerical parameters were pre-discretized by the solver developer.  There are also 3 forbidden parameter combinations derived from a weak inequality constraint between two parameter values. 

[ \
**]{} [@lingelingyalsat] is an SLS solver; it was submitted to the tracks and .  It has 27 parameters that parameterize the solver’s restart component (7 parameters) amongst many other components.  11 of the 27 parameters are numerical, with 6 of them having a trivial upper bound of max-integer ($2^{31}-1$). 

[ \
**]{} [@cryptominisat] is a CDCL solver; it was submitted to the tracks and .  It has 29 parameters that control restarts (6 mostly numerical parameters), clause removal (7 mostly numerical parameters), variable branching and polarity (3 parameters each), simplification (5 parameters), and several other mechanisms.  2 of the numerical parameters further parameterize the blocking restart mechanism and are thus conditional on that mechanism being selected. 

[ \
**]{} [@clasp] is a solver for the more general answer set programming (ASP) problem, but it can also solve SAT, MAXSAT and PB problems.  It is fundamentally similar to the solver submitted in 2013; changes in the new version focused on the ASP solving part rather than the SAT solving part.  As a SAT solver, has $75$ parameters, of which $7$ control preprocessing, $14$ variable selection, $19$ the restart policy, $28$ the deletion policy and $7$ miscellaneous other mechanisms.  The configuration space is highly conditional, with several top-level parameters enabling or disabling certain strategies.  Finally, there are also $2$ forbidden parameter combinations that prevent certain combinations of deletion strategies.  exposes both a mixed continuous/discrete parameter configuration space and a manually-discretized one.  It was submitted to all tracks. 

[ \
**]{} [@riss] is a CDCL solver submitted to all tracks except .  Compared to the 2013 version , it almost doubled its number of parameters, yielding 214 parameters organized into 121 simplification and 93 search parameters.  In particular, it added many new preprocessing and inprocessing techniques, including XOR handling (via Gaussian elimination [@han2012boolean]), and extracting cardinality constraints [@MlazyCard].  Roughly half of the simplification parameters and a third of the search parameters are categorical (in both cases most of the categoricals are binary).  The simplification parameters comprise about 20 Boolean switches for preprocessing techniques and about 100 in-processor parameters, prominently including blocked clause elimination, bounded variable addition, equivalance elimination [@equivalence-reasoning], numerical limits, probing, symmetry breaking, unhiding [@unhiding], Gaussian elimination, covered literal elimination [@covered-literal-elimination], and even some stochastic local search.  The search parameters parameterize a wide range of mechanisms including variable selection, clause learning and removal, restarts, clause minimization, restricted extended resolution, and interleaved clause strengthening. 

[ \
**]{} [@sparrowtoriss] combines the SLS solver *Sparrow* with the CDCL solver by first running *Sparrow*, followed by .  It was submitted to all tracks.  ’s configuration space is that of plus 6 *Sparrow* parameters and 2 parameters controlling when to switch from *Sparrow* to : the maximal number of flips for *Sparrow* (by default 500 million) and the CPU time for *Sparrow* (by default 150 seconds).  Also, in contrast to , does not pre-discretize its numerical parameters, but expresses them as 36 integer and 16 continuous parameters. 

[ \
**]{} [@lingelingyalsat] is a successor to the 2013 version; it was submitted to the tracks and .  Compared to 2013, ’s parameter space grew by roughly a third, to a total of 323 parameters (meaning that again, was the solver with the most parameters).  As in 2013, roughly 40% of these parameters were categorical and the rest integer-valued (many with a trivial upper bound of max-integer, $2^{31}-1$).  Notable groups of parameters that were introduced in the 2014 version include additional preprocessing/inprocessing options and new restart strategies. 

Configuration Pipeline {#sec:cssc2014-pipeline}
----------------------

In the CSSC 2014, we used the configurators , , and .  For each benchmark and solver, we ran and on the solver’s full configuration space, which could contain an arbitrary combination of numerical and categorical parameters.  We also ran all configurators on a discretized version of the configuration space (automatically constructed unless provided by the solver authors), yielding a total of five configuration approaches: -discretized, , -discretized, , and -discretized.  could not handle the complex conditionals of some solvers; therefore, for these solvers we only ran and the two variants. 

Due to the cost of running a third configurator on nearly every configuration scenario, we reduced the budget for each configuration approach from two CPU days on five cores in CSCC 2013 to two CPU days on four cores in CSSC 2014.  In the case of and , as in 2013, we used these four cores to perform four independent 2-day configurator runs.  In the case of , we performed one 2-day run using all four cores.  We evaluated the configurations resulting from each of the 14 configuration runs (4 -discretized, 4 -discretized, 4 , 1 -discretized, and 1 ) on the entire training data set of the benchmark at hand and selected the configuration with the best performance.  We then executed only this configuration on the benchmark’s test set to determine the performance of the configured solver. 

[In the four tracks of the CSSC (, , , ) we had 6, 6, 5, and 6 participating solvers, respectively, and since there were three benchmark families per track, we ended up with $(6+6+5+6)\times 3 = 72$ pairs of solvers and benchmarks to configure them on.  For each of these configuration scenarios, each of the 5 configuration approaches above required four cores for 2 days, yielding a total computational expense of $72 \times 5\times 4 \times 2 = 2880$ CPU days (close to 8 CPU years).  Thanks to a special allocation on the META cluster at the University of Freiburg, we were able to finish this process within 2 weeks.]{} 

[We note that all scripts we used for performing the configuration and analysis experiments were written in Python (updated from Ruby in 2013) and are available for download on the competition website.]{} 

Results {#sec:cssc2014-results}
-------

  Rank                
  ---------- -- -- -- --
  1$^{st}$            
  2$^{nd}$            
  3$^{rd}$            

  : Winners of the four tracks of CSSC 2014.\[tab:results14\]

For each of the four tracks of CSSC 2014, we configured the solvers submitted to the track on each of the three benchmark families from that track and aggregated results across the respective test instances.  We show the winners for each track in Table \[tab:results14\] and discuss the results in the following sections.  Additional details, tables, and figures are provided in an accompanying technical report [@hutter-tech14b]. 

### Results of the Track {#sec:cssc2014-results-indu}

The track consisted of three industrial benchmarks detailed in \[sec:benchmarks-indu\]:  [@biere-misc07a],  [@brummayer-sat10a], and  [@zarpas-sat05a].  Figure \[fig:cssc14-lingeling\] visualizes the results of applying algorithm configuration to the winning solver on these three benchmark sets.  It shows similar results as in the track of CSSC 2013: ’s strong default performance on ‘typical’ hardware verification benchmarks (IBM and BMC) could only be improved slightly by configuration, but much larger improvements were possible on less standard benchmarks, such as . 

Table \[tab:indu2014\] summarizes the results for all six solvers that participated in the track.  These results demonstrate that, in contrast to , several solvers (in particular, , , and ) benefited largely from configuration on the BMC benchmark, but did not reach ’s performance even after configuration.  performed even better than with its default parameters, but did not benefit from configuration as much as (particularly on the benchmark family). 

### Results of the Track {#sec:cssc2014-results-crafted}

The track consisted of the three crafted benchmarks detailed in \[sec:benchmarks-crafted\]: , , and .  Figure \[fig:cssc14-clasp-crafted\] visualizes the improvements configuration yielded on these benchmarks for the best-performing solver, .  The effect of configuration was particularly large on the instances, where it reduced the number of timeouts from 81 to 0.  Similar to the results from CSSC 2013, configuration also substantially improved performance on the instances, decreasing the number of timeouts from 43 to 9.  In contrast to 2013, an unusual effect occurred for on the instances, where the number of timeouts on the test set *increased* from 87 to 93 by configuration; we study the reasons for this in more detail in Section \[sec:why-does-it-work\]. 

Table \[tab:crafted2014\] summarizes the results of all solvers on the track, showing that the performance of many other solvers also substantially improved on the benchmarks and , and only mildly (if at all) on the benchmark.  The aggregate results across these 3 benchmark families show that had the best default performance, but only benefited mildly from configuration (\#timeouts reduced from 115 to 109), whereas benefited much more from configuration and thus outperformed after configuration (\#timeouts reduced from 211 to 102).  Once again, we note that the winning solver only showed mediocre performance based on its default: would have ranked 5th in a comparison based on default performance. 

### Results of the Track {#sec:cssc2014-results-random}

The track consisted of three random benchmarks detailed in \[sec:benchmarks-random\]: , , and .  The instances in are all unsatisfiable, while the other two sets contain both satisfiable and unsatisfiable instances.  Figure \[fig:clasp-random-2014\] visualizes the improvements achieved by configuration on these benchmarks for the best-performing solver .  benefited most from configuration on benchmark , where it reduced the number of timeouts from 18 to 0.  For the other benchmarks, it could already solve all instances in its default parameter configuration, but configuration helped reduce its average runtime by factors of 3 () and 2 (), respectively.  Table \[tab:random2014\] summarizes the results of all solvers for these benchmarks.  We note that solver showed the best default performance, and that after configuration, it also solved all instances from the three benchmark sets, only ranking behind because the latter solved these instances faster. 

### Results of the Track {#sec:cssc2014-results-randomsat}

The track consisted of the three benchmarks detailed in \[sec:benchmarks-random\]: *3sat1k*, *5sat500* and *7sat90*.  Figure \[fig:probsat-randomsat-2014\] visualizes the improvements configuration achieved on these benchmarks for the best-performing solver .  benefited most from configuration on benchmark : its default did not solve a single instance in the maximum runtime of 300 seconds, while its configured version solved all instances in an average runtime below 2 seconds!  Since timeouts at 300s yield a PAR-10 score of 3000, the PAR-10 speedup factor on this benchmark was $1\,500$, the largest we observed in the CSSC.  On the other two scenarios, configuration was also very beneficial, reducing ’s number of timeouts from 24 to 0 (7sat90) and from 10 to 4 (3sat1k), respectively.  Table \[tab:randomsat2014\] summarizes the results of all solvers for these benchmarks, showing that next to , only benefited from configuration.  Neither of the CDCL solvers ( and ) solved a single instance in any of the three benchmarks (in either default or configured variants).  For the other two SLS solvers, and , the defaults were already well tuned for these benchmark sets.  Indeed, we observed overtuning to the training sets in one case each: for and for .  Overall, the configurability of and allowed them to place first and second, respectively, despite their poor default performance (especially on , where neither of them solved a single instance with default settings). 

Post-Competition Analyses {#sec:discussion-of-results}
=========================

While the previous sections focussed on the results of the respective competitions, we now discuss several analyses we performed afterwards to study overarching phenomena and general patterns. 

Why Does Configuration Work So Well and How Can It Fail? {# sec:why-does-it-work}
--------------------------------------------------------

Several practitioners have asked us why automated configuration can yield the large speedups over the default configuration we observed.  We believe there are two key reasons for this:

-   No single algorithmic approach performs best on all types of benchmark instances; this is precisely the same reason that algorithm selection approaches (such as SATzilla [@xu-jair08a] or 3S [@kadioglu-cp11a]) work so well. 

-   Solver defaults are typically chosen to be robust across benchmark families.  For any given benchmark family $F$, highly parameterized solvers can, however, typically be instantiated to exploit the idiosyncrasies of $F$ substantially better. ( These improvements only need to generalize to other instances from $F$, not to other benchmark families.) 

However, algorithm configuration does not necessarily work in all cases.  For example, in the track of the CSSC 2014, we encountered a case in which the configured solver performed somewhat *worse* than the default solver: configured on benchmark family timed out on 93 test instances, whereas its default only timed out on 87 test instances (see also Figure \[fig:cssc14-clasp-labs\]).  Two obvious causes suggest themselves in the case of such a failure:

-   insufficiently long configuration runs (which can result in worse-than-default performance on the *training* set[^7]); and/or

-   overtuning on the training set that does not generalize to the *test* set. 

We investigated the configuration of on further after the competition, and found that in this case *both* of these effects applied: In the CSSC, training performance slightly deteriorated ($86\rightarrow{} 87$ timeouts); and the improved training performance we found with a larger configuration budget[^8] afterwards ($86\rightarrow{} 83$ timeouts) also did not generalize to the test set ($87\rightarrow{} 88$ timeouts). 

 

To contrast the conditions under which configuration can fail and under which it works well, we compared the configuration of on benchmarks ($87\rightarrow 93$ test timeouts in the CSSC) and ($81\rightarrow 0$ test timeouts in the CSSC).  For this analysis, we sampled 100 configurations uniformly at random and evaluated their PAR-10 training and test scores on both of the benchmarks; Figure \[fig:score\_correlation\] shows the result.  The first observation we make directly based on the figure is that for , about 20default, whereas for none of them do: the default is simply very good to start with for and thus much harder to beat.  Second, since several configurations are very good (i.e., fast) for , configurators can make progress much faster (and also take full advantage of adaptive capping to limit the time spent with poor configurations); indeed, in the CSSC the configurators managed to perform about $8$ times more runs in the same time (2 days) for than for (averaging about $14\,400$ vs. $1\,800$ runs).  This explains why configurators require more time to improve training performance on .  Third, to assess the potential for overtuning, we studied how training and test performance correlate.  Visually, Figure \[fig:score\_correlation\] shows a strong overall correlation of PAR-10 training and test scores for both of the benchmarks; Spearman correlation coefficients are indeed high: 0.99 () and 0.98 ().  However, for the top 20explains why improvements on the training set do not necessarily translate to improvements on its test set. 

Overall Configurability of Solvers {#sec:configurability-discussion}
----------------------------------

 

Some solvers consistently benefited more from configuration than others.  Here, we quantify the *configurability* of a solver on a given benchmark by the PAR-10 speedup factor its configured version achieved over its default version, computed on the set of instances solved by at least one of the two.  We then examine the relationship between configurability and number of parameters to determine whether solvers with many parameters consistently benefited more or less from configuration than solvers with few parameters.[^9]

Figure \[fig:configurability-vs-parameters\] shows that configurability was indeed high for solvers with many parameters (e.g., the variants of , *Riss*, and ), but that it did not increase monotonically in the number of parameters: some solvers with very few parameters were surprisingly configurable.  For example, configuration sped up the single-parameter solver by at least a factor of four in all three benchmarks it was configured for, while the 4-parameter solver was not improved at all by configuration.  Furthermore, , which achieved the best single-benchmark performance improvement (as previously discussed in Section \[sec:cssc2014-results-randomsat\]), has only 9 parameters. 

We note that the notion of configurability used here is strongly dependent on the time budget available for configuration.  In the next section, we investigate this issue in more detail. 

Impact of Configuration Budget {#sec:impact-configuration-budget}
------------------------------

The runtime budget we allow to configure each solver has an obvious impact on the results.  In one extreme case, if we let this budget go towards zero, the configuration pipeline returns the solver defaults (and we are back in the setting of the standard SAT competition).  For small, non-zero budgets, we can expect solvers with few parameters to benefit from configuration more, since their configuration spaces are easier to search.  On the other hand, if we increase the time budget, solvers with larger parameter spaces are likely to benefit more than those with smaller parameter spaces (since larger parts of their configuration space can be searched given additional time). 

Figure \[fig:perf-over-time-different-spaces\] illustrates this phenomenon for the two top solvers in the track of CSSC 2014.  With the competition’s configuration budget of two days across 4 cores, performed better than (both solved all test instances, with average runtimes of 13 vs. 21 seconds).  In the extreme case of no time budget for configuration, would have won against , since its default version performed much better (2 vs. 18 timeouts), and, in fact, Figure \[fig:perf-over-time-different-spaces-threecnf\] shows that it required a configuration budget of at least $10^4$ seconds to find improving parameters for the benchmark (where the default version of produced 18 timeouts).  While the configuration of ’s single parameter had long converged by $10^4$ seconds, the configuration of ’s 75 parameters continued to improve performance until the end of the configuration budget, and, in particular for the benchmark, performance would have likely continued to improve further if the budget had been larger. 

We thus conclude that the solver’s flexibility should be chosen in relation to the available budget for configuration: solvers with few parameters can often be improved more quickly than highly flexible solving frameworks, but, given enough computational resources and powerful configurators, the latter ones can typically offer a greater performance potential. 

Results with an Increased Cutoff Time for Validation {#sec:impact-validation-time}
----------------------------------------------------

Next to the overall time budget allowed for configuration, another important time limit is the cutoff time allowed for each single solver run; due to our limited overall budget, we chose this to be quite low: 300 seconds both for solver runs during the configuration process and for the final evaluation of solvers on previously unseen test instances. 

Here, we study how using a larger cutoff time at evaluation time affects results, mimicking a situation where we care about performance with a large cutoff time but use a smaller cutoff time for the configuration process to make progress faster.  In fact, several studies in the literature (e.g., [@hutter-fmcad07a; @khudabukhsh-ijcai09a; @tompkins-sat11a]) used a smaller cutoff time for configuration than for testing, and we found that improvements with a time budget around 300 seconds often lead to improvements with larger cutoff times. 

Table \[tab:indu2014-5000s\] shows the results we obtained when using a cutoff time of 5000 seconds for validation (the same as the SAT competition) for the track of CSSC 2014.  Qualitatively, these results are quite similar to those obtained with an evaluation cutoff time of 300s (compare Table \[tab:indu2014\]), with only few differences.  As expected, given the larger cutoff time, all solvers solved substantially more instances (especially for the and benchmarks).  Nevertheless, with a cutoff time of 5000 seconds, for all solvers, the configured variant (configured to perform well with a cutoff time of 300 seconds) still performed better than the default version, making us more confident that configuration does not substantially overtune to achieve good performance on easy instances only. 

  -- ---------------------- -------------------- ---------------------- ----------------------- ----- ---
                                                                                                      
                                                                               *Overall*         def  
          $10 \to 10$        $6 \to \mathbf{3}$   $66 \to \mathbf{65}$   $82 \to \mathbf{78}$     1    1
      $\mathbf{11} \to 12$   $6 \to \mathbf{4}$       $67 \to 67$        $84 \to \mathbf{83}$     2    2
      $19 \to \mathbf{12}$       $3 \to 3$        $70 \to \mathbf{68}$   $92 \to \mathbf{83}$     3    3
      $19 \to \mathbf{14}$       $3 \to 3$        $70 \to \mathbf{69}$   $92 \to \mathbf{86}$     4    4
      $20 \to \mathbf{18}$   $9 \to \mathbf{4}$   $66 \to \mathbf{64}$   $95 \to \mathbf{86}$     5    5
      $31 \to \mathbf{18}$       $3 \to 3$        $70 \to \mathbf{69}$   $104 \to \mathbf{90}$    6    6
  -- ---------------------- -------------------- ---------------------- ----------------------- ----- ---

  : Results for CSSC 2014 competition track , when final solvers are evaluated with a per-run cutoff time of 5000 seconds instead of 300 seconds (as in Table \[tab:indu2014\]).  The ranking is the same for the default and configured algorithms, but this can be attributed to chance as there are two ties in terms of timeouts, which are only broken by average runtimes: (513.7s) [*vs*]{} (520.5s), and (548.5s) [*vs*]{} (555.0s).  \[tab:indu2014-5000s\]

Results with a Single Configurator {#sec:impact-configurator-discussion}
----------------------------------

  -- ------- ------- ------- -------- -------- ------- ------- ------- ------- --------
                                                                               
                                                                               
      $1.0$   $1.0$   $1.0$   $1.0$    $1.0$    $1.0$   $1.0$   $1.0$   $1.0$   $1.0$
      $1.0$   $1.0$   $1.0$   $3.0$    $1.6$    $1.0$   $1.0$   $1.0$   $1.6$   $1.0$
      $1.0$   $1.2$   $1.1$     –        –      $1.0$   $1.5$   $1.1$     –       –
      $1.2$   $1.1$   $1.2$   $1.5$    $2.0$    $0.9$   $1.0$   $1.0$   $1.0$   $1.8$
      $1.2$   $2.2$   $2.0$   $18.1$   $18.5$   $1.1$   $0.6$   $1.8$   $6.6$   $12.3$
      $1.1$   $1.2$   $1.4$   $3.4$    $3.9$    $1.0$   $1.3$   $1.4$   $3.5$   $4.1$
      $1.1$   $1.5$   $1.9$     –        –      $1.2$   $0.9$   $1.5$     –       –
      $1.1$   $1.1$   $1.4$   $10.5$   $10.1$   $1.2$   $0.9$   $1.1$   $6.0$   $7.4$
      $1.3$   $1.1$   $2.0$     –        –      $1.1$   $1.0$   $1.8$     –       –
      $1.5$   $1.6$   $1.4$     –      $77.2$   $1.4$   $1.0$   $1.3$     –     $30.5$
  -- ------- ------- ------- -------- -------- ------- ------- ------- ------- --------

  : Geometric mean of *PAR-10 slowdown factors over the CSSC result* (i.e., over using the oracle best of our five configuration approaches), computed across the CSSC 2014 scenarios for which the respective solver was submitted.  Note that on the training set $1.0$ is a lower bound for this metric, while on the test set values smaller than $1.0$ are possible if one configuration generalizes better than another.  Entry ‘–’ denotes that was incompatible with the configuration space (see \[app:gga\] for details).\[tab:geometric-slowdowns\]

While the CSSC addressed the performance of SAT solvers rather than the performance of configurators, we have been asked whether our complex configuration pipeline was necessary, or whether a single configurator would have produced similar or identical results.  Indeed, counting the choice of discretized [*vs*]{} non-discretized parameter space, our pipeline used five configuration approaches (-discretized, , -discretized, -discretized, and ).  Thus, if one of these approaches had yielded the same results all by itself, we could have reduced our overall configuration budget five-fold. 

To determine whether this was the case, we evaluated the solver performance we would have observed if we had used each configuration approach in isolation.  For each configuration scenario and each approach, we computed the *PAR-10 slowdown factor over the CSSC result* as the PAR-10 achieved with the respective approach, divided by the PAR-10 of the approach with best training performance (which we selected in the CSSC).  If a configuration approach achieves a PAR-10 slowdown factor close to one, this means that it gives rise to solver performance close to that achieved by our full CSSC configuration pipeline.  For each solver, we then computed the geometric mean of these factors across the scenarios it was configured for.  Table \[tab:geometric-slowdowns\] shows that both variants performed close to best for all solvers, meaning that we would have achieved similar results had we only used in the CSSC.  yielded the next best performance, followed by .  Full results can be found in the accompanying technical report [@hutter-tech14b].  Despite ’s strong performance, we believe it will still be useful to run several configuration approaches in future CSSCs, both to ensure robustness and to assess whether some configuration scenarios are better suited to other configuration approaches. 

Conclusion {#sec:conclusion}
==========

In this article, we have described the design of the Configurable SAT Solver Challenge (CSSC) and the details of CSSC 2013 and CSSC 2014.  We have highlighted two main insights that we gained from this competition:

1.   Automated algorithm configuration often improved performance substantially, in several cases yielding average speedups of orders of magnitude. 

2.   Some solvers benefited more from automated configuration than others, leading to substantially different algorithm rankings after configuration than before (as, [*e.g.*]{}, measured by the SAT competition). 

Also, the configuration budget influenced which algorithm would perform best, and with the competition budget of 2 days on 4–5 cores, algorithms with larger parameter spaces exhibited more capacity for improvement. 

These conclusions have interesting implications for algorithm design: if an algorithm is likely to be applied across a range of specialized applications, then it should be made flexible by parameterization of its key mechanisms and components, and this flexibility should be exploited by automated algorithm configuration.  Our findings thus challenge the traditional approach to solver design that tries to avoid having too many algorithm parameters (since these parameters complicate manual tuning and analysis).  Rather, they promote the design paradigm of *Programming by Optimization (PbO)* [@hoos-cacm12], which aims to avoid premature design choices and to rather actively develop promising alternatives for parts of the design that enable an automated customization to achieve peak performance on particular benchmarks of interest.  Indeed, in the CSSC, we have already observed a trend towards PbO, as evidenced by the introduction of a host of new parameters into state-of-the-art solvers, such as and , between 2013 and 2014. 

Finally, there is no reason why a configurable solver competition should be appropriate and insightful only for SAT.  On the contrary, similar events would be interesting in the context of many other challenging computational problems, such as answer set programming, constraint programming or AI planning.  Another interesting application domain is automatic machine learning, where algorithm configuration can adapt flexible machine learning frameworks to each new dataset at hand [@thornton-kdd13a; @feurer-nips2015a].  We believe that for those and many other problems, similar findings to those we reported here for CSSC would be obtained, leading to analogous conclusions regarding algorithm design. 

Acknowledgements {#sec:ack .unnumbered}
================

Many thanks go to Kevin Tierney for his generous help with running , including his addition of new features, his suggestion of parameter settings and his conversion script to read the pcs format.  We also thank the solver developers for proofreading the description of their solvers and their parameters.  For computational resources to run the competition, we thank Compute Canada (CSSC 2013) and the German Research Foundation (DFG; CSSC 2014).  F. Hutter and M. Lindauer thank the DFG for funding this research under Emmy Noether grant HU 1900/2-1.  H. Hoos acknowledges funding through an NSERC Discovery Grant. 

References {#references .unnumbered}
==========

Benchmark Sets Used {#app:benchmarks}
===================

We mirrored the three main categories of instances from the SAT competition: industrial, crafted, and random.  In 2014, we also included a category of satisfiable random instances from the SAT Races.  For each of these categories, we used various benchmark sets, each of them split into a training set to be used for algorithm configuration and a disjoint test set. 

For each category, to weight all benchmarks equally, we used the same number of test instances from each benchmark; these test sets were subsampled uniformly at random from the respective complete test sets. 

All benchmarks are summarized in Tables \[tab:benchmarks-2013\] and \[tab:benchmarks-2014\] in the main text. 

Industrial Benchmark Sets {#sec:benchmarks-indu}
-------------------------

#### 

This set of SAT-encoded software verification instances consists of 604 instances generated with the CALYSTO static checker [@babic-hvc07], used for the verification of five programs: the spam filter Dspam, the SAT solver HyperSAT, the Wine Windows OS emulator, the gzip archiver, and a component of xinetd (a secure version of inetd).  We used the same training/test split as [@hutter-fmcad07a [@hutter-fmcad07a]]{}, containing 302 training instances and 302 test instances.  We used this benchmark set in the 2013 CSSC. ( In 2014, we only used it for preliminary tests since it is quite easy for modern solvers.) 

#### 

This set of SAT-encoded bounded model checking instances consists of 765 instances generated by [@zarpas-sat05a [@zarpas-sat05a]]{} These instances were originally selected by [@hutter-fmcad07a [@hutter-fmcad07a]]{} as the instances in 40 randomly-selected folders from the IBM Formal Verification Benchmarks Library.  We used their original training/test split, containing 382 training instances and 383 test instances.  We used this benchmark set in both the 2013 and 2014 CSSCs. 

#### 

These instances were produced by a circuit-based CNF fuzzing tool,  [@brummayer-sat10a] (version 0.1).  As was originally designed to produce semi-realistic test cases for debugging SAT solvers, the majority of the instances it produces are trivial; however, occasionally, it produces more challenging instances.  The CircuitFuzz instances were found by generating 10,000 instances and removing all those that could be solved within one second by .  This instance generator was originally described in detail by [@bayless-lion14a [@bayless-lion14a]]{}; we used the 300 instances from that paper as the training set (except one quite easy instance, ‘fuzz\_100\_25433.cnf’, which was dropped unintentionally by a script) and produced 585 additional instances using the same method, to form a testing set.  We used this benchmark set in both the 2013 and 2014 CSSCs. [ We used these instances as part of the industrial track since they are “structured in ways that resemble (at least superficially) real-world, circuit-derived instances” [@bayless-lion14a]; a case could, however, also be made for them to be part of the crafted or random track.]{} 

#### 

This set of SAT instances was derived by unrolling the 2008 Hardware Model Checking Competition circuits [@biere-misc08a].  Each of these instances is a sequential circuit with safety properties.  Each circuit was unrolled to 50, 100, and 200 iterations using the tool *aigunroll* (version 1.9.4) from the AIGER tools [@biere-misc07a].  We omitted trivial instances that were proven SAT or UNSAT during the unrolling process.  While we used the entire set in 2013, in 2014 we removed the 60 instances provided by Intel in order to allow us to publicly share the instances. 

Crafted Benchmark Sets {#sec:benchmarks-crafted}
----------------------

#### 

These instances were first used in the 2013 SAT Competition [@mugrauer2013] and were generated by encoding the graph isomorphism problem to SAT according to the procedure described by [@toran2013 [@toran2013]]{}.  Given two graphs $G_1$ and $G_2$ with $n$ vertices and $m$ edges (for whom the isomorphism problem is to be solved) the generator creates a SAT formula with $n^2$ variables and $O(n)+O(n^3)+O(n^4)$ clauses.  Consequently, the generated instances can contain very many clauses.  The 2064 SAT instances in this set were generated from different types of graphs, [with the number of vertices $n$ ranging from 10 to 1296.[^10]]{} We split the instances uniformly at random into 1032 training and 1032 test instances; [in both the 2013 and 2014 CSSCs, we only used 351 of the test instances]{}. 

#### 

This set contains 651 low-autocorrelation binary sequence (LABS) search problems that were encoded to SAT problems by first encoding them as pseudo-Boolean problems and then as SAT problems.  Instances from this set were first used in the SAT Competition 2013 in the crafted category [@mugrauer2013-2].  We split this benchmark set uniformly at random into 350 training and 351 test instances, and used it in both the 2013 and 2014 CSSCs. 

#### 

These 835 instances [@manthey-sat14r] represent a parameterized unsatisfiable variation of the well-known $n$-queens problem, in which the task is to place $n$ queens on a chess board with $n \times n$ fields such that they do not attack each other.  In the variation considered here, the (unsatisfiable) problem is to either place $n+1$ *rooks* or $n+1$ queens on a board of size $n \times n$. Additional constraints enforcing that there is a piece in each row/column/diagonal make it easier to prove unsatisfiability, and these constraints can be enabled or disabled by generator parameters. [ We used the generator provided by Norbert Manthey to generate instances with $n \in [10,50]$, using all rooks or all queens, using six different problem encodings, and using all combinations of enabling/disabling all types of constraints.  We then removed trivial instances, ending up with 835 instances.  For the CSSC 2014, we selected 484 training instances uniformly at random and used the remaining 351 as test instances.]{} 

Random Benchmark Sets {#sec:benchmarks-random}
---------------------

#### 

This is a set of 600 randomly-generated 3-SAT instances at the phase transition (clause to variable ratio of approximately 4.26).  It includes both satisfiable and unsatisfiable instances.  The set includes 100 instances each with 200 variables (853 clauses), 225 variables (960 clauses), 250 variables (1066 clauses), 275 variables (1172 clauses), 300 variables (1279 clauses), and 325 variables (1385 clauses).  These 600 instances were generated by Lin Xu using the random instance generator from the 2009 SAT competition, and were previously described by [@bayless-lion14a [@bayless-lion14a]]{}.  We employed their uniform random split into 300 training and [300 test instances, using all 300 test instances in the CSSC 2013 (random track) and only a subset of 250 test instances in the CSSC 2014 (random track).]{} 

#### 

This is a set of 750 random 3-SAT instances (satisfiable and unsatisfiable) at the phase transition, with 350 variables and 1493 clauses.  These instances were generated by the ToughSAT instance generator [@bebel-sat13a] and split into 500 training and 250 test instances uniformly at random.  We used this benchmark set in the 2014 CSSC (random track). 

#### 

This set contains only unsatisfiable 5-SAT instances generated uniformly at random with 50 variables and 1056 clauses (a clause-to-variable ratio sharply on the phase transition).  The instances were generated by the uniform random generator used in the SAT Challenge 2012 and SAT Competition 2013, with satisfiable instances being filtered out by running the SLS solver .  We used this benchmark set in both the 2013 and 2014 CSSCs (random track). 

#### 

This is a set of 500 3-SAT instances at the phase transition, all satisfiable.  Each instance has 1000 variables and 4260 clauses.  These instances were previously described by [@tompkins-sat11 [@tompkins-sat11]]{}.  We used their uniform random split into 250 training and test instances in the 2013 CSSC (random track) and in the 2014 CSSC (random satisfiable track). 

#### 

This set contains 500 5-SAT instances generated uniformly at random with a clause-to-variable ratio of 20.  Each instance is satisfiable and has 500 variables and 10000 clauses.  This set was first used for tuning the SAT solver Captain Jack and other SLS solvers [@tompkins-sat11].  We used the original uniform random split into 250 training and test instances in the 2014 CSSC (random satisfiable track). 

#### 

This set contains 500 7-SAT instances generated uniformly at random with a clause-to-variable ratio of 85.  Each instance is satisfiable and has 90 variables and 7650 clauses.  This set was also first used for tuning the SAT solver Captain Jack and other SLS solvers [@tompkins-sat11].  We used the original uniform random split into 250 training and test instances in the 2014 CSSC (random satisfiable track). 

Instance Features Used for these Benchmark Sets {#sec:instance-features}
-----------------------------------------------

As described in \[sec:algoconf-smac\], can use instance features to guide its search.  Such instance features have predominantly been studied in the work on SATzilla for algorithm selection [@nudelman2004understanding; @xu-jair08a] and in machine learning models for predicting algorithm runtime [@hutter-aij14a].  These features range from simple summary statistics, such as the number of variables or clauses in an instance, to the results of short, runtime-limited probes with local search solvers.  In the context of algorithm configuration, we can afford somewhat more expensive features than for algorithm selection since we only require them on the *training* instances (not the test instances) and can compute them once, offline.  Nevertheless, we kept feature computation costs low to not add substantially to the time required for algorithm configuration.  For the instance sets where we already had available instance features from previous work, we used those features.  In particular, we used the 138 features described by [@hutter-aij14a [@hutter-aij14a]]{} for the datasets , , , , and .  For the set , we did not compute features since these instances were very easy to solve even with algorithm defaults (note that also worked very well without features).  For the other datasets, we computed a subset of 119 features, including basic features and feature groups based on survey propagation, clause learning, local search probing, and search space size estimates.[^11]

Configuration Procedures {#app:conf-proc-details}
========================

This appendix describes the configuration procedures we used in more detail.  Configurators typically iterate the following steps: (1) execute the target algorithm on one or more instances with one or more configurations for a limited amount of time; (2) measure the resulting performance metric and (3) decide upon the next target algorithm execution.  Beyond the key question of [which configuration]{} to try next, configurators also need to decide how many runs and which instances to use for each evaluation, and after which time to terminate unsuccessful runs. , ,  and differ in how they instantiate these components. 

: Local Search in Configuration Space {#sec:algoconf-pils}
-------------------------------------

 [@hutter-jair09a], short for iterated local search in parameter configuration space, generalizes the simple (often manually performed) tuning approach of changing one parameter at a time and keeping changes if performance improves.  While that simple tuning approach is a local search that terminates in the first local optimum, carries out an iterated local search [@lourencco-handbook03a] that applies perturbation steps in each local optimum $o$ in order to escape $o$’s basin of attraction and carry out another local search that leads to another local optimum $o'$. Iterated local search then decides whether to continue from the new optimum $o'$ or to return to the previous optimum $o$, thereby performing a biased random walk over locally optimal solutions.  only supports categorical parameters, so numerical parameters need to be discretized before is run.  is an algorithm framework with two different instantiations that differ in their strategy of deciding how many runs to use to evaluate each configuration.  The most straightforward instantiation, *BasicILS*(N), resembles the approach most frequently used in manual parameter optimization: it evaluates each configuration according to a fixed number of $N$ runs on a fixed set of instances.  While this approach is simple and intuitive, it gives rise to the problem of how to set the number $N$. Setting $N$ to a large value yields slow evaluations; using a small number yields fast evaluations, but the evaluations are often not representative for the instance set $\Pi$ (for example, if we choose $N$ runs we can cover at most $N$ instances, even if we only allow a single run per instance).  The second instantiation, *FocusedILS*, solves this problem by allocating most of its runs to strong configurations: it starts with a single run per configuration and incrementally performs more runs for promising configurations.  This means that it can often afford a large number of runs for the best configurations while rejecting most poor configurations based on a few runs.  There is also a guarantee that configurations that were ‘unlucky’ can be revisited in the search, allowing for a proof that FocusedILS—if run indefinitely—will eventually identify the configuration with the best performance on the entire training set. 

Finally, also implements a mechanism for adaptively choosing the time after which to terminate unsuccessful target algorithm runs.  Intuitively, when comparing the performance of two configurations ${{\bm{\theta}}}_{1}$ and ${{\bm{\theta}}}_{2}$ on an instance, and we already know that ${{\bm{\theta}}}_{1}$ solves the instance in time $t_1$, we do not need to run ${{\bm{\theta}}}_{2}$ for longer than $t_1$: we do not need to know precisely *how bad* ${{\bm{\theta}}}_{2}$ is, as long as we know that ${{\bm{\theta}}}_{1}$ is better.  More precisely, each comparison of configurations in is with respect to an instance set $\Pi_{sub} \subset \Pi$, and evaluations of ${{\bm{\theta}}}_{2}$ can be terminated prematurely when ${{\bm{\theta}}}_{2}$’s aggregated performance on $\Pi_{sub}$ is provably worse than that of ${{\bm{\theta}}}_{1}$. In practice, this so-called *adaptive capping* mechanism can speed up ’s progress by orders of magnitude when the best configuration solves instances much faster than the overall maximal cutoff time [@hutter-jair09a].  For all experiments in this paper, we used the FocusedILS variant of the most recent publicly available release 2.3.7[^12] with default parameters. 

: Gender-based Genetic Algorithm {#app:gga}
--------------------------------

The *Gender-based Genetic Algorithm ()* [@ansotegui-cp09a] is a configuration procedure that maintains a population of configurations and proceeds according to an evolutionary metaphor, evolving the population over a number of *generations* in which pairs of configurations mate and produce offspring.  also uses the concept of *gender*: each configuration is labeled with a gender chosen uniformly at random, and when configurations are selected to mate there are separate selection pressures for each gender: configurations from the first gender are selected based on their empirical performance, whereas configurations from the other gender are selected uniformly at random.  The second gender thus serves as a pool of diversity, countering premature convergence to a poor parameter configuration. 

Unlike ’ local search mechanism, ’s recombination operator for combining the parameter values of two parent configurations can operate directly on numerical parameter domains, avoiding the need for discretization. 

Like , implements an adaptive capping mechanism, elegantly combining it with a parallelization mechanism that lets it effectively use multiple processing units.  only ever evaluates configurations in the selection step for the first gender, and its strategy is to evaluate several candidates in parallel until the first one succeeds.  Here, the number of configurations to be evaluated in parallel is taken to be identical to the number of processing units available, $\#units$.[^13]

Like the FocusedILS variant of , also implements an “intensification” mechanism for increasing the number of runs $N$ it performs for each configuration over time.  Specifically, it keeps $N$ constant in each generation, starting with small $N_{start}$ in the first generation, and linearly increasing $N$ up to a larger $N_{target}$ in generation $G_{target}$ and thereafter; $N_{start}$, $N_{target}$, and $G_{target}$, are parameters of . 

For all experiments in the CSSC, we used the most recent publicly available version of , version $1.3.2$.[^14] ’s author Kevin Tierney kindly provided a script to convert the parameter configuration space description for each solver from the competition’s pcs format[^15] to ’s native xml format.  This script allowed us to run for all solvers except those with complex conditionals. 

Next to the parameters $\#units$, $N_{start}$, $N_{target}$, and $G_{target}$ mentioned above, free parameters include the maximal number of generations, $G_{max}$ and the size of the population, $P_{size}$. The setting of these parameters considerably affects ’s behaviour and also determines its overall runtime (when run to completion).  If there is an external fixed time budget (as in the CSSC), these parameters can be modified to ensure that GGA does not finish far too early (thus not making effective use of the available configuration budget) while simultaneously ensuring that runs do not take far too long (in which case configuration would be cut off in one of the first generations, where the search is basically still random sampling).  It is thus important to set GGA’s parameters carefully.  We set the following parameters to values hand-chosen by Kevin Tierney for the CSSC (leaving all other parameters at their default values): $\#units = 4$, $P_{size} = 50$, $G_{target} = 75$, $G_{max} = 100$, $N_{start} = 4$, $N_{target} = \text{\#(training instances in the scenario)}$.[^16] We performed a post hoc analysis, which suggests that these parameters may yet not be optimal: often finished relatively few generations within its configuration budget.  It might thus make sense to use a smaller value of $N_{target}$ in the future to reduce the number of instances considered per configuration.  However, this means that would never consider all instances and may overtune as a result.  How to best set ’s parameters is therefore an open research question. 

: Sequential Model-based Algorithm Configuration {#sec:algoconf-smac}
------------------------------------------------

In contrast to the model-free configurators and ,  [@hutter-lion11a] is a sequential model-based algorithm configuration method, which means that it uses predictive models of algorithm performance [@hutter-aij14a] to guide its search for good configurations.  More specifically, it uses previously observed $\langle{}$configuration, performance$\rangle{}$ pairs $\langle{}{{\bm{\theta}}},
f({{\bm{\theta}}})\rangle{}$ to learn a random forest of regression trees (see, [*e.g.*]{}, [@breimann-mlj01a]) that express a function $\hat{f}:{{\bm{\Theta}}}\rightarrow \mathds{R}$ predicting the performance of arbitrary parameter configurations (including those not yet evaluated) and then uses this function to guide its search.  When instance characteristics $x_\pi \in \mathcal{F}$ are available for each problem instance $\pi$, uses observed $\langle{}$configuration, instance characteristic, performance$\rangle{}$ triplets $\langle{}{{\bm{\theta}}},
x_\pi, f({{\bm{\theta}}},\pi)\rangle{}$ to learn a function $\hat{g}:{{\bm{\Theta}}}\times \mathcal{F} \rightarrow \mathds{R}$ that predicts the performance of arbitrary parameter configurations on instances with arbitrary characteristics.  These so-called *empirical performance models* [@hutter-aij14a] are then marginalized over the instance characteristics of all training benchmark instances in order to derive the function $\hat{f}$ that predicts average performance for each parameter configuration: $\hat{f}({{\bm{\theta}}}) = \mathds{E}_{\pi \sim \Pi_{train}} \left[ \hat{g}({{\bm{\theta}}}, \pi) \right].$ This performance model is used in a sequential optimization process as follows.  After an initialization phase, iterates the following three steps: (1) use the performance measurements observed so far to fit a marginal random forest model $\hat{f}$; (2) use $\hat{f}$ to select a promising configuration ${{\bm{\theta}}}\in {{\bm{\Theta}}}$ to evaluate next, trading off exploration in new parts of the configuration space and exploitation in parts of the space known to perform well; and (3) run ${{\bm{\theta}}}$ on one or more benchmark instances and compare its performance to the best configuration observed so far. 

employs a similar criterion as FocusedILS to determine how many runs to perform for each configuration, and for finite configuration spaces in the limit it also provably converges to the best configuration on the training set.  Unlike , does not require that the parameter space be discretized. 

When used to optimize target algorithm runtime, implements an adaptive capping mechanism similar to the one used in .  When this capping mechanism prematurely terminates an algorithm run we only observe a lower bound of the algorithm’s runtime.  In order to construct predictive models of algorithm runtime in the presence of such so-called *right-censored data points*, applies model-building techniques derived from the survival analysis literature [@hutter-bayesopt11]. 

Hors-Concours Solver  {#sec:riss3ext-discussion}
=====================

So far, we have limited our analysis to the ten open-source solvers that competed for medals.  Recall that one additional solver, , only participated *hors concours*.  It was not eligible for a medal, because it had been submitted as closed source, being based on a highly experimental code branch of that had not been exhaustively tested and was therefore likely to contain bugs. 

As discussed in Section \[sec:controlled\_execution\], our experimental protocol included various safeguards against such bugs: we measured runtime and memory externally, compared reported solubility status against true solubility status where this was known, and checked returned models when an instance was reported satisfiable.  Our configuration pipeline detected and penalized these crashes automatically, enabling the configuration procedures to continue their search and find configurations with no or few crashes.  In fact, the final best configurations identified by our configuration pipeline performed very well and would have handily won both the industrial and the crafted track of the CSSC 2013 had been submitted as open source: in the industrial track, it only left 82 problem instances unsolved (compared to 115 for ); and in the crafted track only 44 (compared to 96 for ).  Even though most of the instances did not solve were due to it crashing, all of these were ‘legal’ crashes that simply did not output a solution (such as segmentation faults).  In particular, we never observed to produce an incorrect output for a CSSC test instance with known satisfiability status.  However, empirical tests with benchmark instances are of course no substitute for formal correctness guarantees, and even seasoned solvers can have bugs.  Indeed, after the competition, ’s developer found a bug in it (in on-the-fly clause improvement [@on-the-fly-clause-improvement]) that caused some satisfiable instances to be incorrectly labeled as unsatisfiable.[^17] This being the case, it was fortunate that was ineligible for medals. 

While empirical testing on benchmark instances, as done in a competition, can never guarantee the correctness of a solver, in future CSSCs, we consider tightening solubility checks on the benchmark instances used, by either limiting the benchmark sets to contain only instances with known satisfiability status or to require (and check) proofs of unsatisfiability, as in the certified UNSAT track of the SAT competition. 

Additional results with PAR-1 score {#sec:more-results-par1}
===================================

 

Figure \[fig:configurability-vs-parameters-par1\] visualizes runtime speedups obtained for each solver, counting timeouts at the cutoff time as the cutoff time itself (PAR-1).  Compared to the PAR-10 results in Figure \[fig:configurability-vs-parameters\], speedups with PAR-1 are up to a factor of ten smaller for benchmark/solver combinations with many timeouts for the default, but otherwise results are qualitatively similar. 

[^1]: <http://www.cs.colostate.edu/~ipc2014/>

[^2]: An alternative definition considers the optimization of expected performance across a *distribution* of instances rather than average performance across a *set* of instances [@hutter-jair09a].  What we consider here can be seen as a special case where the distribution is uniform over a given set of training instances.  It is also possible to optimize performance metrics other than mean performance across instances, but mean performance is by far the most widely used option. 

[^3]: We did not use the iterated racing method I/F-Race [@lopez-ibanez-tech11a], since it does not effectively support runtime optimization and its authors thus discourage its use for this purpose (personal communication with Manuel L[ó]{}pez-Ib[á]{}[ñ]{}ez and Thomas Stützle). 

[^4]: <http://www.cs.ubc.ca/labs/beta/Projects/CSSC2013/>

[^5]: <http://aclib.net/cssc2014/>

[^6]: We executed this competition on the META cluster at the University of Freiburg, whose compute nodes contained 64GB of RAM and two 2.60GHz Intel Xeon E5-2650v2 8-core CPUs with 20 MB L2 cache each, running Ubuntu 14.04 LTS, 64bit. 

[^7]: Worse-than-default performance on the training set is possible since configurators only base their decisions on a *subset* of the training instances; that subset increases over time and only reaches the full training set when the configuration process is given enough time. 

[^8]: Specifically, we ran 32 runs for 10 days each. 

[^9]: Of course, it is simple to construct examples where a solver with a single parameter is highly configurable ([*e.g.*]{}, let the parameter have a poor default setting) or where a solver has many parameters but does not benefit from configuration at all ([*e.g.*]{}, a solver could expose many parameters that are not actually used at all).  The focus of our analysis is therefore on the relationship between configurability and the number of parameters that a solver author reasonably expected would be useful to expose. 

[^10]: [Note that the larger graphs have varying node degrees, and that each node can only match with other nodes of the same degree; this allows the encoding to generate much fewer clauses than in the worst case of equal node degrees.]{} 

[^11]: The code for computing these features is available at <http://www.cs.ubc.ca/labs/beta/Projects/EPMs/>. 

[^12]: <http://www.cs.ubc.ca/labs/beta/Projects/ParamILS/>

[^13]: This coupling of adaptive capping and parallelization is the reason that should not be run on a single core if the objective is to minimize runtime. 

[^14]: <https://wiwi.uni-paderborn.de/dep3/entscheidungsunterstuetzungssysteme-und-operations-research-jun-prof-dr-tierney/research/source-code/>

[^15]: <http://aclib.net/cssc2014/pcs-format.pdf>

[^16]: Actually, due to a miscommunication, we first ran experiments with $N_{target} = 2000$, obtaining somewhat worse results than reported here.  After double-checking with Kevin Tierney we then re-ran everything with the correct value of $N_{target}$ that depended on the number of training instances in each configuration scenario.  We only report these latter results here. 

[^17]: Personal communication with ’s developer Norbert Manthey.