Adaptive capping reduces the cost of algorithm configuration by ending an evaluation when a valid bound already rules out winning the comparison. For nonnegative runtimes, completed runs and elapsed time in the current run can provide a lower bound on the final cost. ParamILS distinguishes trajectory-preserving capping from a more aggressive heuristic policy.[ref]
Consider an original comparison of mean runtime over fixed runs. The incumbent has mean seconds, or total seconds. A candidate has completed runs taking and seconds, and its third run has already taken seconds. Even if all remaining work took zero time, the final mean would satisfyContinuing that candidate cannot improve this comparison. The partial total itself supplies the certificate; no prediction of the remaining runtime is needed.
By contrast, after only the first two runs, their observed mean is , but rejecting solely on that partial mean would be invalid: the four-run lower bound is only . Two sufficiently fast remaining runs could still win. The denominator must correspond to the comparison objective.
A censored algorithm runtime is therefore not an observed completed runtime. Record the cutoff and what bound it establishes. Timeout penalties, changing instance sets or non-runtime objectives require a bound compatible with their own scoring rules. A heuristic early-stopping rule may be useful without preserving the same search decisions as full evaluation.
New to topics? Read the docs here!