Article ID: | iaor200969557 |
Country: | United States |
Volume: | 55 |
Issue: | 8 |
Start Page Number: | 769 |
End Page Number: | 784 |
Publication Date: | Dec 2008 |
Journal: | Naval Research Logistics |
Authors: | Taaffe Kevin, Tirumalasetty Deepak, Romeijn H Edwin |
Keywords: | newsboy problem |
Consider a supplier offering a product to several potential demand sources, each with a unique revenue, size, and probability that it will materialize. Given a long procurement lead time, the supplier must choose the orders to pursue and the total quantity to procure prior to the selling season. We model this as a selective newsvendor problem of maximizing profits where the total (random) demand is given by the set of pursued orders. Given that the dimensionality of a mixed-integer linear programming formulation of the problem increases exponentially with the number of potential orders, we develop both a tailored exact algorithm based on the L-shaped method for two-stage stochastic programming as well as a heuristic method. We also extend our solution approach to account for piecewise-linear cost and revenue functions as well as a multiperiod setting. Extensive experimentation indicates that our exact approach rapidly finds optimal solutions with three times as many orders as a state-of-the-art commercial solver. In addition, our heuristic approach provides average gaps of less than 1% for the largest problems that can be solved exactly. Observing that the gaps decrease as problem size grows, we expect the heuristic approach to work well for large problem instances.