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

Monday, November 25, 2013

Konrad-Zuse-Zentrum für Informationstechnik Berlin
Takustr. 7
14195 Berlin
room: Hörsaal

Lecture - 14:15

Ralf Borndörfer - Konrad-Zuse-Zentrum für Informationstechnik Berlin & FU Berlin

Configuration Models in Transport Optimization

Configurations are local solutions of network optimization problems that can be used to assemble an overall solution. They are used to express complex requirements, that would be hard to formulate using constraints, by means of a local and hence manageable enumeration of ``feasible configurations''. This gives rise to an extended formulation involving additional configuration variables. Usually, one has to make choices between several possible configurations, such that configuration models are often of a set packing, partitioning, or covering type. Such a formulation is combinatorially clean and lends itself to column generation techniques. If the configurations capture a core aspect of the problem, such a model will be provably strong, if the configurations can be computed efficiently, it is algorithmically tractable. Typical examples of configuration models come up in transport optimization, where the integrated treatment of technical etc. constraints or the simultaneous solution of multi-stage models is a major challenge. Successful applications include railway track allocation, leading to path packing configuration models, railway rotation planning, resulting in hypergraph assignment and flow models, and depot management as well as line planning, leading to set partitioning type models. All of these models provide strong LP bounds and can be solved efficiently for large scale real-world problems. The talk surveys these results. It is based on joint work with Martin Grötschel, Olga Heismann, Heide Hoppmann, Marika Karbstein, Torsten Klug, Markus Reuther, Thomas Schlechte, Elmar Swarat, and Steffen Weider.

Colloquium - 16:00

Andreas Paffenholz - TU Darmstadt

Polyhedral Adjunction Theory

Polyhedral adjunction theory allows to study questions of classical adjunction theory for polarized toric varieties from a convex-geometric viewpoint using the associated polyhedral fans and lattice polytopes. Important algebraic invariants like the (unnormalized) spectral value or the nef-value can be defined and studied purely in terms of these polytopes.

Using this approach we obtain new structural results for lattice polytopes and their toric varieties. In particular we can show that a lattice polytope with sufficiently lare spectral value has a Cayley structure, i.e. it allows a non-trivial lattice projection onto a lattice simplex. We can also affirmatively answer a conjecture of Fujita on the spectrum of the spectral value in the toric case.

This is partially based on joint work with Benjamin Nill, Christian Haase, and Sandra Di Rocco.

Letzte Aktualisierung: 18.11.2013