Combinatorial oOptimization Problems with Probability Constraints

The application of the Distributionally Robust Optimization approach to the problem of linear combinatorial optimization with incomplete data sets is studied in this work. This paper aims at finding the procedure for the transformation of the finite data set to the least conservative estimate of the minimized function, which satisfies the specified asymptotic guarantees. In contrast to the related studies, presented in the literature, we consider the incomplete data sets, i. e. such sets that the number of observations of each component of the random cost vector may vary. We argue that such problem setting might be more applicable to practical conditions. We introduce the algorithm of solving the outlined problem, obtaining a particular distributionally robust optimization problem. More specifically, the decision-maker optimizes the worst-case estimate across all probability distributions with given component-wise relative entropy distance from the empirical marginal distribution for each component. We prove the weak optimality of the outlined method and the asymptotical exponential decrease of the error probability when the size of the data set grows. Finally, we conduct the numerical experiments, which compare our methods with the analogues, presented in the literature.