Models and Approximations for Optimization Problems under Uncertainty with Applications to Support Vector Machine and Revenue Management

In this book, we deal with decision making problems plagued by the presence of uncertainty. The first problem we analyze aims at linearly separating two sets of points that have non-disjoint convex closures. To solve this classification task, we formulate robust Support Vector Machine (SVM) models with uncertainty sets in the form of hyperrectangles or hyperellipsoids, and propose a moment-based Distributionally Robust Optimization (DRO) model enforcing limits on observations first-order deviations along principal directions. The efficiency of the new classifiers is evaluated on real-world databases. Numerical experiments show that considering uncertainty explicitly in the models leads to better solutions with respect to the ones provided by the corresponding deterministic program. Despite the wide applicability of DRO models, this class of problems is notoriously difficult to solve. For this reason, secondly, we propose approximation techniques that provide (lower and upper) bounds on the optimal value for DRO problems. This is done through scenario grouping and using the ambiguity sets associated with ϕ-divergences and the Wasserstein distance. Numerical results on a multistage mixed-integer production problem show the efficacy of the novel bounding schemes through different choices of partition strategies, ambiguity sets, and levels of robustness. Thirdly, the last problem we investigate aims at detecting the optimal assortments a retailer shall offer to the market with the aim of maximizing expected profits, when strong preferences among products are observed. This Revenue Management (RM) problem with dominated alternatives is firstly modeled through stochastic dynamic programming, which becomes intractable for instances with a large number of resources. To deal with this curse of dimensionality we recover a compact and tractable deterministic approximation and present preliminary numeric results.