Randomization refers to the process of taking decisions randomly according to the outcome of an independent randomization device such as a dice or a coin flip. The concept is unconventional, and somehow counterintuitive, in the domain of mathematical programming, where deterministic decisions are usually sought even when the problem parameters are uncertain. However, it has recently been shown that using a randomized, rather than a deterministic, strategy in non-convex distributionally robust optimization (DRO) problems can lead to improvement in their objective values. It is still unknown, though, what is the magnitude of improvement that can be attained through randomization or how to numerically find the optimal randomized strategy. In this paper, we study the value of randomization in mixed-integer DRO problems and show that it is bounded by the improvement achievable through its convex relaxation. Furthermore, we identify conditions under which the bound is tight. We then develop an algorithmic procedure, based on column generation, for solving two-stage linear DRO problems with randomization that can be used with both moment-based and Wasserstein ambiguity sets. Finally, we apply the proposed algorithm to solve three classical discrete DRO problems: the assignment problem, the uncapacitated facility location problem, and the capacitated facility location problem, and report numerical results that show the quality of our bounds and the computational performance of the proposed solution method.
Citation
Working paper, June 2018.