IMADA > Ansatte > Marco Chiarandini

COMISEF -- T3 Tutorial

We review empirical methods for the analysis of optimization heuristics with applications in econometrics. In the first part, we report from the computer science literature general principles for a correct organization of computational experiments. We then distinguish different scenarios of analysis and model them in statistical terms. Simple graphical representations of results for the comparisons of few well defined algorithms are suggested.

In the central part of the tutorial, we focus on algorithm configuration and parameter tuning. Several empirical methods to carry out these tasks have emerged in the past years. We review the general ideas underlying ANOVA, regression trees, racing procedures, search methods and response surface methodology.

In the last part, we consider the characterization of performance distributions. For run time distributions, we summarize three methods of model fitting, including censored distributions and extreme value theory, and outline a practical application of the models to the decision of restart times. For solution quality distributions, we review an extreme values procedure for the estimation of optimal solutions. Overall, the emphasis is put on the visualization of results by means of graphics that facilitate the exploration of data and the communication of results in an informative and comprehensive way.

The hands on session comprises two exercises. The first exposes the participants to a practical experience of empirical algorithm configuration. The second focuses on model fitting with censored data.

Marco Chiarandini, Last modified: Mon Dec 8 20:18:10 CET 2008