A study of distributionally robust mixed-integer programming with Wasserstein metric: on the value of incomplete data

European Journal of Operational Research. 2024. Vol. 313. No. 2. P. 602–615.

Sergey S. Ketkov

This study addresses a class of linear mixed-integer programming (MILP) problems that involve uncertainty in the objective function parameters. The parameters are assumed to form a random vector, whose 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. First, we prove that the three-level problem admits a single-level MILP reformulation, if the class of loss functions is restricted to biaffine functions. Secondly, it turns out that for several particular forms of data uncertainty, the outlined problem can be solved reasonably fast by leveraging the nominal MILP problem. Finally, we conduct a computational study, where the out-of-sample performance of our model and computational complexity of the proposed MILP reformulation are explored numerically for several application domains.

Keywords: Wasserstein metric, mixed-integer programming, Incomplete data, робастно-стохастическая оптимизация, смешанно-целочисленное программирование, Метрика Вассерштейна, distributionally robust optimization, Uncertainty modeling, Моделирование неопределенности, Неполные данные

Publication based on the results of: Research on graph and network structures and its applications (2023)