Approximation Algorithms for Dynamic Assortment Optimization Models
© 2018 INFORMS 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 notor...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/135083 |
| _version_ | 1826212833028734976 |
|---|---|
| author | Aouad, Ali Levi, Retsef Segev, Danny |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Aouad, Ali Levi, Retsef Segev, Danny |
| author_sort | Aouad, Ali |
| collection | MIT |
| description | © 2018 INFORMS 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. |
| first_indexed | 2024-09-23T15:38:37Z |
| format | Article |
| id | mit-1721.1/135083 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:38:37Z |
| publishDate | 2021 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1350832023-12-18T20:02:12Z Approximation Algorithms for Dynamic Assortment Optimization Models Aouad, Ali Levi, Retsef Segev, Danny Sloan School of Management © 2018 INFORMS 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. 2021-10-27T20:10:38Z 2021-10-27T20:10:38Z 2019 2021-04-13T13:23:15Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/135083 en 10.1287/MOOR.2018.0933 Mathematics of Operations Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) SSRN |
| spellingShingle | Aouad, Ali Levi, Retsef Segev, Danny Approximation Algorithms for Dynamic Assortment Optimization Models |
| title | Approximation Algorithms for Dynamic Assortment Optimization Models |
| title_full | Approximation Algorithms for Dynamic Assortment Optimization Models |
| title_fullStr | Approximation Algorithms for Dynamic Assortment Optimization Models |
| title_full_unstemmed | Approximation Algorithms for Dynamic Assortment Optimization Models |
| title_short | Approximation Algorithms for Dynamic Assortment Optimization Models |
| title_sort | approximation algorithms for dynamic assortment optimization models |
| url | https://hdl.handle.net/1721.1/135083 |
| work_keys_str_mv | AT aouadali approximationalgorithmsfordynamicassortmentoptimizationmodels AT leviretsef approximationalgorithmsfordynamicassortmentoptimizationmodels AT segevdanny approximationalgorithmsfordynamicassortmentoptimizationmodels |