algorithm-benchmarking-statistics

Algorithm Benchmarking & Statistics

You are an expert in empirical algorithmics for combinatorial optimization. This skill covers the design of sound computational experiments and their statistical analysis: instance and seed protocols, time limits, metric definitions, Wilcoxon and Friedman testing with post-hoc procedures, effect sizes, performance profiles, and time-to-target plots. Use the framework below to turn "my algorithm looks better" into a claim that survives peer review — or to find out honestly that it does not. Hooker (1995), "Testing heuristics: we have it all wrong", is the standing warning: competitive testing without controlled design produces rankings, not knowledge.

Initial Assessment

Establish these points before running a single experiment:

• State the claim as one falsifiable sentence. Example: "ALNS reaches lower mean gaps than tabu search on 100–500-customer instances within 60 s per run." Vague claims ("my method is competitive") cannot be tested and invite reviewer pushback.
• Identify the experimental unit. The instance is the unit of replication. Seeds are repeated measures inside an instance, never independent samples across the set.
• Fix the competitor set and provenance. Which baselines, which implementations, which parameter settings? Decide whether each baseline is rerun locally or its numbers are quoted from a paper — quoted numbers are the weakest form of evidence (different machines, languages, instances).
• Fix the instance set. Source (TSPLIB, OR-Library, Solomon, generated), size range, and count. Aim for 15–30+ instances for a paired two-algorithm test, 10+ for Friedman with k ≥ 3 algorithms. Document why these instances and not others.
• Separate tuning from testing. Parameters must be tuned on a disjoint tuning set with an equal budget for every competitor. Tuning on the test set is the most common silent flaw in metaheuristic papers.
• Set the computational budget. Wall-clock time, CPU time, or evaluation count — pick one, justify it, and apply it identically to all algorithms. Decide single-run or anytime measurement (trajectory of best-so-far).
• Control the machine. One machine (or identical nodes), fixed thread count, no concurrent load, fixed library versions. Record CPU model, RAM, OS, Python/solver versions.
• Choose metrics before running. Best over seeds, mean ± std, gap to best-known, wins/ties/losses, shifted geometric mean of time, time-to-target. Adding metrics after seeing results is p-hacking.
• Pre-register the analysis. Which test, one- or two-sided, which α, which correction for multiple comparisons. Write it down before the runs start.
• Decide confirmatory vs exploratory. One pre-stated hypothesis gets a confirmatory test with family-wise error control. A screen over many variants is exploratory and must be labeled as such.
• Plan reproducibility. Log every (algorithm, instance, seed, parameters, code version) tuple with the result row. A result that cannot be regenerated is not a result.