Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2012-13 > Constrained Assortment Optimization for the Nested Logit Model
How to contact us


LSE 10 logo master_6

Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE


Enquiries: dom.events@lse.ac.uk 


Follow us online



Constrained Assortment Optimization for the Nested Logit Model

Wednesday 5 December 2012, 4.30pm-6.00pm
2.08, New Academic Building

Professor Guillermo Gallego

Liu Family Professor, Department of Industrial Engineering & Operations Research
Columbia University

Personal Profile


We study assortment problems under variants of the nested logit (NL) choice model. The objective is to find an assortment that maximizes the expected revenue per customer. We show that the problem is polynomially solvable for the standard NL model (dissimilarity parameters less than one and customers purchasing from the selected nest). Relaxing either assumption renders the problem NP-hard. For the hard cases, we develop parsimonious collections of candidate assortments with worst-case performance guarantees. We then study the problem with a cardinality, space, or parent-child constraint for the standard model. We show that an optimal assortment under cardinality or parent-child constraints can be obtained by solving a linear program. We show that the problem is NP-hard under space constraints and provide a 2-approximation algorithm for this case. This approximation algorithm also provides a performance guarantee of 1 / (1- ε) when the space requirement for each product is at most a fraction ε of the space availability in each nest. We also develop a linear program to obtain an assortment with an arbitrarily good performance guarantee under space constraints, whose size increases with the performance guarantee. (Joint work with J. Davis and H. Topaloglu.)


        Guillermo Gallego