IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v291y2021i3p830-845.html
   My bibliography  Save this article

An exact method for assortment optimization under the nested logit model

Author

Listed:
  • Alfandari, Laurent
  • Hassanzadeh, Alborz
  • Ljubić, Ivana

Abstract

We study the problem of finding an optimal assortment of products maximizing the expected revenue, in which customer preferences are modeled using a nested logit choice model. This problem is known to be polynomially solvable in a specific case and NP-hard otherwise, with only approximation algorithms existing in the literature. We provide an exact general method that embeds a tailored Branch-and-Bound algorithm into a fractional programming framework. In contrast to the existing literature, in which assumptions are imposed on either the structure of nests or the combination and characteristics of products, no assumptions on the input data are imposed. Although our approach is not polynomial in input size, it can solve the most general problem setting for large-size instances. We show that the fractional programming scheme’s parameterized subproblem, a highly non-linear binary optimization problem, is decomposable by nests, which is the primary advantage of the approach. To solve the subproblem for each nest, we propose a two-stage approach. In the first stage, we fix a large set of variables based on the single-nest subproblem’s newly-derived structural properties. This can significantly reduce the problem size. In the second stage, we design a tailored Branch-and-Bound algorithm with problem-specific upper bounds. Numerical results show that the approach is able to solve assortment instances with five nests and with up to 5000 products per nest. The most challenging instances for our approach are those with a mix of nests’ dissimilarity parameters, where some of them are smaller than one and others are greater than one.

Suggested Citation

  • Alfandari, Laurent & Hassanzadeh, Alborz & Ljubić, Ivana, 2021. "An exact method for assortment optimization under the nested logit model," European Journal of Operational Research, Elsevier, vol. 291(3), pages 830-845.
  • Handle: RePEc:eee:ejores:v:291:y:2021:i:3:p:830-845
    DOI: 10.1016/j.ejor.2020.12.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720310171
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2020.12.007?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

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


    Cited by:

    1. Shaoning Han & Andrés Gómez & Oleg A. Prokopyev, 2022. "Fractional 0–1 programming and submodularity," Journal of Global Optimization, Springer, vol. 84(1), pages 77-93, September.
    2. 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.
    3. Agrawal, Priyank & Tulabandhula, Theja & Avadhanula, Vashist, 2023. "A tractable online learning algorithm for the multinomial logit contextual bandit," European Journal of Operational Research, Elsevier, vol. 310(2), pages 737-750.
    4. Méndez-Vogel, Gonzalo & Marianov, Vladimir & Lüer-Villagra, Armin, 2023. "The follower competitive facility location problem under the nested logit choice rule," European Journal of Operational Research, Elsevier, vol. 310(2), pages 834-846.

    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:eee:ejores:v:291:y:2021:i:3:p:830-845. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.