Decomposition Algorithms for Two-Stage Distributionally Robust Mixed Binary Programs

In this paper, we introduce and study a two-stage distributionally robust mixed binary problem (TSDR-MBP) in which the random parameters follow the worst-case distribution belonging to an uncertainty set of probability distributions. We present a decomposition algorithm, which utilizes a distribution separation procedure and parametric cuts within Benders' algorithm or the L-shaped method, to solve TSDR-MBPs with binary variables in the first stage and mixed binary programs in the second stage. We refer to this algorithm as a distributionally robust integer (DRI) L-shaped algorithm. Using a similar decomposition framework, we provide another algorithm to solve a TSDR linear problem where both stages have only continuous variables. We investigate conditions and the families of ambiguity sets for which our algorithms are finitely convergent. We present two examples of ambiguity set, defined using moment matching or the Kantorovich--Rubinstein distance (Wasserstein metric), which satisfy the foregoing conditions. We also present a cutting surface algorithm to solve TSDR-MBPs. We computationally evaluate the performance of the DRI L-shaped algorithm and the cutting surface algorithm in solving distributionally robust versions of a few instances from the stochastic integer programming library, in particular stochastic server location and stochastic multiple binary knapsack problem instances. We also discuss the usefulness of incorporating partial distribution information in two-stage stochastic optimization problems.