Greedy-Like Algorithms for Dynamic Assortment Planning Under Multinomial Logit Preferences

Aouad, A, Levi, R and Segev, D (2018) Greedy-Like Algorithms for Dynamic Assortment Planning Under Multinomial Logit Preferences. Operations Research, 66 (5). pp. 1321-1345. ISSN 0030-364X OPEN ACCESS


We study the joint assortment planning and inventory management problem, where stock-out events elicit dynamic substitution effects, described by the multinomial logit (MNL) choice model. Special cases of this setting have been extensively studied in recent literature, notably the static assortment planning problem. Nevertheless, to our knowledge, the general formulation is not known to admit efficient algorithms with analytical performance guarantees before this work, and most of its computational aspects are still wide open. In this paper, we devise what is, to our knowledge, the first provably good approximation algorithm for dynamic assortment planning under the MNL model. We derive a constant-factor guarantee for a broad class of demand distributions that satisfy the increasing failure rate property. Our algorithm relies on a combination of greedy procedures, where stocking decisions are restricted to specific classes of products and the objective function takes modified forms. We demonstrate that our approach substantially outperforms state-of-the-art heuristic methods in terms of performance and speed, leading to an average revenue gain of 4% to 12% in computational experiments. In the course of establishing our main result, we develop new algorithmic ideas that may be of independent interest. These include weaker notions of submodularity and monotonicity, shown sufficient to obtain constant-factor worst-case guarantees, despite using noisy estimates of the objective function

More Details

Item Type: Article
Subject Areas: Management Science and Operations
Additional Information:

© 2018 INFORMS

Finalist in the 2016 INFORMS Nicholson Prize

Date Deposited: 30 May 2019 10:49
Date of first compliant deposit: 07 Oct 2019
Subjects: Inventory control
Ancillary printing and publishing industries
Last Modified: 23 Apr 2024 00:43

Export and Share


Accepted Version - Text


View details on Dimensions' website

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item