Technical Note—Capacitated Assortment Optimization: Hardness and Approximation

References

• Aouad A, Farias V, Levi R, Segev D (2018) The approximability of assortment optimization under ranking preferences. Oper. Res. 66(6):1661–1669.Link, Google Scholar
• Ben-Akiva M, Lerman S (1985) Discrete Choice Analysis: Theory and Application to Travel Demand, vol. 9 (MIT Press, Cambridge, MA).Google Scholar
• Blanchet J, Gallego G, Goyal V (2016) A Markov chain approximation to choice modeling. Oper. Res. 64(4):886–905.Link, Google Scholar
• Bront JJM, Méndez-Díaz I, Vulcano G (2009) A column generation algorithm for choice-based network revenue management. Oper. Res. 57(3):769–784.Link, Google Scholar
• Chen R, Jiang H (2019) Capacitated assortment and price optimization under the multilevel nested logit model. Oper. Res. Lett. 47(1):30–35.Crossref, Google Scholar
• Chen R, Jiang H (2020) Capacitated assortment and price optimization under the nested logit model. J. Global Optim. 77:895–918.Crossref, Google Scholar
• Davis JM, Gallego G, Topaloglu H (2014) Assortment optimization under variants of the nested logit model. Oper. Res. 62(2):250–273.Link, Google Scholar
• Désir A, Goyal V, Segev D, Ye C (2020) Capacity constrained assortment optimization under the Markov chain based choice model. Management Sci. 66(2):698–721.Link, Google Scholar
• Feldman JB, Topaloglu H (2015) Capacity constraints across nests in assortment optimization under the nested logit model. Oper. Res. 63(4):812–822.Link, Google Scholar
• Feldman JB, Topaloglu H (2017) Revenue management under the Markov chain choice model. Oper. Res. 65(5):1322–1342.Link, Google Scholar
• Frieze AM, Clarke MRB (1984) Approximation algorithms for the m-dimensional 0–1 knapsack problem: Worst-case and probabilistic analyses. Eur. J. Oper. Res. 15(1):100–109.Crossref, Google Scholar
• Gallego G, Topaloglu H (2014) Constrained assortment optimization for the nested logit model. Management Sci. 60(10):2583–2601.Link, Google Scholar
• Gallego G, Topaloglu H (2019) Revenue Management and Pricing Analytics (Springer, New York).Crossref, Google Scholar
• Jagabathula S, Rusmevichientong P (2016) A nonparametric joint assortment and price choice model. Management Sci. 63(9):3128–3145.Link, Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Complexity of Computer Computations (Springer, New York), 85–103.Crossref, Google Scholar
• Li G, Rusmevichientong P, Topaloglu H (2015) The d-level nested logit model: Assortment and price optimization problems. Oper. Res. 62(2):325–342.Link, Google Scholar
• Luce RD (1959) Individual Choice Behavior: A Theoretical Analysis (Wiley, Hoboken, NJ).Google Scholar
• McFadden D (1978) Modeling the choice of residential location. Transportation Res. Rec. 673:72–77.Google Scholar
• McFadden D, Train K (2000) Mixed MNL models for discrete response. J. Appl. Econometrics 15(5):447–470.Crossref, Google Scholar
• Méndez-Díaz I, Miranda-Bront JJ, Vulcano G, Zabala P (2014) A branch-and-cut algorithm for the latent-class logit assortment problem. Discrete Appl. Math. 164:246–263.Crossref, Google Scholar
• Mika S, Gallego G, Paat R, Topaloglu H, Davis J (2021) Revenue-utility tradeoff in assortment optimization under the multinomial logit model with totally unimodular constraints. Management Sci. 67(5):2845–2869.Google Scholar
• Mittal S, Schulz AS (2013) A general framework for designing approximation schemes for combinatorial optimization problems with many objectives combined into one. Oper. Res. 61(2):386–397.Link, Google Scholar
• Papadimitriou CH, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. Proc. 41st Annual IEEE Symp. Foundations Comput. Sci. (IEEE, New York), 86–92.Google Scholar
• Plackett RL (1975) The analysis of permutations. J. R. Stat. Soc. Ser. C. Appl. Stat. 24(2):193–202.Crossref, Google Scholar
• Rusmevichientong P, Max Shen ZJ, Shmoys DB (2009) A PTAS for capacitated sum-of-ratios optimization. Oper. Res. Lett. 37(4):230–238.Crossref, Google Scholar
• Rusmevichientong P, Shen Z-JM, Shmoys DB (2010) Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Oper. Res. 58(6):1666–1680.Link, Google Scholar
• Rusmevichientong P, Shmoys D, Tong C, Topaloglu H (2014) Assortment optimization under the multinomial logit model with random choice parameters. Production Oper. Management 23(11):2023–2039.Crossref, Google Scholar
• Talluri K, Van Ryzin G (2004) Revenue management under a general discrete choice model of consumer behavior. Management Sci. 50(1):15–33.Link, Google Scholar
• Wang Y, Shen Z-JM (2017) Joint optimization of capacitated assortment and pricing problem under the tree logit model. Technical report, University of California, Berkeley.Google Scholar
• Williams HCWL (1977) On the formation of travel demand models and economic evaluation measures of user benefit. Environ. Planning A 3(9):285–344.Crossref, Google Scholar
• Zhang D, Cooper WL (2005) Revenue management for parallel flights with customer-choice behavior. Oper. Res. 53(3):415–431.Link, Google Scholar