Robust Capacity Planning with General Upgrading

Problem definition : General upgrading is a strategy by which a firm can upgrade a customer to any higher-end product whenever a lower-end product is out of stock. In this paper, we consider the capacity planning problem of deciding the initial capacity for multiple products to maximize the expected total profit when general upgrading is allowed. Methodology/results : We formulate the problem as a two-stage distributionally robust optimization (DRO) model under the commonly employed ambiguity set with marginal mean and variance information. To obtain an exact reformulation as a second-order cone program (SOCP) that is directly solvable, one needs to characterize the extreme points of the dual of the second-stage problem. To this end, we first show that the dual second-stage problem can be equivalently reformulated as an economic lot-sizing problem with bounded inventory constraints. We then derive a binary extended formulation for the extreme points of the dual polyhedron based on the characterization via a shortest path network, which enables a polynomially solvable SOCP. Our characterization of the extreme points can also be used for other ambiguity sets, such as when partial correlation is incorporated or the type 2-Wasserstein ambiguity set, to derive tractable formulations. Managerial implications : Our reformulation of the second-stage problem connects various problems studied separately in the literature, such as appointment-scheduling and economic lot-sizing problems. Our extensive numerical studies show that our DRO solution performs best with limited training data or in highly uncertain environments with nonstationary demand distributions. Using a real data set from a cosmetic company, we also demonstrate that our DRO model yields a higher mean profit and lower variability compared with the sample average approximation.