  


An algorithm for assortment optimization under parametric discrete choice models
Tien Mai(maitien86gmail.com) Abstract: This work concerns the assortment optimization problem that refers to selecting a subset of items that maximizes the expected revenue in the presence of the substitution behavior of consumers specified by a parametric choice model. The key challenge lies in the computational difficulty of finding the best subset solution, which often requires exhaustive search. The literature on constrained assortment optimization lacks a practically efficient method that is general to deal with different types of parametric choice models (e.g., the multinomial logit, mixed logit or general multivariate extreme value models). In this paper, we propose a new approach that allows to address this issue. The idea is that, under a general parametric choice model, we formulate the problem into a binary nonlinear programming model, and use an iterative algorithm to find a binary solution. At each iteration, we propose a way to approximate the objective (expected revenue) by a linear function, and a polynomialtime algorithm to find a candidate solution using this approximate function. We also develop a greedy local search algorithm to further improve the solutions. We test our algorithm on instances of different sizes under various parametric choice model structures and show that our algorithm dominates existing exact and heuristic approaches in the literature, in terms of solution quality and computing cost. Keywords: parametric choice model, assortment optimization, binary trust region, greedy local search Category 1: Applications  OR and Management Sciences Category 2: Integer Programming (01 Programming ) Citation: BenAkiva M (1973)The structure of travel demand models. Ph.D. thesis, MIT. BenAkiva M, Bierlaire M (1999) Discrete choice methods and their applications to shortterm travel decisions. Hall R, ed., Handbook of Transportation Science, 5–34 (Kluwer). BenAkiva M, Lerman SR (1985) Discrete Choice Analysis: Theory and Application to Travel Demand(MIT Press, Cambridge, Massachusetts). Bertsimas D, Misic V (2017) Exact firstchoice product line optimization. Forthcoming in Operations Research. Bront JJM, M endezDıaz I, Vulcano G (2009) A column generation algorithm for choicebased network revenue management. Operations Research 57(3):769–784. Daly A, Bierlaire M (2006) A general and operational representation of generalised extreme value models. Transportation Research Part B 40(4):285 – 305. Davis JM, Gallego G, Topaloglu H (2014) Assortment optimization under variants of the nested logit model. Operations Research 62(2):250–273. Desir A, Goyal V (2014) Nearoptimal algorithms for capacity constrained assortment optimization. Availableat SSRN 2543309. Feige U, Mirrokni VS, Vondrak J (2011) Maximizing nonmonotone submodular functions. SIAM Journalon Computing 40(4):1133–1153. Fischetti M, Lodi A (2003) Local branching.Mathematical programming 98(13):23–47. Fosgerau M, McFadden M, Bierlaire M (2013) Choice probability generating functions.Journal of Choice Modelling 8:118. Gallego G, Topaloglu H (2014) Constrained assortment optimization for the nested logit model. ManagementScience 60(10):2583–2601. Jagabathula S (2014) Assortment optimization under general choice. Available at SSRN 2512831.Jena SD, Lodi A, Palmer H (2017) Partiallyranked choice models for datadriven assortment optimization. Technical Report DS4DM2017011, Canada Excellence Research Chair. Koppelman F, Wen CH (2000) The paired combinatorial logit model: properties, estimation and application. Transportation Research Part B 34:75–89. Li G, Rusmevichientong P, Topaloglu H (2015) The dlevel nested logit model: Assortment and price optimization problems. Operations Research 63(2):325–342. Liu Q, Van Ryzin G (2008) On the choicebased linear programming model for network revenue management. Manufacturing & Service Operations Management 10(2):288–310. Mai T, Frejinger E, Fosgerau M, Bastin F (2017) A dynamic programming approach for quickly estimating large networkbased MEV models.Transportation Research Part B: Methodological 98:179–197. McFadden D (1978) Modelling the choice of residential location. Karlqvist A, Lundqvist L, Snickars F,Weibull J, eds., Spatial Interaction Theory and Residential Location, 75–96 (Amsterdam: NorthHolland). McFadden D, Train K (2000) Mixed MNL models for discrete response.Journal of applied Econometrics 447–470. MendezDıaz I, MirandaBront JJ, Vulcano G, Zabala P (2010) A branchandcut algorithm for the latent class logit assortment problem. Electronic Notes in Discrete Mathematics 36:383–390. Nocedal J, Wright SJ (2006) Numerical Optimization(New York, NY, USA: Springer), 2nd edition. Rusmevichientong P, Shen ZJM, Shmoys DB (2010) Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations research 58(6):1666–1680. 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. Rusmevichientong P, Topaloglu H (2012) Robust assortment optimization in revenue management under the multinomial logit choice model.Operations Research 60(4):865–882. Small KA (1987) A discrete choice model for ordered alternatives. Econometrica 55(2):409–424. Talluri K, Van Ryzin G (2004) Revenue management under a general discrete choice model of consumer behavior. Management Science 50(1):15–33. Train K (2003) Discrete Choice Methods with Simulation (Cambridge University Press). van Ryzin G, Vulcano G (2014) A market discovery algorithm to estimate a general class of nonparametric choice models. Management Science 61(2):281–300. van Ryzin G, Vulcano G (2017) An expectationmaximization method to estimate a rankbased choice model of demand.Operations Research 65(2):396–407. Vovsha P, Bekhor S (1998) Linknested logit model of route choice Overcoming route overlapping problem. Transportation Research Record 1645:133–142. Wu TH (1997) A note on a global approach for general 0–1 fractional programming.European Journal of Operational Research 101(1):220–223. Download: [PDF] Entry Submitted: 04/17/2020 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  