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

Felipe Campelo*, Elizabeth Wanner

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

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.
Original languageEnglish
Pages (from-to)851–883
Number of pages33
JournalJournal of Heuristics
Volume26
Issue number6
Early online date5 Aug 2020
DOIs
Publication statusE-pub ahead of print - 5 Aug 2020

Bibliographical note

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 http://creativecommons.org/licenses/by/4.0/.

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.

Keywords

  • Experimental comparison of algorithms
  • Iterative sampling
  • Multiple hypotheses testing
  • Sample size estimation
  • Statistical methods

Fingerprint Dive into the research topics of 'Sample size calculations for the experimental comparison of multiple algorithms on multiple problem instances'. Together they form a unique fingerprint.

Cite this