IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v44y2019i2p487-511.html
   My bibliography  Save this article

Approximation Algorithms for Dynamic Assortment Optimization Models

Author

Listed:
  • 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)

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.

Suggested Citation

  • Ali Aouad & Retsef Levi & Danny Segev, 2019. "Approximation Algorithms for Dynamic Assortment Optimization Models," Mathematics of Operations Research, INFORMS, vol. 44(2), pages 487-511, May.
  • Handle: RePEc:inm:ormoor:v:44:y:2019:i:2:p:487-511
    DOI: 10.1287/moor.2018.0933
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2018.0933
    Download Restriction: no

    File URL: https://libkey.io/10.1287/moor.2018.0933?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions - 1," LIDAM Reprints CORE 334, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Mahesh Nagarajan & S. Rajagopalan, 2008. "Inventory Models for Substitutable Products: Optimal Policies and Heuristics," Management Science, INFORMS, vol. 54(8), pages 1453-1466, August.
    3. Paat Rusmevichientong & Huseyin Topaloglu, 2012. "Robust Assortment Optimization in Revenue Management Under the Multinomial Logit Choice Model," Operations Research, INFORMS, vol. 60(4), pages 865-882, August.
    4. Vivek F. Farias & Srikanth Jagabathula & Devavrat Shah, 2013. "A Nonparametric Approach to Modeling Choice with Limited Data," Management Science, INFORMS, vol. 59(2), pages 305-322, December.
    5. Kalyan Talluri & Garrett van Ryzin, 2004. "Revenue Management Under a General Discrete Choice Model of Consumer Behavior," Management Science, INFORMS, vol. 50(1), pages 15-33, January.
    6. James M. Davis & Guillermo Gallego & Huseyin Topaloglu, 2014. "Assortment Optimization Under Variants of the Nested Logit Model," Operations Research, INFORMS, vol. 62(2), pages 250-273, April.
    7. Paat Rusmevichientong & Benjamin Van Roy & Peter W. Glynn, 2006. "A Nonparametric Approach to Multiproduct Pricing," Operations Research, INFORMS, vol. 54(1), pages 82-98, February.
    8. Vishal Gaur & Dorothée Honhon, 2006. "Assortment Planning and Inventory Decisions Under a Locational Choice Model," Management Science, INFORMS, vol. 52(10), pages 1528-1543, October.
    9. Vineet Goyal & Retsef Levi & Danny Segev, 2016. "Near-Optimal Algorithms for the Assortment Planning Problem Under Dynamic Substitution and Stochastic Demand," Operations Research, INFORMS, vol. 64(1), pages 219-235, February.
    10. Siddharth Mahajan & Garrett van Ryzin, 2001. "Stocking Retail Assortments Under Dynamic Consumer Substitution," Operations Research, INFORMS, vol. 49(3), pages 334-351, June.
    11. Guang Li & Paat Rusmevichientong & Huseyin Topaloglu, 2015. "The d -Level Nested Logit Model: Assortment and Price Optimization Problems," Operations Research, INFORMS, vol. 63(2), pages 325-342, April.
    12. Garrett van Ryzin & Siddharth Mahajan, 1999. "On the Relationship Between Inventory Costs and Variety Benefits in Retail Assortments," Management Science, INFORMS, vol. 45(11), pages 1496-1509, November.
    13. Dorothée Honhon & Vishal Gaur & Sridhar Seshadri, 2010. "Assortment Planning and Inventory Decisions Under Stockout-Based Substitution," Operations Research, INFORMS, vol. 58(5), pages 1364-1379, October.
    14. Dorothee Honhon & Sreelata Jonnalagedda & Xiajun Amy Pan, 2012. "Optimal Algorithms for Assortment Selection Under Ranking-Based Consumer Choice Models," Manufacturing & Service Operations Management, INFORMS, vol. 14(2), pages 279-289, April.
    15. Jacob B. Feldman & Huseyin Topaloglu, 2017. "Revenue Management Under the Markov Chain Choice Model," Operations Research, INFORMS, vol. 65(5), pages 1322-1342, October.
    16. A. Gürhan Kök & Marshall L. Fisher, 2007. "Demand Estimation and Assortment Optimization Under Substitution: Methodology and Application," Operations Research, INFORMS, vol. 55(6), pages 1001-1021, December.
    17. Jose Blanchet & Guillermo Gallego & Vineet Goyal, 2016. "A Markov Chain Approximation to Choice Modeling," Operations Research, INFORMS, vol. 64(4), pages 886-905, August.
    18. Stephen A. Smith & Narendra Agrawal, 2000. "Management of Multi-Item Retail Inventory Systems with Demand Substitution," Operations Research, INFORMS, vol. 48(1), pages 50-64, February.
    19. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions," LIDAM Reprints CORE 341, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Victor Martínez-de-Albéniz & Sumit Kunnumkal, 2022. "A Model for Integrated Inventory and Assortment Planning," Management Science, INFORMS, vol. 68(7), pages 5049-5067, July.
    2. Paat Rusmevichientong & Mika Sumida & Huseyin Topaloglu, 2020. "Dynamic Assortment Optimization for Reusable Products with Random Usage Durations," Management Science, INFORMS, vol. 66(7), pages 2820-2844, July.
    3. Kameng Nip & Zhenbo Wang & Zizhuo Wang, 2021. "Assortment Optimization under a Single Transition Choice Model," Production and Operations Management, Production and Operations Management Society, vol. 30(7), pages 2122-2142, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mehrani, Saharnaz & Sefair, Jorge A., 2022. "Robust assortment optimization under sequential product unavailability," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1027-1043.
    2. Amr Farahat & Joonkyum Lee, 2018. "The Multiproduct Newsvendor Problem with Customer Choice," Operations Research, INFORMS, vol. 66(1), pages 123-136, January.
    3. Çömez-Dolgan, Nagihan & Fescioglu-Unver, Nilgun & Cephe, Ecem & Şen, Alper, 2021. "Capacitated strategic assortment planning under explicit demand substitution," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1120-1138.
    4. Çömez-Dolgan, Nagihan & Moussawi-Haidar, Lama & Jaber, Mohamad Y. & Cephe, Ecem, 2022. "Capacitated assortment planning of a multi-location system under transshipments," International Journal of Production Economics, Elsevier, vol. 251(C).
    5. Victor Martínez-de-Albéniz & Sumit Kunnumkal, 2022. "A Model for Integrated Inventory and Assortment Planning," Management Science, INFORMS, vol. 68(7), pages 5049-5067, July.
    6. Mou, Shandong & Robb, David J. & DeHoratius, Nicole, 2018. "Retail store operations: Literature review and research directions," European Journal of Operational Research, Elsevier, vol. 265(2), pages 399-422.
    7. Kameng Nip & Zhenbo Wang & Zizhuo Wang, 2021. "Assortment Optimization under a Single Transition Choice Model," Production and Operations Management, Production and Operations Management Society, vol. 30(7), pages 2122-2142, July.
    8. Ali Aouad & Vivek Farias & Retsef Levi, 2021. "Assortment Optimization Under Consider-Then-Choose Choice Models," Management Science, INFORMS, vol. 67(6), pages 3368-3386, June.
    9. Transchel, Sandra & Buisman, Marjolein E. & Haijema, Rene, 2022. "Joint assortment and inventory optimization for vertically differentiated products under consumer-driven substitution," European Journal of Operational Research, Elsevier, vol. 301(1), pages 163-179.
    10. Strauss, Arne K. & Klein, Robert & Steinhardt, Claudius, 2018. "A review of choice-based revenue management: Theory and methods," European Journal of Operational Research, Elsevier, vol. 271(2), pages 375-387.
    11. Transchel, Sandra, 2017. "Inventory management under price-based and stockout-based substitution," European Journal of Operational Research, Elsevier, vol. 262(3), pages 996-1008.
    12. Yalçın Akçay & Yunke Li & Harihara Prasad Natarajan, 2020. "Category Inventory Planning With Service Level Requirements and Dynamic Substitutions," Production and Operations Management, Production and Operations Management Society, vol. 29(11), pages 2553-2578, November.
    13. Dimitris Bertsimas & Velibor V. Mišić, 2019. "Exact First-Choice Product Line Optimization," Operations Research, INFORMS, vol. 67(3), pages 651-670, May.
    14. Qiu, Jiaqing & Li, Xiangyong & Duan, Yongrui & Chen, Mengxi & Tian, Peng, 2020. "Dynamic assortment in the presence of brand heterogeneity," Journal of Retailing and Consumer Services, Elsevier, vol. 56(C).
    15. Boxiao Chen & Xiuli Chao, 2020. "Dynamic Inventory Control with Stockout Substitution and Demand Learning," Management Science, INFORMS, vol. 66(11), pages 5108-5127, November.
    16. Çömez-Dolgan, Nagihan & Dağ, Hilal & Fescioglu-Unver, Nilgun & Şen, Alper, 2023. "Multi-plant manufacturing assortment planning in the presence of transshipments," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1033-1050.
    17. Vineet Goyal & Retsef Levi & Danny Segev, 2016. "Near-Optimal Algorithms for the Assortment Planning Problem Under Dynamic Substitution and Stochastic Demand," Operations Research, INFORMS, vol. 64(1), pages 219-235, February.
    18. Negin Golrezaei & Hamid Nazerzadeh & Paat Rusmevichientong, 2014. "Real-Time Optimization of Personalized Assortments," Management Science, INFORMS, vol. 60(6), pages 1532-1551, June.
    19. Shin, Hojung & Park, Soohoon & Lee, Euncheol & Benton, W.C., 2015. "A classification of the literature on the planning of substitutable products," European Journal of Operational Research, Elsevier, vol. 246(3), pages 686-699.
    20. Pol Boada-Collado & Victor Martínez-de-Albéniz, 2020. "Estimating and Optimizing the Impact of Inventory on Consumer Choices in a Fashion Retail Setting," Manufacturing & Service Operations Management, INFORMS, vol. 22(3), pages 582-597, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:44:y:2019:i:2:p:487-511. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.