Paper Info
Title
Quantifying homogeneity of instance sets for algorithm configuration
Abstract
Automated configuration procedures play an increasingly prominent role in realising the performance potential inherent in highly parametric solvers for a wide range of computationally challenging problems. However, these configuration procedures have difficulties when dealing with inhomogenous instance sets, where the relative difficulty of problem instances varies between configurations of the given parametric algorithm. In the literature, instance set homogeneity has been assessed using a qualitative, visual criterion based on heat maps. Here, we introduce two quantitative measures of homogeneity and empirically demonstrate these to be consistent with the earlier qualitative criterion. We also show that according to our measures, homogeneity increases when partitioning instance sets by means of clustering based on observed runtimes, and that the performance of a prominent automatic algorithm configurator increases on the resulting, more homogenous subsets.
Year
DOI
Venue
2012
10.1007/978-3-642-34413-8_14
LION
Keywords
Field
DocType
parametric solvers,instance set homogeneity,parametric algorithm,automated configuration procedure,problem instance,partitioning instance set,homogeneity increase,inhomogenous instance set,quantifying homogeneity,algorithm configuration,prominent automatic algorithm configurator,configuration procedure
Configurator,Mathematical optimization,Homogeneity (statistics),Computer science,Algorithm configuration,Parametric statistics,Artificial intelligence,Cluster analysis,Machine learning
Conference
Citations 
PageRank 
References 
3
0.42
31
Authors
2
Name
Order
Citations
PageRank
Marius Schneider12308.21
Holger H. Hoos25327308.70