Empirical analysis tools for the study of algorithm design scenarios

News

Abstract

We propose empirical analysis approaches for studying the tradeoffs arising when comparing several competing algorithm designs. These approaches can provide insight into performance variation both across candidate algorithms and across instances. They can also identify the best tradeoff between evaluating a larger number of candidate algorithm designs, performing these evaluations on a larger number of problem instances, and allocating more time to each algorithm run. We applied these tools to a study of the rich algorithm design spaces offered by three highly-parameterized, state-of-the-art algorithms for satisfiability and mixed integer programming, considering six different distributions of problem instances. We demonstrate that the resulting algorithm design scenarios differ in many ways, with important consequences for both automatic and manual algorithm design, and we expect that our methods and findings will lead to tangible improvements in algorithm design methods.

People

• Frank Hutter, Ph.D. student (UBC)
• Holger Hoos, Associate Professor (UBC)
• Kevin Leyton-Brown, Assistant Professor (UBC)

Papers

• Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown.
  Tradeoffs in the Empirical Evaluation of Competing Algorithm Designs
  To appear in Annals of Mathematics and Artificial Intelligence's Special Issue on Learning and Intelligent Optimization (2010).

Algorithms and parameters considered

• The algorithms we configured and their parameters are described on a separate webpage.
• Here, we simply list the 1000 parameter settings used for each of the 3 algorithms CPLEX, Spear, and Satenstein.
  In each case, the format is the same as the traj files in ParamILS: ignore the first 5 columns (they do have meaning in the traj files, but not here); every column past that corresponds to a parameter. The ith row in these files corresponds to the (i+1)th column in the input matrices below (+1 since the 1st column in the input matrices is the instance name)
• 1000 samples of CPLEX's parameter configuration space
• 1000 samples of Spear's parameter configuration space
• 1000 samples of SATenstein's parameter configuration space Note that in the case of SATenstein the first and the second 500 samples are from different sub-configuration spaces (DLS and non-DLS, respectively), in which many of the parameters have a very different meanining

Data (input matrices)

• CPLEX-regions100
• CPLEX-ORLIB
• Spear-IBM
• Spear-SWV (for a while the online version of this file had a column missing; that old file is here)
• Satenstein-QCP
• Satenstein-SWGCP

Software

• Empirical analysis tools in Matlab (single .m file, 30KB)

Please send any questions, concerns or comments to Frank Hutter