Communications of the ACM

CPLEX22 is the most widely used commercial MIP solver. BIGMIX is a highly heterogenous mix of publicly available mixed integer programming problems. As with the mix of SAT instances in our first benchmark, linear regression struggled with predictions for some types of instances and occasionally made catastrophic mispredictions. Again, random forests performed much more robustly. RCW models the dispersal and territory establishment of the redcockaded woodpecker conditional on decisions about which parcels of land to protect. 1 The runtime of CPLEX for this domain was surprisingly predictable; random forests yielded among the best EHM performance we have ever observed.

Beyond Single Algorithms

Unlike average-case complexity re-
sults that characterize the inherent
complexity of a computational prob-
lem, EHMs always describe the perfor-
mance of a given algorithm. In some
sense this is an inherent limitation: a
statistical approach cannot summarize
the performance of algorithms that
have not yet been invented. However,
there is a useful way in which we can
relax the single-algorithm restriction:
we can build a model that describes a
space of existing algorithms.
More specifically, most state-of-the-
art algorithms for hard combinatorial
problems offer a range of algorithm
parameters in order to enable users
to customize or tune the algorithm’s
behavior. We define “parameters” very
broadly, as encompassing any argu-
ment passed to a solver that changes
its behavior (and, thus, its runtime)
but not the nature of the solution it re-
turns. Parameters can thus be contin-
uous, categorical, ordinal, or Boolean,
and can even be conditional on val-
ues taken by other parameters. More
importantly, categorical and Boolean
parameters can be used to represent
very abstract decisions—effectively
selecting among unrelated blocks of
code—and can thereby open up vast
algorithm design spaces. For example,
IBM ILOG CPLEX exposes 76 param-
eters ( 45 categorical, six Boolean, 18
integer, and seven real-valued); 17 a
fairly coarse discretization of these pa-
rameters yields over 1047 different al-
gorithm instantiations with vastly dif-
ferent performance profiles. We call
such an instantiation of all parameters
of a given algorithm to specific values
a configuration. The second example
of a parameterized solver we use here
is the SAT solver SPEAR, 4 which ex-
poses 26 parameters (seven categori-
cal, three Boolean, four integer, and 12
real-valued), giving rise to over 1017 dif-
ferent algorithm instantiations.
We now consider generalizing
EHMs to describe such parameterized
algorithms. In principle, this is not
much of a change: we consider mod-
els that map from a joint space of con-
figurations and instance features to
runtime predictions. The question is
how well such an approach can work.
Before we can give an answer, we need
to decide how to evaluate our meth-
ods. We could test on the same con-
figurations that we used to train the
EHM but on new problem instances,
on new configurations but on previ-
ously seen instances, or on combina-
tions of previously unseen configura-
tions and instances.

The third case is the hardest; it is the only setting for which we show results here. Figure 5 illustrates some representative results in this setting, focusing on random forest models. The first row shows scatterplots like those presented earlier, with each point representing a run of a randomly selected, previously unseen

Figure 4. Visual comparison of models for runtime predictions on unseen instances. In each plot, the x-axis denotes true runtime and the y-axis runtime as predicted by the respective model. Predictions above 3,000 or below 0.001 are denoted by a blue x.