




Seminar In Optimization ST 20008 Abstracts 07.04.2008: Kay Haymacher  Global Optimization: a challenge in theoretical physics
Global Optimization is the most promising approach to solve several problems of molecular biophysics and biomolecular engineering  protein structure prediction and rational drug design by docking being the most prominent ones.
"Thermodynamically" inspired algorithms such as Simulated Annealing (SA) have proven to be most successful to this end. However, SA is an example for two shortcomings of such protocols, as it suffers from: 1) trapping in local minima and 2) unknown internal parameters which have to be well chosen for an efficient search.
We will show two synergistically combinable approaches to overcome these problems: stochastic tunneling (to cope with trapping) and timeseries analysis by detrended fluctuation analysis (to make randomized optimization algorithms parameterfree, thus blackboxlike). We also discuss the applicability of detrended fluctuation analysis on other global optimization algorithms such as Extremal Optimization or Energy Landscape Paving.
back... 26.05.2008: Fernando Mário de Oliveira Filho  The Lovász theta number for infinite graphs on the sphere
An idea central to combinatorial optimization is the use of
relaxations, usually linear programming or semidefinite programming
relaxations, to bound the optimal value of combinatorial optimization
problems. These techniques often provide the best known bounds for
many problems.
In this direction, Lovász (1979) proposed a semidefinite programming
formulation for the maximum stable set problem, which consists of
finding the maximum number of pairwise nonadjacent vertices in a
graph. This formulation is now known as de Lovász theta number and,
together with variants, provides in many cases the best known upper
bounds for the size of a maximum stable set in a graph.
But what if we want to apply similar ideas to infinite graphs? Of
particular interest is the following graph G(n, t), where 1 < t < 1:
its vertices are the points of the (n1)dimensional unit sphere
(which lives in R^n) and two points are adjacent if their inner
product is exactly t. In this context, stable sets are infinite, but
we may restrict ourselves to Lebesgue measurable stable sets and try
to find upper bounds for the maximum measure of such stable sets.
In this talk, I will show how the Lovász theta number, and thus
ultimately ideas from semidefinite programming, can be adapted to
derive bounds of the maximum measure of stable sets on G(n, t). As a
consequence, we obtain new lower bounds for the measurable chromatic
number of the Euclidean space for dimensions 10, ..., 24.
This is based on joint work with Christine Bachoc, Gabriele Nebe, and
Frank Vallentin.
back... 23.06.2008: Silke Möser  Cubical Projectivities
Consider a pure cubical complex K and two facets &sigma and &sigma' of K that share a common ridge ρ. Then we can define the perspectivity &lang &sigma,&sigma' &rang to be a certain combinatorial isomorphism &sigma &rarr &sigma'. Moreover, we define the projectivity along a facet path (i.e., a sequence of facets such that each pair of consecutive facets share a common ridge) to be the concatenation of the corresponding perspectivities.
The set of all projectitivies along closed loops based at a fixed base facet &sigma forms a group, the group &Pi(K,&sigma) of projectivities of K with respect to the base facet σ.
In the talk we will  after briefly recalling the concepts involved  introduce different types of groups of projectivities and give an overview over some results and applications.
back... 01.07.2008: Dr. Dennis Michaels  Novel Convex Underestimators and their Application to the
Synthesis of Combined Reaction Distillation Processes
joint work with J. Gangadwala, U.U. Haus, M. Jach, A. Kienle
and R. Weismantel
Combined reaction distillation processes are an important domain in
chemical process synthesis. One of the challenging tasks in selecting
an optimal design for a combined reaction distillation process is to
determine convex relaxations that yield strong global bounds on optimal
solutions for the underlying nonlinear optimization problem.
Such relaxations are constructed by replacing the involved nonlinear
terms by convex under and concave overestimators. In order to build strong
convex relaxations providing a useful global bound, the estimators have to
be chosen best possible. This leads to the question of determining the convex
and concave envelopes of a function.
In this talk we will focus on a ternary reaction distillation process.
In particular, we consider a model formulation based on wave
functions that includes a certain family of partially convex functions, a
family of affinerational functions and sigmoidal wave functions in two
variables. For all three classes of functions we will present a
description of the envelopes or novel convex underestimators that provide
a better approximation quality than the known estimators obtained by applying
standard tools.
back... 02.07.2008: Kerstin Dächert  Einführung in die multikriterielle Optimierung
Der Vortrag soll einen Einblick in Theorie und Praxis der multikriteriellen
Optimierung geben. Im ersten Teil werden verschiedene Lösungsansätze für
multikriterielle Optimierungsprobleme vorgestellt. Dazu gehören Optimali
tätskonzepte und Skalarisierungsmethoden.
Im zweiten Teil soll anhand eines Beispiels auf die Probleme eingegangen wer
den, die sich speziell bei der multikriteriellen kombinatorischen Optimierung
ergeben.
back... 21.07.2008: Irma Hernandez Magallanes  Seasonality & Volatility: Applications to
Time Series and Point Processes
The modeling of seasonality and volatility is of interest in a variety
of areas like: economics, risk analysis, ecology, transportation,
finance. A review of parametric, nonparametric and hybrid methods for
modeling seasonality and volatility is presented. Two applications are
explored, one in Banking and the other in Forest Fires.
back... 21.07.2008: Erick Moreno Centeno  Country creditrisk rating aggregation via the
separationdeviation model
Country creditrisk ratings are evaluated independently by several
agencies. A common method of aggregating the ratings into a single
rating is by taking their averages (the averaging method). We show
here that an approach that captures the relative ranking of the
countries given by each agency leads to an improved aggregate
rating with respect to several criteria. The approach we use  the
separationdeviation model  was proposed by Hochbaum. We further
prove several properties of the separationdeviation model, including
the property that the aggregate rating obtained by the
separationdeviation model agrees with the majority of agencies or
reviewers, regardless of the scale used. In an experimental study, we
show that the aggregate rating obtained by the separationdeviation
model has fewer rank reversals (discrepancies in the rank ordering of
the countries) than the aggregate rating obtained by the averaging
method.
back... 09.09.2008: Dr. Carlos E. Ferreira  A polyhedral investigation of the LCS problem and a repetitionfree variant /Cristina G. Fernandes, Carlos E. Ferreira, Christian Tjandraatmadja, and Yoshiko Wakabayashi/
Universidade de São Paulo, Brazil
We consider the longest common subsequence problem (lcs) and a variant of it where each symbol may occur at most once in the common subsequence.
The lcs is a wellknown problem that can be solved in polynomial time by a dynamic programming algorithm. We provide a complete description of a
polytope we associate with the lcs. The integrality of this polytope can be derived by showing that it is in fact the clique polytope of a perfect graph.
The repetitionfree version of the problem is known to be difficult. We also associate a polytope with this version and investigate its facial structure.
We present some valid and facetdefining inequalities for this polytope and discuss separation procedures. Finally, we present some computational results
of a branch and cut algorithm we have implemented for this problem.
(this was presented in LATIN 2008: Lecture Notes in Computer Science v. 4957. p. 329338 (2008).)
back... 19.09.2008: Sebastian Stiller  A ConstantApproximate Feasibility Test for Multiprocessor RealTime
Scheduling joint work with Vincenzo Bonifaci, Alberto MarchettiSpaccamela
We devise the first constantapproximate feasibility test for sporadic
multiprocessor realtime scheduling. We give an algorithm that, given a task
system and e > 0, correctly decides either that the task system can be
scheduled using the earliest deadline first algorithm on m speed(21/m+e)
machines, or that the system is infeasible for m speed1 machines. The
running time of the algorithm is polynomial in the size of the task system
and 1/e. We also provide an improved bound trading off speed for additional
machines.
Our analysis relies on a new concept for counting the workload of an
interval, that might also turn useful for analyzing other types of task
systems.
back...

