Title:

Joint Assortment and Inventory Optimization under the Markov chain choice model

Abstract:

We consider a joint assortment and inventory optimization problem faced by a seller who needs to decide on both the assortment and the inventories of a set of N substitutable products before the start of a selling season to maximize the expected profit. This is an important problem faced by most retailers in many product categories where the inventory decisions need to be made in advance of the selling season. 

We model dynamic stock-out based substitution using a Markov Chain choice model where substitutions between products are captured via probabilistic transitions. The Markov chain model is a significant generalization of the multinomial logit model and has been shown to provide a good approximation for a large class of choice models under reasonable assumptions. Furthermore, the static assortment optimization remains tractable under this model. In particular, we can solve the unconstrained problem optimally and give a constant factor approximation for the capacity constrained version. 

In this work, we consider a problem where we need to make the assortment and inventory decisions jointly to maximize expected profit from T customers arriving sequentially with i.i.d. preferences according to the given Markov chain choice model. We present a near-optimal algorithm for the problem that achieves an $O(\sqrt{NT})$ regret with respect to an LP upper bound. Our algorithm balances between expected revenue and inventory costs by identifying a subset of products that can pool demand without significantly cannibalizing the revenue in the presence of dynamic substitution. We also present computational experiments that show that our algorithm empirically outperforms natural approaches both on synthetic and realistic instances.

Bio: 

Vineet Goyal is Associate Professor in the Industrial Engineering and Operations Research Department at Columbia University where he joined in 2010. He received his Bachelor's degree in Computer Science from Indian Institute of Technology, Delhi in 2003 and his Ph.D. in Algorithms, Combinatorics and Optimization (ACO) from Carnegie Mellon University in 2008. Before coming to Columbia, he spent two years as a Postdoctoral Associate at the Operations Research Center at MIT. He is interested in the design of efficient and robust data-driven algorithms for large scale dynamic optimization problems with applications in  revenue management and healthcare problems. His research has been continually supported by grants from NSF and industry including NSF CAREER Award in 2014 and faculty research awards from Google, IBM, Adobe and Amazon.