A column generation scheme for distributionally robust multi-item newsvendor problems


référence BibTeX

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.

, 26 pages

Application de recherche


G2161.pdf (570 Ko)