An algorithm for assortment optimization under parametric discrete choice models
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 polynomial-time 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 (0-1 Programming )
Citation: Ben-Akiva M (1973)The structure of travel demand models. Ph.D. thesis, MIT. Ben-Akiva M, Bierlaire M (1999) Discrete choice methods and their applications to short-term travel decisions. Hall R, ed., Handbook of Transportation Science, 5–34 (Kluwer). Ben-Akiva M, Lerman SR (1985) Discrete Choice Analysis: Theory and Application to Travel Demand(MIT Press, Cambridge, Massachusetts). Bertsimas D, Misic V (2017) Exact first-choice product line optimization. Forthcoming in Operations Research. Bront JJM, M endez-Dıaz I, Vulcano G (2009) A column generation algorithm for choice-based 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) Near-optimal algorithms for capacity constrained assortment optimization. Availableat SSRN 2543309. Feige U, Mirrokni VS, Vondrak J (2011) Maximizing non-monotone submodular functions. SIAM Journalon Computing 40(4):1133–1153. Fischetti M, Lodi A (2003) Local branching.Mathematical programming 98(1-3):23–47. Fosgerau M, McFadden M, Bierlaire M (2013) Choice probability generating functions.Journal of Choice Modelling 8:1-18. 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) Partially-ranked choice models for data-driven assortment optimization. Technical Report DS4DM-2017-011, 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 d-level nested logit model: Assortment and price optimization problems. Operations Research 63(2):325–342. Liu Q, Van Ryzin G (2008) On the choice-based 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 network-based 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: North-Holland). McFadden D, Train K (2000) Mixed MNL models for discrete response.Journal of applied Econometrics 447–470. Mendez-Dıaz I, Miranda-Bront JJ, Vulcano G, Zabala P (2010) A branch-and-cut 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 expectation-maximization method to estimate a rank-based choice model of demand.Operations Research 65(2):396–407. Vovsha P, Bekhor S (1998) Link-nested 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.
Entry Submitted: 04/17/2020
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|