IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v60y2014i10p2583-2601.html
   My bibliography  Save this article

Constrained Assortment Optimization for the Nested Logit Model

Author

Listed:
  • Guillermo Gallego

    (Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027)

  • Huseyin Topaloglu

    (School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853)

Abstract

We study assortment optimization problems where customer choices are governed by the nested logit model and there are constraints on the set of products offered in each nest. Under the nested logit model, the products are organized in nests. Each product in each nest has a fixed revenue associated with it. The goal is to find a feasible set of products, i.e., a feasible assortment, to maximize the expected revenue per customer. We consider cardinality and space constraints on the offered assortment, which limit the number of products and the total space consumption of the products offered in each nest, respectively. We show that the optimal assortment under cardinality constraints can be obtained efficiently by solving a linear program. The assortment optimization problem under space constraints is NP-hard. We show how to obtain an assortment with a performance guarantee of 2 under space constraints. This assortment also provides a performance guarantee of 1/(1- (epsilon) ) when the space requirement of each product is at most a fraction (epsilon) of the space availability in each nest. Building on our results for constrained assortment optimization, we show that we can efficiently solve joint assortment optimization and pricing problems under the nested logit model, where we choose the assortment of products to offer to customers, as well as the prices of the offered products.Data, as supplemental material, are available at http://dx.doi.org/10.1287/mnsc.2014.1931 . This paper was accepted by Dimitris Bertsimas, optimization.

