 ParamILS

ParamILS is a framework for algorithm configuration based on iterated local search. It explores an algorithm parameter space using improvements to nearby configurations, perturbations and occasional restarts. BasicILS compares configurations on a fixed number of matched training runs; FocusedILS adapts how many runs support a comparison.^[ref]

The distinctive efficiency idea of adaptive capping is to stop spending evaluation time on a candidate once it cannot win the comparison under the stated cost model. Consider an original example with three fixed instances and mean nonnegative runtime as the objective function. A fully evaluated incumbent has total time $12$ seconds, hence mean $4$ seconds. If the first two candidate runs already total $13$ seconds, even a zero-time final run leaves mean at least $13/3>4$. Rejecting that candidate does not require finishing the last run.

This argument depends on its assumptions: the comparison uses the same fixed instance set and a lower bound on unfinished cost. It cannot be transferred unchanged to arbitrary quality scores or a different timeout penalty. The paper distinguishes trajectory-preserving capping from a more aggressive heuristic variant; faster rejection does not always carry the same guarantee.^[ref]

The method turns tuning into a measured optimization experiment, but a good observed configuration is not a proof of a global minimum. The neighborhood, evaluation budget and deployment workload remain relevant to what the returned setting establishes.