Abstract:

In this work, we study two-stage distributionally robust mixed-integer programs with uncertain parameters having finite discrete support. This setting is particularly attractive from a computational perspective because the DRO problem remains tractable and can be reformulated as a (possibly much larger) mixed-integer program, allowing the use of standard optimization technology. We propose an ambiguity set defined through a generalized optimal transportation problem. This formulation extends the classical Kantorovich ambiguity set, enabling the modeling of a wider range of practical situations while preserving useful structural properties. We analyze the main characteristics of this ambiguity set and discuss how they affect the structure of the resulting optimization problem.

Three solution frameworks are investigated. The first is the Benders-like method proposed by Bansal, Huang, and Mehrotra (2018). The second derives a single-stage formulation obtained by dualizing the transportation problem defining the ambiguity set. The third uses an epigraph formulation with dynamically generated optimality cuts in a row-and-column generation scheme. The approaches are evaluated on a distributionally robust location–transportation problem with uncertain demand. Computational results show that the relative performance of the approaches depends strongly on the characteristics of the ambiguity set: the dualization approach is simple and effective in the easiest instances, the row-and-column generation performs well when the ambiguity set approximates robust optimization, and the Benders-type method is preferable in the remaining settings.