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.
10–2
10–2
10–1
100
101
102
103
10–1
100
101
102
103
Minisat 2.0-COMPETITON
R
idge
reg
res
s
ion
R
and
omF
or
es
t
RMSE=0.95
Concorde-RUE
RMSE=0.41
CPLEX-BIGMIX
RMSE= 1. 1
CPLEX-RCW
RMSE=0.20
RMSE=0.55 RMSE=0.45 RMSE=0.72 RMSE=0.03
10–2
10–2
10–1
100
101
102
103
10–1
100
101
102
103
10–2
10–2
10–1
100
101
102
103
101
102
103
10–1
100
101
102
103
103
102
101
10–2
10–2
10–1
100
101
102
103
10–1
100
101
102
103
10–2
10–2
10–1
100
101
102
103
10–1
100
101
102
103
10–2
10–2
10–1
100
101
102
103
101
102
103
10–1
100
101
102
103
103
102
101