Monday, November 25, 2013
Konrad-Zuse-Zentrum für Informationstechnik Berlin
Takustr. 7
14195 Berlin
room: Hörsaal
Lecture - 14:15
Abstract:
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
Abstract:
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.