Adaptive capping
= Adaptive capping
<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.<ParamILS: An Automatic Algorithm Configuration Framework by Frank Hutter and others>[Section 4.1, particularly 4.1.1–4.1.2]{ref}
Consider an original comparison of mean runtime over $N=4$ fixed runs. The incumbent has mean $c_\ast=5$ seconds, or total $20$ seconds. A candidate has completed runs taking $6$ and $7$ seconds, and its third run has already taken $8$ seconds. Even if all remaining work took zero time, the final mean would satisfy
$$
\widehat c_4\ge\frac{6+7+8}{4}=5.25>5.
$$
Continuing 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 $13/2=6.5>5$, but rejecting solely on that partial mean would be invalid: the four-run lower bound is only $13/4=3.25$. 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.