January 29, 2007
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
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
Abstract:
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.