 BasicILS

BasicILS is the fixed-evaluation variant of ParamILS. In $\mathrm{BasicILS}(N)$, competing parameter settings are compared using the same $N$ benchmark runs, with matched instances and random seeds.^[ref] The comparison rule supplies the cost estimates used by the surrounding iterated local search.

For mean runtime, writewhere $r_i$ is the recorded cost on the specified run. Consider invented costs $A=(1,1,19)$ seconds and $B=(5,5,5)$ seconds. With only the first run, $A$ appears better, $1<5$. Across all three runs, its mean is $7$ seconds while $B$ remains at $5$ seconds. Choosing $N$ therefore affects both evaluation expense and how much instance variation the estimate captures.

Using the same run list makes that example a comparison on common evidence. Comparing $A$ only on easy instances with $B$ on harder ones would answer a different question. Even a matched finite sample can be unrepresentative of future workloads, so the final configuration still needs evaluation on unused instances.

FocusedILS changes the allocation of runs rather than requiring the same fixed $N$ for every explored candidate. Adaptive capping can avoid completing an already-lost runtime comparison under a valid lower-bound rule. Neither modification makes a finite observed mean a proof of the best possible setting in the entire algorithm parameter space.