Suggested Citation

  • Guillermo Gallego & Huseyin Topaloglu, 2014. "Constrained Assortment Optimization for the Nested Logit Model," Management Science, INFORMS, vol. 60(10), pages 2583-2601, October.
    • Handle: RePEc:inm:ormnsc:v:60:y:2014:i:10:p:2583-2601
    DOI: 10.1287/mnsc.2014.1931
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.2014.1931
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.2014.1931?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. A. Gürhan Kök & Marshall L. Fisher & Ramnath Vaidyanathan, 2008. "Assortment Planning: Review of Literature and Industry Practice," International Series in Operations Research & Management Science, in: Narendra Agrawal & Stephen A. Smith (ed.), Retail Supply Chain Management, chapter 0, pages 99-153, Springer.
    2. Anderson, Simon P & de Palma, Andre, 1992. "Multiproduct Firms: A Nested Logit Approach," Journal of Industrial Economics, Wiley Blackwell, vol. 40(3), pages 261-276, September.
    3. Joern Meissner & Arne Strauss & Kalyan Talluri, 2011. "An Enhanced Concave Program Relaxation for Choice Network Revenue Management," Working Papers MRG/0020, Department of Management Science, Lancaster University, revised Jan 2011.
    4. McFadden, Daniel, 1980. "Econometric Models for Probabilistic Choice among Products," The Journal of Business, University of Chicago Press, vol. 53(3), pages 13-29, July.
    5. 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.
    6. 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.
    7. 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.
    8. Sumit Kunnumkal & Huseyin Topaloglu, 2008. "A refined deterministic linear program for the network revenue management problem with customer choice behavior," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(6), pages 563-580, September.
    9. Timothy Richards, 2007. "A nested logit model of strategic promotion," Quantitative Marketing and Economics (QME), Springer, vol. 5(1), pages 63-91, March.
    10. Lingxiu Dong & Panos Kouvelis & Zhongjun Tian, 2009. "Dynamic Pricing and Inventory Control of Substitute Products," Manufacturing & Service Operations Management, INFORMS, vol. 11(2), pages 317-339, December.
    11. Qian Liu & Garrett van Ryzin, 2008. "On the Choice-Based Linear Programming Model for Network Revenue Management," Manufacturing & Service Operations Management, INFORMS, vol. 10(2), pages 288-310, October.
    12. Dan Zhang & Daniel Adelman, 2009. "An Approximate Dynamic Programming Approach to Network Revenue Management with Customer Choice," Transportation Science, INFORMS, vol. 43(3), pages 381-394, August.
    13. Daniel McFadden & Kenneth Train, 2000. "Mixed MNL models for discrete response," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 15(5), pages 447-470.
    14. Train,Kenneth E., 2009. "Discrete Choice Methods with Simulation," Cambridge Books, Cambridge University Press, number 9780521747387.
    15. Kalyan Talluri, 2010. "A randomized concave programming method for choice network revenue management," Economics Working Papers 1215, Department of Economics and Business, Universitat Pompeu Fabra, revised Oct 2011.
    16. Hongmin Li & Woonghee Tim Huh, 2011. "Pricing Multiple Products with the Multinomial Logit and Nested Logit Models: Concavity and Implications," Manufacturing & Service Operations Management, INFORMS, vol. 13(4), pages 549-563, October.
    17. Juan José Miranda Bront & Isabel Méndez-Díaz & Gustavo Vulcano, 2009. "A Column Generation Algorithm for Choice-Based Network Revenue Management," Operations Research, INFORMS, vol. 57(3), pages 769-784, June.
    18. Paat Rusmevichientong & David Shmoys & Chaoxu Tong & Huseyin Topaloglu, 2014. "Assortment Optimization under the Multinomial Logit Model with Random Choice Parameters," Production and Operations Management, Production and Operations Management Society, vol. 23(11), pages 2023-2039, November.
    19. Guillermo Gallego & Ruxian Wang, 2014. "Multiproduct Price Optimization and Competition Under the Nested Logit Model with Product-Differentiated Price Sensitivities," Operations Research, INFORMS, vol. 62(2), pages 450-461, April.
    20. Paat Rusmevichientong & Zuo-Jun Max Shen & David B. Shmoys, 2010. "Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint," Operations Research, INFORMS, vol. 58(6), pages 1666-1680, December.
    21. Ward Hanson & Kipp Martin, 1996. "Optimizing Multinomial Logit Profit Functions," Management Science, INFORMS, vol. 42(7), pages 992-1003, July.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. W. Zachary Rayfield & Paat Rusmevichientong & Huseyin Topaloglu, 2015. "Approximation Methods for Pricing Problems Under the Nested Logit Model with Price Bounds," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 335-357, May.
    3. Jacob B. Feldman & Huseyin Topaloglu, 2017. "Revenue Management Under the Markov Chain Choice Model," Operations Research, INFORMS, vol. 65(5), pages 1322-1342, October.
    4. 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.
    5. 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.
    6. Ruxian Wang & Zizhuo Wang, 2017. "Consumer Choice Models with Endogenous Network Effects," Management Science, INFORMS, vol. 63(11), pages 3944-3960, November.
    7. Rui Chen & Hai Jiang, 2020. "Capacitated assortment and price optimization under the nested logit model," Journal of Global Optimization, Springer, vol. 77(4), pages 895-918, August.
    8. Mika Sumida & Guillermo Gallego & Paat Rusmevichientong & Huseyin Topaloglu & James Davis, 2021. "Revenue-Utility Tradeoff in Assortment Optimization Under the Multinomial Logit Model with Totally Unimodular Constraints," Management Science, INFORMS, vol. 67(5), pages 2845-2869, May.
    9. Ali Aouad & Danny Segev, 2021. "Display Optimization for Vertically Differentiated Locations Under Multinomial Logit Preferences," Management Science, INFORMS, vol. 67(6), pages 3519-3550, June.
    10. Meng Qi & Ho‐Yin Mak & Zuo‐Jun Max Shen, 2020. "Data‐driven research in retail operations—A review," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(8), pages 595-616, December.
    11. Dan Zhang & Larry Weatherford, 2017. "Dynamic Pricing for Network Revenue Management: A New Approach and Application in the Hotel Industry," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 18-35, February.
    12. Hongmin Li & Scott Webster & Nicholas Mason & Karl Kempf, 2019. "Product-Line Pricing Under Discrete Mixed Multinomial Logit Demand," Service Science, INFORMS, vol. 21(1), pages 14-28, January.
    13. Xi Chen & Chao Shi & Yining Wang & Yuan Zhou, 2021. "Dynamic Assortment Planning Under Nested Logit Models," Production and Operations Management, Production and Operations Management Society, vol. 30(1), pages 85-102, January.
    14. 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.
    15. Antoine Désir & Vineet Goyal & Danny Segev & Chun Ye, 2020. "Constrained Assortment Optimization Under the Markov Chain–based Choice Model," Management Science, INFORMS, vol. 66(2), pages 698-721, February.
    16. 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.
    17. Ruxian Wang, 2018. "When Prospect Theory Meets Consumer Choice Models: Assortment and Pricing Management with Reference Prices," Manufacturing & Service Operations Management, INFORMS, vol. 20(3), pages 583-600, July.
    18. Anton J. Kleywegt & Hongzhang Shao, 2022. "Revenue Management Under the Markov Chain Choice Model with Joint Price and Assortment Decisions," Papers 2204.04774, arXiv.org.
    19. Gallego, Guillermo & Li, Anran & Truong, Van-Anh & Wang, Xinshang, 2020. "Approximation algorithms for product framing and pricing," LSE Research Online Documents on Economics 101983, London School of Economics and Political Science, LSE Library.
    20. Chan, Rebecca & Li, Zhaolin & Matsypura, Dmytro, 2020. "Assortment optimisation problem: A distribution-free approach," Omega, Elsevier, vol. 95(C).

    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:ormnsc:v:60:y:2014:i:10:p:2583-2601. 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.