Tutorials' Abstract

Thursday, 6th September 2007

17:00 Tutorial 1: An overview of software framework for SLS methods
Luca Di Gaspero
Universita degli Studi di Udine, Italy

Over the last few years a number of general software frameworks for SLS methods have been proposed in the literature. Despite the interest of the research community on this subject, there is, however, no widely-accepted software tool--a situation which is very different from that in other domains like ILP or CP. A possible (but not the only) explanation of this phenomenon is the lack of a unified view of Local Search, which is reflected in a number of different design choices done in software tools. The framework user is forced to adhere to another researcher's SLS view in order to use the framework, making this adoption harder.

In this tutorial, I will present a general overview of SLS software frameworks highlighting the similarities and differences in the SLS model employed and their impact in the design choices. I will analyze the main contributions in this research area and I will show some example on the coding of SLS algorithms using the different frameworks.

Friday, 7th September 2007

PDF slides of the tutorial

Due to the complexity of theoretical analysis, heuristic algorithms for optimization are commonly evaluated on the basis of computational experiments. The tutorial reviews the issues related to the empirical analysis of the implementations of stochastic local search algorithms. It treats the choice of performance measure and reviews different scenarios of analysis. By using applied examples, it presents exploratory data analysis techniques for the graphical representation of the results and for the discovery of patterns in the data collected. Then, it examines the statistical tests which, if used, might increase the reliability and scientific value of the results presented in research papers. The tutorial focuses on the basic concepts of statistical testing such as parametric, nonparametric tests, multiple comparisons and sequential testing and poses some open issues. It prepares the field for the more advanced methods that will be presented in rest of the program planned for the day.

17:00 Tutorial 3: Basic and advanced statistic techniques for algorithm engineering
Ruben Ruiz
Valencia University of Technology, Spain

Sound and detailed statistical experimentation is a must in disciplines like industrial engineering or medical sciences. However, this is not the case in the area of algorithm engineering.

Among other issues, there are three main aspects to consider when working with algorithms and specially with metaheuristics. First, we have the design and calibration, i.e., how to choose different operators and/or techniques and how to set them in order to improve performance. Second, there is the analysis or the ability to explain performance differences as a function of the different parameters or operators used. Lastly, we have the algorithm comparison or how to effectively claim which algorithm is best. All these issues have to be dealt within an environment that includes stochasticity, large sets of input instances and many, many other lurking potential problems.

In this tutorial we will briefly overview some advanced statistic techniques that can be very helpful when dealing with these problems. We will talk about design of experiments, from complete factorials to mixed level fractional factorial designs, unfolding, confounding and many specific topics related with algorithmic experimentation. Some brief hints will be given about non-parametric statistical designs, advanced decision trees and CHAID techniques that are useful when dealing with categorical response variables.

Saturday, 8th September 2007

09:30 Tutorial 4: Reactive Search
Roberto Battiti
DISI - Dipartimento di Ingegneria e Scienza dell'Informazione, Universita' di Trento, Italy

Most state-of-the-art heuristics are characterized by a certain number of choices and free parameters, whose appropriate setting is a subject that raises issues of research methodology. In some cases the role of the user as an intelligent (learning) part makes the reproducibility of heuristic results difficult and, as a consequence, the competitiveness of alternative techniques depends in a crucial way on the user's capabilities. Reactive Search advocates the use of simple sub-symbolic machine learning to automate the parameter tuning process and make it an integral (and fully documented) part of the algorithm. The word "reactive" hints at a ready response to events during the search through an internal online feedback loop for the self-tuning of critical parameters. Task-dependent and local properties of the configuration space can be used by the algorithm to determine the appropriate balance between diversification and intensification.

In the tutorial we will overview the state-of-the art in various stochastic local search technique from the specc point of view of identifying and using opportunities for learning and self-adaptation.