A Column Generation Scheme for Distributionally Robust Multi-Item Newsvendor Problems

In this paper, we study a distributionally robust multi-item newsvendor problem, where the demand distribution is unknown but specified with a general event-wise ambiguity set. Using the event-wise affine decision rules, we can obtain a conservative approximation formulation of the problem, which can typically be further reformulated as a linear program. In order to efficiently solve the resulting large-scale linear program, we develop a column generation-based decomposition scheme and speed up the computational efficiency by exploiting a special column selection strategy and stopping early based on a Karush–Kuhn–Tucker condition test. Focusing on the Wasserstein ambiguity set and the event-wise mean absolute deviation set, a computational study demonstrates the computational efficiency of the proposed algorithm over a set of 540 randomly generated instances, significantly outperforming the commercial solver and a Benders decomposition method.

Citation

HEC Montreal, 2021, working paper

Article

Download

View A Column Generation Scheme for Distributionally Robust Multi-Item Newsvendor Problems