Seminars & Events

Mathematics and Computer Science Division
"Heuristics for Stochastic Optimization: Case Studies in Parameter Tuning and Stochastic Routing Problems"

DATE: April 21, 2010
TIME: 1:00 PM - 2:00 PM
SPEAKER: Prasanna Balaprakash, LANS CACHE Postdoctoral Interviewee
LOCATION: Building 240 Seminar Room 4301, Argonne National Laboratory
HOST: Stefan Wild

Description:
In the first part of the talk, Prasanna will focus on automatic tuning of parameterized algorithms. Many high performing algorithms for computationally hard problems require the setting of a number of parameters to optimize their performance. The task of setting appropriate parameters is essentially a stochastic optimization problem that arises repeatedly in tuning heuristic algorithms and it is relevant for a variety of other contexts. While practitioners frequently tackle this task based on their experience and using rules of thumb, this task can effectively be automatized using automated tuning procedures. Prasanna will discuss our recent research on automated parameter tuning methods for off-line parameter tuning. In particular, Prasanna will present the recently developed Iterative F-race algorithm that tackles the tuning task from a machine learning perspective.

In the second part of the talk, Prasanna will focus on stochastic routing problems. In previous research on stochastic routing problems, most commonly analytical computation approach was used in iterative improvement algorithms and metaheuristics. This is particularly the case for the prototypical examples of stochastic routing problems, such as the probabilistic traveling salesman problem (PTSP). The alternative empirical estimation approach has never been thoroughly investigated. Prasanna will give an overview of our recent research efforts to engineer effective estimation-based iterative improvement algorithms and metaheuristics for the PTSP. Using experimental studies, Prasanna will show that the empirical estimation approach is actually a viable alternative even for the simple, prototypical stochastic routing problems and the estimation-based algorithms outperform by quite a substantial margin previously proposed state-of-the-art algorithms.

Save the event to your calendar [schedule.ics]