Hasso-Plattner-Institut
 

HPI Kolloquium: "Optimization - From Classic Approaches to Black-Box Heuristics"

Timo Kötzing (HPI)

24. November 2016

Abstract

Optimization problems are everywhere: whether we want to find a fast way to work or whether expensive industrial machinery needs to be tuned to give optimal performance, we have it in our hands to save time and or money. Typical optimization problems come with many side constraints and contradictory goals, sometimes measuring quality can only be achieved by simulations. Only rarely can one find a straightforward specific algorithm, such as, for example, Dijkstra's Algorithm for finding shortest paths. Sometimes it is possible to remodel a problem as a linear program or in terms of satisfiability. For these types of problems strong solvers are known; however, in most cases problems are too hard to be easily tractable. This is when black-box optimization proves beneficial: these general-purpose optimizers can be applied to any given problem without requiring problem-specific information. This latter approach has the significant advantage that development costs are very low, while applicability is very high. Understanding these algorithms is a challenge of ongoing research, providing insights which lead to new and more powerful optimization algo-rithms. In this talk we will review this evolution of problem solving and show how modern heu-ristics can give very efficient algorithms. We discuss examples where optimization algorithms were applied very successfully, both in research domains (such as bio-informatics or human-com-puter interaction) and industrial domains (such as path finding and design optimization).

Short CV

Timo Kötzing studied computer science and mathematics at the Christian Albrechts University in Kiel. As a Fulbright scholar he continued his education in the USA, receiving his PhD in computer science from the University of Delaware, USA, in 2009. Afterwards, he was a postdoc in Kurt Mehlhorn's Algorithms and Complexity Group of the Max Planck Institute for Informatics, Saar-brücken, Germany. From 2013 till 2015 he was postdoctoral researcher at the University of Jena, Germany. Since June 2015 he is a postdoctoral researcher at the Hasso Plattner Institute in Pots-dam, Germany, Algorithm Engineering Group, where in 2016 he started work on his DFG-"Eigene Stelle" project. His work concerns both the theoretical foundation of learning theory as well as the analysis of randomized search heuristics. Regarding the latter topic he has a strong focus on de-veloping efficient optimization algorithms for black-box search and efficient tools for the analysis of such algorithms. He has over 60 publications in peer-reviewed venues (including leading con-ferences and journals) which received a lot of attention whether in press or as best paper awards. He is a recurrent PC member for the "Genetic and Evolutionary Computation Conference", the top ACM conference for evolutionary computation, including being a co-chair of its "Theory Track" in 2016.

Host: Prof. Dr. Tobias Friedrich