08 març 2013
IBM Research, New York, USA
Meinolf Sellmann

Practically all algorithms have parameters that are partly fixed by
the programmer and partly set by the user. In this talk, we present
the robust, inherently parallel genetic algorithm (GGA) for the
problem of configuring algorithms automatically. GGA tunes
algorithms with categorical, ordinal, and/or continuous parameters
based on a training benchmark set of representative input instances.

In order to cope with the high costs of evaluating the fitness of
individuals, we introduce a gender separation whereby we apply
different selection pressure on both genders.
We then augment our configurator to perform instance-specific
algorithm configuration (ISAC). It is based on the integration of
the GGA configurator and the recently proposed stochastic offline
programming paradigm. Based on an algorithm that computes a feature
vector that characterizes any given input instance, ISAC provides
high quality parameter settings for any new inputs.

Experiments with a variety of different constrained optimization and
constraint satisfaction solvers show that automatic algorithm
configuration vastly outperforms manual tuning. Moreover, we show
that instance-specific tuning frequently leads to significant speed-
ups over instance-oblivious configurations. This work formed the
basis of the IBM 3S SAT Portfolio which won two gold medals at the
2011 SAT Competition and has since led to much improved non-model
based portfolios.


Dr. Meinolf Sellmann is Department Manager of the group "AI for
Optimization" at IBM Research Headquarters in New York. Meinolf works
at the frontier of Operations Research, Algorithms, and Artificial
Intelligence and his research focuses on hard combinatorial feasibility
and optimization problems as they arise in the context of real-world
applications. He is especially interested in the integration of
methods from mathematical programming, approximation theory, and
constraint programming.

Meinolf received his doctorate degree in 2002 from Paderborn
University (Germany) and then went on to Cornell University as
Postdoctoral Associate. From 2004 to 2010 he held a postition as
Assistant Professor at Brown University. Meinolf has published over
60 articles in renowned international conferences and journals, served
as Conference Chair of CP 2007 and PC Chair of CPAIOR 2013, received
multiple best paper nominations and prestigious awards such as an
NSF Early Career Award. Most recently, in 2011 and 2012 Meinolf and
his team won several medals at the SAT Solver Competitions, among
others two gold medals for the most CPU-time efficient SAT solver
for random and crafted SAT instances, and the best multi-engine
approach for industrial SAT instances.