Joint Assortment and Inventory Planning Under the Markov Chain Choice Model

We address the joint assortment and inventory optimization problem for an online retailer facing a set of N substitutable products. The retailer must determine both the assortment and inventories of these products before the start of the selling season to maximize the expected profit. We consider a setting with dynamic SOBS, where consumers’ choices follow the Markov chain choice model. This is a challenging problem, and even computing the expected profit for a given assortment and inventory solution requires solving an intractable dynamic program. We present a sample average approximation-based algorithm for the problem that achieves a regret of [Formula: see text] with respect to an linear program (LP) upper bound. Our algorithm first selects an assortment by balancing the expected revenue (from a single consumer) and the inventory cost. We do this by identifying a subset of products that can pool demand from the universe of substitutable products without significantly cannibalizing the revenue in the presence of dynamic substitution behavior of consumers. We then use a sample average approximation-based LP to decide on the inventory level for each item in the selected assortment. We numerically show that our algorithm considerably improves the performance over standard approaches from the literature on a wide range of instances of the Markov chain choice model and demonstrate that it carefully handles the inventory of products in the long tail (i.e., products with small mean total demand). This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported by Amazon [Research Award (V. Goyal and O. El Housni)] and the National Science Foundation [Grants CMMI 1636046 (V. Goyal) and 2226900 (O. El Housni)]. The research was partially supported by RGC from Hong Kong [Grant 16215820 (G. Gallego)]. Supplemental Material: The online appendices and data files are available at https://doi.org/10.1287/mnsc.2023.01322 .