Sample size calculations for the experimental comparison of multiple algorithms on multiple problem instances

This work presents a statistically principled method for estimating the\nrequired number of instances in the experimental comparison of multiple\nalgorithms on a given problem class of interest. This approach generalises\nearlier results by allowing researchers to design experiments based on the\ndesired best, worst, mean or median-case statistical power to detect\ndifferences between algorithms larger than a certain threshold. Holm's\nstep-down procedure is used to maintain the overall significance level\ncontrolled at desired levels, without resulting in overly conservative\nexperiments. This paper also presents an approach for sampling each algorithm\non each instance, based on optimal sample size ratios that minimise the total\nrequired number of runs subject to a desired accuracy in the estimation of\npaired differences. A case study investigating the effect of 21 variants of a\ncustom-tailored Simulated Annealing for a class of scheduling problems is used\nto illustrate the application of the proposed methods for sample size\ncalculations in the experimental comparison of algorithms.\n