商品組合最佳化決策問題是當今零售業與線下、線上廣告投放業務等多個管理實務領域中業者須面對的一大決策難題。其核心在於面對有限共享資源與庫存、補貨限制的前提下選擇適當的商品上架組合，以確保顧客到訪後之預期銷售收益最大化。其中業者須考慮商品庫存狀況與到訪顧客偏好等多個現實條件以確保商品銷售的如期收益。本研究建構一在有限銷售期的架構下，以混合多項羅吉特模型（Mixed Multinomial Logit Model, MMNL）呈現顧客偏好的異質性與隨機性，估計在不同到訪顧客下商品被購買的機率，並將此機率分布作為期望目標收益與資源約束的參考依據。
為解決MMNL模型帶來的非線性與可能的非凸性性質致使在傳統線性最佳化求值方法下尋找全域最佳解的高複雜度與高時間成本，本研究參考Brown & Zhang (2023)研究中的流體鬆弛方法建構相容之流體鬆弛模型：藉由放寬決策變數的二元限制，將原問題轉化為相對可處理的連續近似，以在確保求出的最佳近似值效果的同時加快求值過程。此方法保持原模型的決策品質並兼顧運算效率，不僅擁有既有文獻的理論作為近似解有效性的依據，且在實務層面上能提供可實作的決策框架。
綜上所述，本研究主要建立於Brown & Zhang (2023)所提出之流體鬆弛架構，並針對商品組合問題進行延伸，其主要貢獻如下：一、將原本固定購買機率之動態資源配置模型，延伸至考慮 MMNL 顧客異質性的動態商品組合問題，其中明確納入庫存與資源限制；二、將流體鬆弛方法導入 MMNL 商品組合問題，重新建構適用於本研究問題之流體模型與策略轉換流程，並提供可計算的上界與可操作之策略生成機制；三、透過數值實驗驗證此架構在 MMNL 商品組合問題上的可行性，並分析其策略特性與績效，致力於在多期環境下提升整體銷售期的總預期收益。

A Fluid Relaxation Framework for Dynamic Assortment Strategies under Heterogeneous Customer Preferences

Po-Han Lin
Advisor: Dr. Ya-Tang Chuang
Department of Industrial and Information Management, College of Management, National Cheng Kung University

Dynamic assortment optimization is an important decision problem in retailing, e-commerce, and advertising, where firms must determine which products to offer under limited inventory and display resources. This study develops a finite-horizon dynamic assortment model in which customer choice is represented by a Mixed Multinomial Logit (MMNL) model, while finite inventories and assortment-capacity constraints are explicitly considered. Because exact dynamic programming suffers from rapidly expanding state and action spaces, a fluid relaxation framework is introduced to transform the discrete problem into a continuous approximation and provide an upper bound on optimal expected revenue. Two implementable policies, randomized and deterministic, are constructed from the fluid solution. Numerical experiments show that the fluid upper bound differs from the exact dynamic programming optimum by only about 0.04% in the benchmark setting. Both fluid-based policies achieve revenues close to the optimal policy, and the deterministic policy provides particularly stable performance. These findings indicate that fluid relaxation can serve as an effective approximation framework for dynamic assortment decisions involving heterogeneous customers, limited inventories, and shared display resources.

