  


NearOptimal Algorithms for Capacity Constrained Assortment Optimization
Antoine Desir (ad2918columbia.edu) Abstract: Assortment optimization is an important problem that arises in many practical applications such as retailing and online advertising. In an assortment optimization problem, the goal is to select a subset of items that maximizes the expected revenue in the presence of the substitution behavior of consumers specified by a choice model. In this paper, we consider the capacity constrained version of the assortment optimization problem under several choice models including Multinomial logit (MNL), Nested Logit (NL) and the mixture of Multinomial logit (MMNL) models. The goal is to select a revenue maximizing subset of items with total weight or capacity at most a given bound. We present a fully polynomial time approximation scheme (FPTAS) for these models when the number of mixtures or nests is constant. Our FPTAS uses ideas similar to the FPTAS for the knapsack problem. The running time of our algorithm depends exponentially on the number of mixtures in the MMNL model. We show that surprisingly the exponential dependence on the number of mixtures is necessary for any nearoptimal algorithm for the MMNL choice model. In particular, we show that there is no algorithm with running time polynomial in the number of items, n and mixtures, K that obtains an approximation better than O(1/K1−δ) for any δ > 0 for even the unconstrained assortment optimization over a general MMNL model. Our reduction provides a procedure to construct a natural family of hard benchmark instances for the assortment optimization problem over MMNL that may be of independent interest. These instances are quite analogous to the consideration set based models (Jagabathula and Rusmevichientong (2014)) where the consideration set arises from a graphical model. We also present some special cases of MMNL and NL models where we can obtain an FPTAS with a polynomial dependence on the number of mixtures. Keywords: Assortment Optimization, FPTAS, Approximation Algorithm Category 1: Applications  OR and Management Sciences Category 2: Combinatorial Optimization Category 3: Combinatorial Optimization (Approximation Algorithms ) Citation: Department of Industrial Engineering and Operations Research, Columbia University, January 2015 Download: [PDF] Entry Submitted: 05/13/2013 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  