Robust Capacity Planning with General Upgrading

General upgrading is a strategy that a firm can upgrade a customer with any higher-end product whenever a lower-end product is out-of-stock. In this paper, we consider the capacity planning problem to decide the initial capacity for multiple products to maximize the expected total profit when general upgrading is allowed. Given the marginal mean and variance information of the demand distribution for each product, we formulate it as a two-stage distributionally robust optimization (DRO) model. 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 second-stage problem of general upgrading can be equivalently reformulated as a one-level upgrading problem allowing for "product return", which significantly reduces the dimension of the problem. We then propose an algorithm that recursively partitions the polyhedron of the dual of the general upgrading problem into simpler subsets whose extreme points can be effectively characterized. When the revenue from upgrading is large, our exact SOCP reformulation admits a polynomial size. Finally, we conduct extensive numerical experiments to demonstrate the efficiency of our algorithm and validate the out-of-sample performance of the DRO solution.