In this paper, we use a data-driven Wasserstein distributionally robust framework to consider uncertain parameters in optimization problems.

Distributionally robust optimization is an approach to optimization under uncertainty that assumes only partial information on the probability distribution of the uncertain parameters. Unlike the classic approach of stochastic optimization, in DRO, the exact probability distribution is unknown. Instead, we assume that it belongs to an ambiguity set of distributions. The ambiguity set we use is a Wasserstein ball which is, using the Wasserstein metric, the ball centered at the empirical distribution of the training samples dataset, with a chosen radius epsilon. This particular case of DRO is called data-driven Wasserstein DRO.

In the case of a combinatorial optimization problem when only the cost function is affected by uncertainties, we show that the data-driven Wasserstein distributionally robust counterpart of a polynomial problem remains polynomial. More precisely, we prove that, if the optimization problem can be written as a 0-1 integer linear program with n variables, the complexity of solving the distributionally robust counterpart is at most n+1 times the complexity of solving the original problem. This means that every complexity results (related to polynomiality) of an optimization problem is kept for its robust counterpart. For example, the robust counterpart of any alpha-approximable NP-hard 0-1 discrete problem is also alpha-approximable.