Dual Decomposition of Two-Stage Distributionally Robust Mixed-Integer Programming under the Wasserstein Ambiguity Set

We develop a dual decomposition of two-stage distributionally robust mixed-integer programming (DRMIP) under the Wasserstein ambiguity set. The dual decomposition is based on the Lagrangian dual of DRMIP, which results from the Lagrangian relaxation of the nonanticipativity constraints and min-max inequality. We present two Lagrangian dual problem formulations, each of which is based on different principle. We show that the two dual problems have the same Lagrangian bound. We develop and implement the dual decomposition method that solves the Lagrangian dual of DRMIP, which requires only minor modifications of the existing method for stochastic mixed-integer programming. We also present extensive numerical results on eighty dynamic capacity acquisition and assignment problem test instances (DCAP, one of the SIPLIB test instances) and demonstrate the computational performance of the method and the impact of the discretization properties.