×

An enhanced conic reformulation for capacity-constrained assortment optimization under the mixture of multinomial logit model. (English) Zbl 07910606

Summary: In this work, we study the conic quadratic mixed-integer formulation for assortment optimization problem under the mixture of multinomial logit (MMNL) model. The MMNL model generalizes the widely studied multinomial logit choice model and can approximate any random utility model with an arbitrary additive error. An important operational decision problem in revenue management is assortment optimization problem, which aims to find a subset of products to make available to customers that maximizes the expected revenue of the retailer. It is known that assortment optimization problem under the MMNL model is NP-hard and inapproximable within any constant performance guarantee. Commonly used methods for solving such problem are heuristical approaches or customized combinatorial optimization approaches. In the meanwhile, studies related to global optimization approaches are relatively scarce. We propose an enhanced conic quadratic mixed-integer formulation for solving assortment optimization problem under the MMNL model with a higher computational efficiency. Furthermore, we conduct extensive numerical experiments to demonstrate that the proposed reformulation significantly outperforms the existing conic reformulations for assortment optimization under the MMNL model.

MSC:

90B99 Operations research and management science
90C20 Quadratic programming
90C27 Combinatorial optimization
90C32 Fractional programming
Full Text: DOI

References:

[1] Şen, A.; Atamtürk, A.; Kaminsky, P., Technical note-a conic integer optimization approach to the constrained assortment problem under the mixed multinomial logit model, Oper. Res., 66, 4, 994-1003, 2018 · Zbl 1455.90109 · doi:10.1287/opre.2017.1703
[2] Xie, T.; Ge, D., A tractable discrete fractional programming: Application to constrained assortment optimization, J. Comb. Optim., 36, 400-415, 2018 · Zbl 1392.90113 · doi:10.1007/s10878-018-0302-x
[3] Chen, R.; Jiang, H., Capacitated assortment and price optimization under the nested logit model, J. Global Optim., 77, 895-918, 2020 · Zbl 1447.91062 · doi:10.1007/s10898-020-00896-x
[4] Nip, K.; Wang, Z.; Wang, Z., Assortment optimization under a single transition choice model, Prod. Oper. Manag., 30, 7, 2122-2142, 2021 · doi:10.1111/poms.13358
[5] Jin, Q.; Lin, JY; Zhou, SX, Price discounts and personalized product assortments under multinomial logit choice model: A robust approach, IISE Trans., 53, 4, 453-471, 2021 · doi:10.1080/24725854.2020.1798036
[6] Luce, RD, Individual Choice Behavior: A Theoretical Analysis, 1959, New York: Wiley, New York · Zbl 0093.31708
[7] McFadden, D.; Zarembka, P., Conditional logit analysis of qualitative choice behaviour, Frontiers in Econometrics, 105-142, 1973, New York: Academic Press, New York
[8] Talluri, K.; van Ryzin, G., Revenue management under a general discrete choice model of consumer behavior, Manag. Sci., 50, 1, 15-33, 2004 · Zbl 1168.91427 · doi:10.1287/mnsc.1030.0147
[9] Kök, A.; Fisher, M., Demand estimation and assortment optimization under substitution: Methodology and application, Oper. Res., 55, 6, 1001-1021, 2007 · Zbl 1167.91386 · doi:10.1287/opre.1070.0409
[10] Wang, R.; Wang, Z., Consumer choice models with endogenous network effects, Manag. Sci., 63, 11, 3944-3960, 2017 · doi:10.1287/mnsc.2016.2520
[11] Sahin, O.; Wang, R., The impact of consumer search cost on assortment planning and pricing, Manag. Sci., 64, 8, 3649-3666, 2017
[12] Chen, X., Li, Y., Mao, J.: A nearly instance optimal algorithm for top-k ranking under the multinomial logit model. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, pp. 2504-2522. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2018) · Zbl 1403.68182
[13] Davis, JM; Gallego, G.; Topaloglu, H., Assortment optimization under variants of the nested logit model, Oper. Res., 62, 2, 250-273, 2014 · Zbl 1295.90076 · doi:10.1287/opre.2014.1256
[14] McFadden, D.; Train, K., Mixed MNL models for discrete response, J. Appl. Economet., 15, 5, 447-470, 2000 · doi:10.1002/1099-1255(200009/10)15:5<447::AID-JAE570>3.0.CO;2-1
[15] Rusmevichientong, P.; Shen, ZJM; Shmoys, DB, Dynamic assortment optimization with a multinomial logit choice model and capacity constraint, Oper. Res., 58, 6, 1666-1680, 2010 · Zbl 1228.90170 · doi:10.1287/opre.1100.0866
[16] Feldman, J.; Topaloglu, H., Capacity constraints across nests in assortment optimization under the nested logit model, Oper. Res., 63, 4, 812-822, 2015 · Zbl 1329.90087 · doi:10.1287/opre.2015.1383
[17] Gallego, G.; Topaloglu, H., Constrained assortment optimization for the nested logit model, Manage. Sci., 60, 10, 2583-2601, 2014 · doi:10.1287/mnsc.2014.1931
[18] Désir, A., Goyal, V., Zhang, J.: Capacitated assortment optimization: Hardness and approximation. Oper. Res. (2021). Forthcoming
[19] Mahajan, S.; van Ryzin, G., Stocking retail assortments under dynamic consumer substitution, Oper. Res., 49, 3, 334-351, 2001 · Zbl 1163.90339 · doi:10.1287/opre.49.3.334.11210
[20] Gallego, G.; Topaloglu, H., Revenue Management and Pricing Analytics, 2019, Berlin: Springer, Berlin · doi:10.1007/978-1-4939-9606-3
[21] Rusmevichientong, P.; Shmoys, D.; Tong, C.; Topaloglu, H., Assortment optimization under the multinomial logit model with random choice parameters, Prod. Oper. Manag., 23, 11, 2023-2039, 2014 · doi:10.1111/poms.12191
[22] Bront, JJM; 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 · doi:10.1287/opre.1080.0567
[23] Méndez-Díaz, I.; Miranda-Bront, JJ; Vulcano, G.; Zabala, P., A branch-and-cut algorithm for the latent-class logit assortment problem, Discret. Appl. Math., 164, 246-263, 2014 · Zbl 1326.90041 · doi:10.1016/j.dam.2012.03.003
[24] Feldman, J.; Topaloglu, H., Bounding optimal expected revenues for assortment optimization under mixtures of multinomial logits, Prod. Oper. Manag., 24, 10, 1598-1620, 2015 · doi:10.1111/poms.12365
[25] McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems. Math. Program. 10(1), 147-175 (1976) · Zbl 0349.90100
[26] Grant, M., Boyd, S.: The CVX users’ guide, release 2.2. http://cvxr.com/cvx/doc/CVX.pdf (2020)
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.