[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
IDEAS home Printed from https://ideas.repec.org/a/bla/popmgt/v30y2021i7p2122-2142.html
   My bibliography  Save this article

Assortment Optimization under a Single Transition Choice Model

Author

Listed:
  • Kameng Nip
  • Zhenbo Wang
  • Zizhuo Wang
Abstract
In this study, we consider a new customer choice model which we call the single transition choice model. In this model, there is a universe of products and customers arrive at each product with a certain probability. If the arrived product is unavailable, then the seller can recommend a subset of available products and the customer will purchase one of the recommended products or choose not to purchase with certain transition probabilities. The distinguishing features of the model are that the seller can control which products to recommend depending on the arrived product, and each customer either purchases a product or leaves the market after one transition. We study the assortment optimization problem under this model. Particularly, we show that it is NP‐Hard even if the customer can transition from each product to at most two products. Despite the computational complexity, we provide polynomial time algorithms or approximation algorithms for several special cases, such as when the customer can only transition from each product to at most a given number of products and the size of each recommended set is bounded. Our approximation algorithms are developed by invoking the submodularity arguments, or connecting the problem with maximum constraint satisfaction problem and applying randomized rounding techniques to its semidefinite programming relaxation. We also provide a tight worst‐case performance bound for revenue‐ordered assortments. In addition, we propose a compact mixed‐integer program formulation, which is efficient for moderate size problems. Finally, we conduct numerical experiments to demonstrate the effectiveness of the proposed algorithms.

Suggested Citation

  • 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.
    • Handle: RePEc:bla:popmgt:v:30:y:2021:i:7:p:2122-2142
    DOI: 10.1111/poms.13358
    as

    Download full text from publisher

    File URL: https://doi.org/10.1111/poms.13358
    Download Restriction: no
    File URL: https://libkey.io/10.1111/poms.13358?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. Szarek, Stanislaw J. & Werner, Elisabeth, 1999. "A Nonsymmetric Correlation Inequality for Gaussian Measure," Journal of Multivariate Analysis, Elsevier, vol. 68(2), pages 193-211, February.
    2. 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.
    3. Benjamin Scheibehenne & Rainer Greifeneder & Peter M. Todd, 2010. "Can There Ever Be Too Many Options? A Meta-Analytic Review of Choice Overload," Journal of Consumer Research, Journal of Consumer Research Inc., vol. 37(3), pages 409-425, October.
    4. 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.
    5. Train,Kenneth E., 2009. "Discrete Choice Methods with Simulation," Cambridge Books, Cambridge University Press, number 9780521766555.
    6. 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.
    7. Jacob B. Feldman & Huseyin Topaloglu, 2017. "Revenue Management Under the Markov Chain Choice Model," Operations Research, INFORMS, vol. 65(5), pages 1322-1342, October.
    8. 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.
    9. Negin Golrezaei & Hamid Nazerzadeh & Paat Rusmevichientong, 2014. "Real-Time Optimization of Personalized Assortments," Management Science, INFORMS, vol. 60(6), pages 1532-1551, June.
    10. 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.
    11. 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.
    12. ,, 1999. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 15(3), pages 427-432, June.
    13. Alice Paul & Jacob Feldman & James Mario Davis, 2018. "Assortment Optimization and Pricing Under a Nonparametric Tree Choice Model," Manufacturing & Service Operations Management, INFORMS, vol. 20(3), pages 550-565, July.
    14. Guillermo Gallego & Huseyin Topaloglu, 2014. "Constrained Assortment Optimization for the Nested Logit Model," Management Science, INFORMS, vol. 60(10), pages 2583-2601, October.
    15. Srikanth Jagabathula & Paat Rusmevichientong, 2017. "Nonparametric Joint Assortment and Price Choice Model," Management Science, INFORMS, vol. 63(9), pages 3128-3145, September.
    16. Guillermo Gallego & Richard Ratliff & Sergey Shebalov, 2015. "A General Attraction Model and Sales-Based Linear Program for Network Revenue Management Under Customer Choice," Operations Research, INFORMS, vol. 63(1), pages 212-232, February.
    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. ,, 1999. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 15(4), pages 629-637, August.
    19. ,, 1999. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 15(5), pages 777-788, October.
    20. 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.
    21. 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.
    22. 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.
    23. 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.
    24. ,, 1999. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 15(1), pages 151-160, February.
    25. Nathan Kallus & Madeleine Udell, 2020. "Dynamic Assortment Personalization in High Dimensions," Operations Research, INFORMS, vol. 68(4), pages 1020-1037, July.
    26. 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.
    27. 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.
    28. Fernando Bernstein & A. Gürhan Kök & Lei Xie, 2015. "Dynamic Assortment Customization with Limited Inventories," Manufacturing & Service Operations Management, INFORMS, vol. 17(4), pages 538-553, October.
    29. 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.
    30. Ruxian Wang & Zizhuo Wang, 2017. "Consumer Choice Models with Endogenous Network Effects," Management Science, INFORMS, vol. 63(11), pages 3944-3960, November.
    31. Gilles Laurent & Eric Lapersonne & Jean-Jacques Le Goff, 1995. "Consideration sets of size one: An empirical investigation of automobile purchases," Post-Print hal-00458463, HAL.
    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. Qi Feng & J. George Shanthikumar & Mengying Xue, 2022. "Consumer Choice Models and Estimation: A Review and Extension," Production and Operations Management, Production and Operations Management Society, vol. 31(2), pages 847-867, February.
    2. Qi Feng & J. George Shanthikumar, 2022. "Developing operations management data analytics," Production and Operations Management, Production and Operations Management Society, vol. 31(12), pages 4544-4557, December.
    3. Schlicher, Loe & Lurkin, Virginie, 2024. "Fighting pickpocketing using a choice-based resource allocation model," European Journal of Operational Research, Elsevier, vol. 315(2), pages 580-595.
    4. Julia Heger & Robert Klein, 2024. "Assortment optimization: a systematic literature review," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 46(4), pages 1099-1161, December.

    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. Julia Heger & Robert Klein, 2024. "Assortment optimization: a systematic literature review," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 46(4), pages 1099-1161, December.
    2. 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.
    3. Kris Johnson Ferreira & Joel Goh, 2021. "Assortment Rotation and the Value of Concealment," Management Science, INFORMS, vol. 67(3), pages 1489-1507, March.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Çö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.
    9. Çö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).
    10. Wang, Mengmeng & Zhang, Xun & Li, Xiaolong, 2023. "Multiple-purchase choice model: estimation and optimization," International Journal of Production Economics, Elsevier, vol. 265(C).
    11. Jacob Feldman & Alice Paul & Huseyin Topaloglu, 2019. "Technical Note—Assortment Optimization with Small Consideration Sets," Operations Research, INFORMS, vol. 67(5), pages 1283-1299, September.
    12. 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.
    13. Shipra Agrawal & Vashist Avadhanula & Vineet Goyal & Assaf Zeevi, 2019. "MNL-Bandit: A Dynamic Learning Approach to Assortment Selection," Operations Research, INFORMS, vol. 67(5), pages 1453-1485, September.
    14. Dimitris Bertsimas & Velibor V. Mišić, 2019. "Exact First-Choice Product Line Optimization," Operations Research, INFORMS, vol. 67(3), pages 651-670, May.
    15. 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.
    16. 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.
    17. Çö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.
    18. Flores, Alvaro & Berbeglia, Gerardo & Van Hentenryck, Pascal, 2019. "Assortment optimization under the Sequential Multinomial Logit Model," European Journal of Operational Research, Elsevier, vol. 273(3), pages 1052-1064.
    19. 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.
    20. Ali Aouad & Jacob Feldman & Danny Segev, 2023. "The Exponomial Choice Model for Assortment Optimization: An Alternative to the MNL Model?," Management Science, INFORMS, vol. 69(5), pages 2814-2832, May.

    More about this item

    Statistics

    Access and download statistics

    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:bla:popmgt:v:30:y:2021:i:7:p:2122-2142. 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: Wiley Content Delivery (email available below). General contact details of provider: http://onlinelibrary.wiley.com/journal/10.1111/(ISSN)1937-5956 .

    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.