Robust combinatorial optimization under convex and discrete cost uncertainty

Abstract

In this survey, we discuss the state of the art of robust combinatorial optimization under uncertain cost functions. We summarize complexity results presented in the literature for various underlying problems, with the aim of pointing out the connections between the different results and approaches, and with a special emphasis on the role of the chosen uncertainty sets. Moreover, we give an overview over exact solution methods for NP-hard cases. While mostly concentrating on the classical concept of strict robustness, we also cover more recent two-stage optimization paradigms.

Keywords

• 90C99