Christoph Buchheim, Technical University of Dortmund

Abstract

An interesting class of nonlinear discrete optimization problems arises in robust optimization. For a combinatorial optimization problem with linear but uncertain objective, the (strictly) robust counterpart has a nonlinear objective whose characteristics depend on the considered uncertainty set. E.g., if the latter is an ellipsoid, the objective can be modelled by a second-order cone constraint. A lot of effort has been put into the investigation of specific combinatorial structures, in order to develop tailored algorithms or to show hardness results. In our talk, the focus is on algorithms that can access the underlying combinatorial structure only via a linear optimization or a separation routine. We first discuss the existence of oracle-polynomial algorithms for some typical classes of uncertainty sets. In the second part of the talk, we present new algorithmic approaches that allow to deal with general ellipsoidal or polytopal uncertainty sets, which lead to NP-hard problems in general. These approaches are based on well-known methods from continuous optimization, such as the Frank-Wolfe 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.