Groupe d’études et de recherche en analyse des décisions

A column generation scheme for two-stage distributionally robust multi-item newsvendor problem

Shanshan Wang HEC Montréal, Canada

Shanshan Wang

In this talk, we study a two-stage distributionally robust multi-item newsvendor problem, where the demand distribution is unknown but specified with a general event-wise ambiguity set (proposed in Chen et al. (2020)). Using the event-wise affine decision rules, we can obtain a conservative approximation formulation of the problem, which, under mild conditions, can be 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 improve the computational efficiency by using a multiple columns strategy and a novel early stopping criterion. Focusing on the Wasserstein ambiguity set and event-wise mean absolute deviation set, a computational study demonstrates the computational efficiency of the proposed algorithm over a set of randomly generated instances. The computational results show that our algorithm significantly outperforms CPLEX and a Benders decomposition method for this class of problems.

This is a joint work with Professor Erick Delage from HEC Montréal.