Assortment optimization under the multinomial logit model with product synergies. (English) Zbl 1476.91082
Summary: In synergistic assortment optimization, a product’s attractiveness changes as a function of which other products are offered. We represent synergy structure graphically. Vertices denote products. An edge denotes synergy between two products, which increases their attractiveness when both are offered. Finding an assortment to maximize retailer’s expected profit is NP-hard in general. We present efficient algorithms when the graph is a path, a tree, or has low treewidth. We give a linear program to recover the optimal assortment for paths.
MSC:
| 91B42 | Consumer behavior, demand theory |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 90C09 | Boolean programming |
References:
| [1] | Blanchet, J.; Gallego, G.; Goyal, V., A markov chain approximation to choice modeling, Oper. Res., 64, 4, 886-905 (2016) · Zbl 1348.90614 |
| [2] | Bodlaender, H. L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 6, 1305-1317 (1996) · Zbl 0864.68074 |
| [3] | Bodlaender, H. L.; Gilbert, J. R.; Hafsteinsson, H.; Kloks, T., Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, J. Algorithms, 18, 2, 238-255 (1995) · Zbl 0818.68118 |
| [4] | Brandstadt, A.; Spinrad, J. P., Graph Classes: a Survey, Vol. 3, 167-185 (1999), SIAM · Zbl 0919.05001 |
| [5] | Bront, J. J.M.; Méndez-Díaz, I.; Vulcano, G., A column generation algorithm for choice-based network revenue management, Oper. Res., 57, 3, 769-784 (2009) · Zbl 1233.90061 |
| [6] | A. Désir, V. Goyal, J. Zhang, Near-optimal algorithms for capacity constrained assortment optimization, Available at SSRN 2543309, 2014. |
| [7] | Feldman, J.; Paul, A.; Topaloglu, H., Technical note—assortment optimization with small consideration sets, Oper. Res. (2019) · Zbl 1444.90011 |
| [8] | Feldman, J.; Topaloglu, H., Revenue management under the markov chain choice model, Oper. Res., 65, 5, 1322-1342 (2017) · Zbl 1411.91497 |
| [9] | G. Feng, X. Li, Z. Wang, Analysis of discrete choice models: A welfare-based framework, arXiv preprint arXiv:1503.01854, 2015. |
| [10] | Gallego, G.; Ratliff, R.; Shebalov, S., A general attraction model and sales-based linear program for network revenue management under customer choice, Oper. Res., 63, 1, 212-232 (2014) · Zbl 1422.91446 |
| [11] | Hanks, A. S.; Just, D. R.; Wansink, B., Trigger foods: The influence of “irrelevant” alternatives in school lunchrooms, Agric. Resour. Econ. Rev., 41, 1, 114-123 (2012) |
| [12] | Honhon, D.; Jonnalagedda, S.; Pan, X. A., Optimal algorithms for assortment selection under ranking-based consumer choice models, Manuf. Serv. Oper. Manag., 14, 2, 279-289 (2012) |
| [13] | Kochenberger, G.; Hao, J.-K.; Glover, F.; Lewis, M.; Lü, Z.; Wang, H.; Wang, Y., The unconstrained binary quadratic programming problem: a survey, J. Comb. Optim., 28, 1, 58-81 (2014) · Zbl 1303.90066 |
| [14] | Li, H.; Huh, W. T., Pricing multiple products with the multinomial logit and nested logit models: Concavity and implications, Manuf. Serv. Oper. Manag., 13, 4, 549-563 (2011) |
| [15] | Luce, R. D., Individual Choice Behavior a Theoretical Analysis (1959), John Wiley and sons · Zbl 0093.31708 |
| [16] | Mahajan, S.; Van Ryzin, G., Stocking retail assortments under dynamic consumer substitution, Oper. Res., 49, 3, 334-351 (2001) · Zbl 1163.90339 |
| [17] | McFadden, D.; Train, K., Mixed MNL models for discrete response, J. Appl. Économ., 15, 5, 447-470 (2000) |
| [18] | McFadden, D., Conditional Logit Analysis of Qualitative Choice Behavior (1973), Institute of Urban and Regional Development, University of California |
| [19] | Padberg, M., The boolean quadric polytope: some characteristics, facets and relatives, Math. Program., 45, 1, 139-172 (1989) · Zbl 0675.90056 |
| [20] | Radzik, T., Fractional combinatorial optimization, (Handbook of Combinatorial Optimization (1998), Springer), 429-478 · Zbl 0934.90065 |
| [21] | Rusmevichientong, P.; Shmoys, D. B.; Tong, C.; Topaloglu, H., Assortment optimization under the multinomial logit model with random choice parameters, Prod. Oper. Manag., 23, 11, 2023-2039 (2014) |
| [22] | Simonson, I., Choice based on reasons: The case of attraction and compromise effects, J. Consum. Res., 16, 2, 158-174 (1989) |
| [23] | Simonson, I., The effect of product assortment on buyer preferences, J. Retail, 75, 3, 347-370 (1999) |
| [24] | Simonson, I.; Tversky, A., Choice in context: Tradeoff contrast and extremeness aversion, J. Mark. Res., 29, 3, 281-295 (1992) |
| [25] | Thurstone, L. L., A law of comparative judgment., Psychol. Rev., 34, 4, 273 (1927) |
| [26] | Train, K., Discrete Choice Methods with Simulation (2003), Cambridge university press · Zbl 1047.62098 |
| [27] | Wald, J. A.; Colbourn, C. J., Steiner trees, partial 2-trees, and minimum IFI networks, Networks, 13, 2, 159-167 (1983) · Zbl 0529.68036 |
| [28] | Williamson, D. P.; Shmoys, D. B., The Design of Approximation Algorithms, 257-279 (2011), Cambridge university press · Zbl 1219.90004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
