Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

January 29, 2007

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

Mark de Longueville - Freie Universität Berlin

Topological Methods - An introduction with one and higher dimensional necklaces

Over the last few decades the interaction between combinatorics and topology has become very vital, in particular the use of topological tools in combinatorics has shown to be very powerful. In this talk I want to discuss a typical example of such an application of topology to a combinatorial problem: Noga Alon's Necklace Theorem. We introduce the general scheme that arises, i.e., how do we get from a combinatorial to a topological problem, and sketch a short proof of Alon's theorem. This will lead us to a fair division problem of measures which admits a very beautiful high dimensional generalization that I will discuss in the last part of the talk. (This talk is partly based on joint work with Rade Zivaljevic.)

Colloquium - 16:00

Marco Lübbecke - Technische Universität Berlin

Computational Mixed Integer Programming

Mixed integer programming is a powerful and versatile tool to model a host of practical applications as well as purely mathematical problems from e.g., combinatorial optimization. We briefly review the technique of column generation in integer programming which recently allowed to solve huge complex models. As an example for an application we present the following practical problem. The Cargo Express service of Swiss Federal Railways (SBB Cargo) offers fast overnight transportation of goods between selected train stations in Switzerland and is currently operated as a two-hub and spoke system. We present a model for planning the operation of this service as a whole. It captures the underlying optimization problem with a high level of detail: Traffic routing, train routing, make-up, scheduling, and locomotive assignment are all addressed. At the same time we respect hard constraints like tight service time windows, and train and yard capacities. To the best of our knowledge, such an integration of planning steps into one exact approach has not been successfully attempted before. We describe our approaches for obtaining provably good quality solutions. We conclude our study with computational results on realistic data.

Letzte Aktualisierung: 18.01.2007