Approximation Algorithms for Dynamic Assortment Optimization Models

Ali Aouad (), Retsef Levi () and Danny Segev ()
Additional contact information
Ali Aouad: London Business School, London NW1 4SA, United Kingdom
Retsef Levi: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Danny Segev: Department of Statistics, University of Haifa, Haifa 31905, Israel

Mathematics of Operations Research, 2019, vol. 44, issue 2, 487-511

Abstract: We consider the single-period joint assortment and inventory planning problem with stochastic demand and dynamic substitution across products, motivated by applications in highly differentiated markets, such as online retailing and airlines. This class of problems is known to be notoriously hard to deal with from a computational standpoint. In fact, prior to the present paper, only a handful of modeling approaches were shown to admit provably good algorithms, at the cost of strong restrictions on customers’ choice outcomes. Our main contribution is to provide the first efficient algorithms with provable performance guarantees for a broad class of dynamic assortment optimization models. Under general rank-based choice models, our approximation algorithm is best possible with respect to the price parameters, up to lower-order terms. In particular, we obtain a constant-factor approximation under horizontal differentiation, where product prices are uniform. In more structured settings, where the customers’ ranking behavior is motivated by price and quality cues, we derive improved guarantees through tailor-made algorithms. In extensive computational experiments, our approach dominates existing heuristics in terms of revenue performance, as well as in terms of speed, given the myopic nature of our methods. From a technical perspective, we introduce a number of novel algorithmic ideas of independent interest, and unravel hidden relations to submodular maximization.

Keywords: assortment planning; inventory management; choice models; dynamic optimization; approximation algorithms; submodularity (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/moor.2018.0933 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:44:y:2019:i:2:p:487-511

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().