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.

## Article

Download

View Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints