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


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

Publication DOI:
Additional Information: This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit Funding: F. Campelo worked under grants from Brazilian agencies FAPEMIG (APQ-01099-16) and CNPq (404988/2016-4). E. F. Wanner has been funded by The Leverhulme Trust through Research Fellowship RF-2018-527/9.
Uncontrolled Keywords: Experimental comparison of algorithms,Iterative sampling,Multiple hypotheses testing,Sample size estimation,Statistical methods,Software,Information Systems,Computer Networks and Communications,Control and Optimization,Management Science and Operations Research,Artificial Intelligence
Publication ISSN: 1381-1231
Last Modified: 27 Jun 2024 10:28
Date Deposited: 06 Aug 2020 12:15
Full Text Link:
Related URLs: https://link.sp ... 732-020-09454-w (Publisher URL)
http://www.scop ... tnerID=8YFLogxK (Scopus URL)
PURE Output Type: Article
Published Date: 2020-12-01
Published Online Date: 2020-08-05
Accepted Date: 2020-07-22
Authors: Campelo, Felipe (ORCID Profile 0000-0001-8432-4325)
Wanner, Elizabeth (ORCID Profile 0000-0001-6450-3043)



Version: Published Version

License: Creative Commons Attribution

| Preview


Version: Accepted Version

Access Restriction: Restricted to Repository staff only

Export / Share Citation


Additional statistics for this record