Robust multi-product newsvendor model with uncertain demand and substitution

This work studies a Robust Multi-product Newsvendor Model with Substitution (R-MNMS), where the demand and the substitution rates are stochastic and are subject to cardinality-constrained uncertainty sets. The goal of this work is to determine the optimal order quantities of multiple products to maximize the worst-case total profit. To achieve this, we first show that for given order quantities, computing the worst-case total profit, in general, is NP-hard. Therefore, we derive the closed-form optimal solutions for the following three special cases: (1) if there are only two products, (2) if there is no substitution among different products, and (3) if the budget of demand uncertainty is equal to the number of products. For a general R-MNMS, we formulate it as a mixed-integer linear program with an exponential number of constraints and develop a branch and cut algorithm to solve it. For large-scale problem instances, we further propose a conservative approximation of R-MNMS and prove that under some certain conditions, this conservative approximation yields an exact optimal solution to R-MNMS. The numerical study demonstrates the effectiveness of the proposed approaches and the robustness of our model.