Adelman, D., & Mersereau, A. J. (2008). Relaxations of weakly coupled stochastic dynamic programs. Operations Research, 56(3), 712–727.
Agrawal, S., Avadhanula, V., Goyal, V., & Zeevi, A. (2019). MNL-bandit: A dynamic learning approach to assortment selection. Operations Research, 67(5), 1453–1485.
Aouad, A., Levi, R., & Segev, D. (2018a). Approximation algorithms for dynamic assortment optimization models. Mathematics of Operations Research, 44(2). Published online: 6 Sep 2018.
Aouad, A., Levi, R., & Segev, D. (2018b). Greedy-like algorithms for dynamic assortment planning under multinomial logit preferences. Operations Research, 66(5), 1321–1345.
Bernstein, F., Kök, A. G., & Xie, L. (2015). Dynamic assortment customization with limited inventories. Manufacturing & Service Operations Management, 17(4), 533–545.
Bertsimas, D., & Mišić, V. V. (2016). Decomposable Markov decision processes: A fluid optimization approach. Operations Research, 64(6), 1463–1480.
Blanchet, J., Gallego, G., & Goyal, V. (2016). A Markov chain approximation to choice modeling. Operations Research, 64(4), 886–905.
Bront, J. J. M., Méndez-Dı́az, I., & Vulcano, G. (2009). A column generation algorithm for choice-based network revenue management. Operations Research, 57(3), 769–784.
Brown, D. B., & Zhang, J. (2023). Fluid policies, reoptimization, and performance guarantees in dynamic resource allocation. Operations Research. Published online: 11 Dec 2023.
Caro, F., & Gallien, J. (2007). Dynamic assortment with demand learning for seasonal consumer goods. Management Science, 53(2), 276–292.
Davis, J. M., Gallego, G., & Topaloglu, H. (2014). Assortment optimization under variants of the nested logit model. Operations Research, 62(2), 250–273.
de Albéniz, V. M., & Kunnumkal, S. (2022). A model for integrated inventory and assortment planning. Management Science, 68(7), 4839–4862.
Désir, A., Goyal, V., & Zhang, J. (2022). Technical note—capacitated assortment optimization: Hardness and approximation. Operations Research, 70(2), 660–671.
Feldman, J., & Topaloglu, H. (2015). Bounding optimal expected revenues for assortment optimization under mixtures of multinomial logits. Production and Operations Management, 24(10), 1593–1608.
Geunes, J., & Su, Y. (2020). Single-period assortment and stock-level decisions for dual sales channels with capacity limits and uncertain demand. International Journal of Production Research, 58(18), 5579–5600.
Jasin, S., Lyu, C., Najafi, S., & Zhang, H. (2024). Assortment optimization with multi-item basket purchase under multivariate MNL model. Manufacturing & Service Operations Management, 26(1), 102–119.
Kunnumkal, S., & Talluri, K. (2019). Choice network revenue management based on new tractable approximations. Transportation Science, 53(6), 1591–1608.
Ma, W. (2023). When is assortment optimization optimal? Management Science, 69(4), 1895–1913.
Mahajan, S., & Van Ryzin, G. (2001). Stocking retail assortments under dynamic consumer substitution. Operations research, 49(3), 334–351.
McFadden, D. (1974). Conditional logit analysis of qualitative choice behavior. Frontiers in Econometrics, (pp. 105–142).
McFadden, D., & Train, K. (2000). Mixed MNL models for discrete response. Journal of Applied Econometrics, 15(5), 447–470.
Rooderkerk, R. P., van Heerde, H. J., & Bijmolt, T. H. A. (2013). Optimizing retail assortments. Marketing Science, 32(5), 699–715.
Rusmevichientong, P., Shmoys, D., Tong, C., & Topaloglu, H. (2014). Assortment optimization under the multinomial logit model with random choice parameters. Production and Operations Management, 23(11), 2023–2039.
Sajadi, S. J., & Ahmadi, A. (2022). An integrated optimization model and metaheuristics for assortment planning, shelf space allocation, and inventory management of perishable products: A real application. PLOS ONE, 17(3), e0264186.
Sen, A., Atamturk, A., & Kaminsky, P. (2017). A conic integer programming approach to constrained assortment optimization under the mixed multinomial logit model. arXiv preprint arXiv:1705.09040.
Simchi-Levi, D., Sun, R., & Wang, X. (2023). Technical note—online matching with Bayesian rewards. Operations Research, 73(1), 296–310.
Ulu, C., Honhon, D., & Alptekinoglu, A. (2012). Learning consumer tastes through dynamic assortments. Operations Research, 60(4), 865–878.
Yan, P., Miao, S., & Xie, H. (2025). Assortment optimization under the generalized Markov chain choice model. SSRN Working Paper.
Yang, Y., Wu, C.-H., & Chen, Y.-J. (2023). Managing consumer retention via pricing and switching cost under discrete mixed multinomial logit demand. HKUST Business School Research Paper No. 2023-113.
Zhang, H., Zhang, Q., Wu, F., & Yang, Y. (2024). Dynamic assortment selection under inventory and limited switches constraints. IEEE Transactions on Knowledge and Data Engineering, 36(3), 728–740.