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
Abstract:
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.)