Algorithm configuration

Algorithm configuration chooses settings of a parameterized algorithm to improve its performance on a specified class of inputs. An algorithm parameter space describes the allowed settings; the objective function may measure runtime, solution quality or another declared cost. The target algorithm solves the instances, while a configuration procedure searches for settings under which it works well.^[ref]

For an original example, suppose two settings have runtimes $A=(1,9)$ seconds and $B=(4,4)$ seconds on two instance types. With equally likely types, the mean costs are $5$ and $4$ seconds, favouring $B$. If the first type instead has probability $0.9$, the means become $0.9(1)+0.1(9)=1.8$ and $4$ seconds, favouring $A$. There is no distribution-independent best setting in this example: the intended workload is part of the optimization problem.

Measured cost estimates also depend on time limits, random seeds and which instances were sampled. Report those choices and evaluate the chosen setting on previously unused instances. Reusing the tuning results as the only evidence of improvement rewards settings that happened to fit the observed sample.

ParamILS supplies a concrete search procedure for this problem. Algorithm selection is a related decision about which algorithm to run for an instance, whereas the example above fixes one parameterized target and chooses its settings. In both cases, specifying what may change is necessary to interpret an experimental comparison.