Optimization Online


The Value of Randomized Solutions in Mixed-Integer Distributionally Robust Optimization Problems

Erick Delage (erick.delage***at***hec.ca)
Ahmed Saif (Ahmed.Saif***at***dal.ca)

Abstract: 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.

Keywords: distributionally robust optimization, randomized strategies, mixed-integer programming

Category 1: Robust Optimization

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

Citation: Working paper, June 2018.

Download: [PDF]

Entry Submitted: 06/21/2018
Entry Accepted: 06/21/2018
Entry Last Modified: 07/26/2018

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