Optimization Online


Robust Combinatorial Optimization under Convex and Discrete Cost Uncertainty

Christoph Buchheim (christoph.buchheim***at***math.tu-dortmund.de)
Jannis Kurtz (jannis.kurtz***at***math.tu-dortmund.de)

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: Robust Optimization, Uncertainty, Combinatorial Optimization, Two-stage Robustness, K-Adaptability, Complexity

Category 1: Robust Optimization

Category 2: Combinatorial Optimization

Category 3: Integer Programming


Download: [PDF]

Entry Submitted: 09/12/2017
Entry Accepted: 09/12/2017
Entry Last Modified: 08/08/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society