Operations Research Seminar: Michaël Poss, LIRMM

An introduction to robust combinatorial optimization

Michaël Poss, LIRMM

Robust optimization (RO) has become a central framework to handle the uncertainty that arises in the parameters of optimization problems. While classical RO results can efficiently handle linear programs for a large variety of uncertainty sets, the situation is more complex for optimization problems involving discrete decisions. Efficient exact or approximate solution algorithms for such problems must exploit the combinatorial structure of the problems at hand. In this tutorial, we shall review key results of this field, which has witnessed a revival in the last ten years since the introduction of structured uncertainty sets (budget, ellipsoids, ...). We will show how the static robust counterparts of many polynomially solvable problems remain polynomially solvable, and highlight problems that turn NP-hard.