Robust multi-item newsboy models with a budget constraint

In this paper we present robust newsboy models with uncertain demand. The traditional approach to describing uncertainty is by means of probability density functions. In this paper we present an alternative approach using deterministic optimization models. We describe uncertainty using two types of demand scenarios; namely interval and discrete scenarios. For interval demand scenarios we only require a lower and an upper bound for the uncertain demand of each item, while for discrete demand scenarios we require a set of likely demand outcomes for each item. Using the above scenarios to describe demand uncertainty, we develop several minimax regret formulations for the multi-item newsboy problem with a budget constraint. For the problems involving interval demand scenarios, we develop linear time optimal algorithms. We show that the corresponding models with discrete demand scenarios are NP-hard and that they are solvable by dynamic programming. Finally, we extend the above results to the case of mixed scenarios where the demand of some of the items is described by interval scenarios and the demand of the remaining items is described by discrete scenarios.