Mi, 15.11.2017, 17:15

FÄLLT AUS!! Oraclebased Algorithms for Robust Optimization
Mathematisches Kolloquium
Referent:
Prof. Dr. Christoph Buchheim, Technische Universität Dortmund
Raum:
S214 /24
Zuvor findet um 16:45 Uhr die Teerunde in Raum 244 des
Mathematikgebäudes (S2/15), Schlossgartenstaße 7, statt. Combinatorial optimization problems arise in many applications, e.g., when computing a shortest path in a street network. In practice, the problem data is often uncertain: the actual travel time needed when using a street depends on the traffic situation and is thus not exactly predictable. The robust optimization approach tries to take such uncertainties into account already in the problem formulation, by asking for solutions that remain feasible in each likely scenario and that optimize the worst case over all these scenarios. However, most algorithms devised in the literature have two drawbacks: firstly, they are problemspecific, which means that the developed methods cannot easily be generalized to other applications. Secondly, many approaches are not able to model correlations between uncertain coefficients in an appropriate way. In particular, few publications address the general case of ellipsoidal uncertainty, which arises naturally when coefficients are assumed to be normally distributed. This is partly due to the fact that most combinatorial optimization problems under ellipsoidal uncertainty cannot be solved efficiently (in theory), in particular when correlations are taken into account. However, these correlations are highly relevant in practice: if it takes a long time to travel a street due to heavy traffic, the same is true with high probability for neighboring streets. In the talk, new algorithmic approaches are discussed that allow to deal with general ellipsoidal or polytopal uncertainty sets. These approaches are based on wellknown methods from continuous optimization, such as the FrankWolfe technique or active set methods, and do not depend on the specific combinatorial structure but require only an optimization or a separation oracle for the underlying problem.
