Capacity Constraints Across Nests in Assortment Optimization Under the Nested Logit Model

We consider assortment optimization problems when customers choose according to the nested logit model and there is a capacity constraint limiting the total capacity consumption of all products offered in all nests. When each product consumes one unit of capacity, our capacity constraint limits the cardinality of the offered assortment. For the cardinality constrained case, we develop an efficient algorithm to compute the optimal assortment. When the capacity consumption of each product is arbitrary, we give an algorithm to obtain a 4-approximate solution. We show that we can compute an upper bound on the optimal expected revenue for an individual problem instance by solving a linear program. In our numerical experiments, we consider problem instances involving products with arbitrary capacity consumptions. Comparing the expected revenues from the assortments obtained by our 4-approximation algorithm with the upper bounds on the optimal expected revenues, our numerical results indicate that the 4-approximation algorithm performs quite well, yielding less than 2% optimality gap on average.