Optimization Online


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

Kibaek Kim (kimk***at***anl.gov)

Abstract: 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. In addition, we analyze the structural properties showing that DRMIP, as infinite-dimensional programming, is finitely reducible and thus weakly discretizable. We also prove that the Lagrangian dual of DRMIP is weakly discretizable. Based on these properties, we justify the dual decomposition method for solving DRMIP with a discretized support. 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 DCAP test instances (one of the SIPLIB test instances) and demonstrate the computational performance of the method and the impact of the discretization properties.

Keywords: dual decomposition, distributionally robust optimization, two-stage stochastic mixed-integer programming

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Robust Optimization

Citation: Argonne National Laboratory, ANL/MCS-P9291-0420

Download: [PDF]

Entry Submitted: 04/03/2020
Entry Accepted: 04/03/2020
Entry Last Modified: 04/06/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society