Distributionally robust mixed-integer programming with Wasserstein metric: on the value of uncertain data

Sergey S. Ketkov

Published 2023-04-03Version 1

This study addresses a class of linear mixed-integer programming (MIP) problems that involve uncertainty in the objective function coefficients. The coefficients are assumed to form a random vector, which probability distribution can only be observed through a finite training data set. Unlike most of the related studies in the literature, we also consider uncertainty in the underlying data set. The data uncertainty is described by a set of linear constraints for each random sample, and the uncertainty in the distribution (for a fixed realization of data) is defined using a type-1 Wasserstein ball centered at the empirical distribution of the data. The overall problem is formulated as a three-level distributionally robust optimization (DRO) problem. We prove that for a class of bi-affine loss functions the three-level problem admits a linear MIP reformulation. Furthermore, it turns out that in several important particular cases the three-level problem can be solved reasonably fast by leveraging the nominal MIP problem. Finally, we conduct a computational study, where the out-of-sample performance of our model and computational complexity of the proposed MIP reformulation are explored numerically for several application domains.