TU Darmstadt
| Home      | FB 4      | TU Darmstadt 
Staff members
Jobs and Scholarships
Previous Seminars
How to find us
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 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 (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 Frank Vallentin.

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 standard tools.

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.

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 separation-deviation model

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 method.

09.09.2008: Dr. Carlos E. Ferreira - A polyhedral investigation of the LCS problem and a repetition-free 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 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).)

19.09.2008: Sebastian Stiller - A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
joint work with Vincenzo Bonifaci, Alberto Marchetti-Spaccamela

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 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.