On a class of data-driven mixed-integer programming problems under uncertainty: a distributionally robust approach
This addresses uncertainty in optimization for operations research and decision-making, but it is incremental as it builds on existing distributionally robust methods with a focus on varying observation counts.
The paper tackles data-driven mixed-integer programming under uncertainty by developing prediction and prescription rules with asymptotic guarantees, showing that a Pareto optimal solution can be obtained via a distributionally robust optimization problem using relative entropy distances, and it demonstrates effective out-of-sample performance in numerical experiments.
In this study we analyze linear mixed-integer programming problems, in which the distribution of the cost vector is only observable through a finite training data set. In contrast to the related studies, we assume that the number of random observations for each component of the cost vector may vary. Then the goal is to find a prediction rule that converts the data set into an estimate of the expected value of the objective function and a prescription rule that provides an associated estimate of the optimal decision. We aim at finding the least conservative prediction and prescription rules, which satisfy some specified asymptotic guarantees as the sample size tends to infinity. We demonstrate that under some mild assumption the resulting vector optimization problems admit a Pareto optimal solution with some attractive theoretical properties. In particular, this solution can be obtained by solving a distributionally robust optimization (DRO) problem with respect to all probability distributions with given component-wise relative entropy distances from the empirical marginal distributions. It turns out that the outlined DRO problem can be solved rather effectively whenever there exists an effective algorithm for the respective deterministic problem. In addition, we perform numerical experiments where the out-of-sample performance of the proposed approach is analyzed.