Optimization Online


Multi-Product Newsvendor Problem with Customer-driven Demand Substitution: A Stochastic Integer Program Perspective

Jie Zhang (jiezhang***at***vt.edu)
Weijun Xie (wxie***at***vt.edu)
Subhash Sarin (sarins***at***vt.edu)

Abstract: This paper studies a multi-product newsvendor problem with customer-driven demand substitution, where each product, once run out of stock, can be proportionally substituted by the others. This problem has been widely studied in the literature, however, due to nonconvexity and intractability, only limited analytical properties have been reported and no efficient approaches have been proposed. This paper first completely characterizes the optimal order policy when the demand is known and reformulates this nonconvex problem as a discrete submodular maximization model. When the demand is random, we formulate the problem as a two-stage stochastic integer program, derive several necessary optimality conditions, prove the submodularity of the profit function, and also develop polynomial-time approximation algorithms and show their performance guarantees. We further propose a tight upper bound via nonanticipativity dual, which is proven to be very close to the optimal value and can yield a good-quality feasible solution under a mild condition. Our numerical investigation demonstrates effectiveness of the proposed algorithms. Moreover, several useful findings and managerial insights are revealed from a series of sensitivity analyses.

Keywords: Newsvendor Problem, Demand Substitution, Stochastic Program, Submodularity, Approximation Algorithm

Category 1: Applications -- OR and Management Sciences

Citation: submitted to a journal

Download: [PDF]

Entry Submitted: 05/31/2018
Entry Accepted: 06/01/2018
Entry Last Modified: 10/12/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society