Seminar In Optimization ST 20008
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 time-series analysis by detrended fluctuation analysis (to make randomized optimization algorithms parameter-free, thus black-box-like). We also discuss the applicability of detrended fluctuation analysis on other global optimization algorithms such as Extremal Optimization or Energy Landscape Paving.
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
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 (n-1)-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
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.
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 affine-rational 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
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
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, non-parametric and hybrid methods for
modeling seasonality and volatility is presented. Two applications are
explored, one in Banking and the other in Forest Fires.
21.07.2008: Erick Moreno Centeno - Country credit-risk rating aggregation via the
Country credit-risk 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
separation-deviation model -- was proposed by Hochbaum. We further
prove several properties of the separation-deviation model, including
the property that the aggregate rating obtained by the
separation-deviation 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 separation-deviation
model has fewer rank reversals (discrepancies in the rank ordering of
the countries) than the aggregate rating obtained by the averaging
09.09.2008: Dr. Carlos E. Ferreira - A polyhedral investigation of the LCS problem and a repetition-free variant
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 well-known 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 repetition-free 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 facet-defining 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. 329-338 (2008).)
/Cristina G. Fernandes, Carlos E. Ferreira, Christian Tjandraatmadja, and Yoshiko Wakabayashi/
Universidade de São Paulo, Brazil
19.09.2008: Sebastian Stiller - A Constant-Approximate Feasibility Test for Multiprocessor Real-Time
We devise the first constant-approximate feasibility test for sporadic
multiprocessor real-time 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-(2-1/m+e)
machines, or that the system is infeasible for m speed-1 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
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
joint work with Vincenzo Bonifaci, Alberto Marchetti-Spaccamela