In this paper, we study a robust two-stage concept of combinatorial optimization problems under discrete demand uncertainty.
Combinatorial optimization problems are based on a finite set of elements for which we decide whether they are part of a solution.
We divide the elements into two types, the so-called fixed and free elements.
In a first stage, we irrecoverably decide whether some fixed elements are part of a solution despite uncertain demand.
In a second stage, we decide whether some free elements complete a solution after a demand scenario is realized.
The objective is to find a robust solution that minimizes the worst-case cost over a finite scenario set.
We show the $\mathcal{NP}$-hardness of this robust two-stage version of several specific combinatorial optimization problems under discrete demand uncertainty but provide a polynomial-time solvable special case.
In particular, we apply this concept to three combinatorial optimization problems: the representative multi-selection, the shortest path, and the minimum weight perfect $b$-matching problem.
We prove the $\mathcal{NP}$-hardness and present special cases solvable in pseudo-polynomial and polynomial time.