We review linear statistical models for the analysis of computational experiments on optimization algorithms. The models offer the mathematical framework to separate the effects of algorithmic components and instance features included in the analysis. We regard test instances as drawn from a population and we focus our interest not on those single instances but on the whole population. Hence, instances are treated as a random factor. Overall these experimental designs lead to mixed effects linear models. We present both the theory to justify these models and a computational example in which we analyze and comment on several possible experimental designs. The example is a component-wise analysis of local search algorithms for the 2-edge-connectivity augmentation problem. We use standard statistical software to perform the analysis and report the R commands. Data sets and the analysis in SAS are available in an online compendium.
|Title of host publication||Experimental Methods for the Analysis of Optimization Algorithms|
|Editors||Thomas Bartz-Beielstein, Marco Chiarandini, Luís Paquete, Mike Preuss|
|Publication status||Published - 2010|