Michael Poss : Robust combinatorial optimization

Michael Poss
CNRS, LIRMM, Montpellier

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. We shall also review shortly the very recent propositions to address multi-stage counterparts where some discrete optimization variables can be adapted to the values taken by the uncertain parameters.

Michael Poss a soutenu sa thèse à l'Université Libre de Bruxelles en 2011, suivie par un postdoctorat au Portugal (Aveiro et Coimbra). Il a rejoint le CNRS en 2012 pour travailler dans le laboratoire Heudiasyc, avant de muter au LIRMM en 2014 où il effectue actuellement ses recherches au sein de l'équipe MAORE. Ses travaux récents traitent essentiellement de l'optimisation robuste combinatoire, sujet de sa soutenance d'HdR en 2016, via la programmation mathématique en nombres entiers, et les algorithmes combinatoires. Il dirige plusieurs projets scientifiques (ANR, PHC-Pessoa, ...) et a publié différents articles sur le sujet (Oper. Res., Math. Prog., SIAM J. Opt.).