Technical Note—New Bounds for Cardinality-Constrained Assortment Optimization Under the Nested Logit Model

We consider the cardinality-constrained assortment optimization problem under the nested logit model where there is a constraint that limits the number of products that can be offered within each nest. The problem is known to be intractable if the nest dissimilarity parameters are larger than one or there is a no-purchase alternative within each nest. Although these conditions often come up in practice, the existing solution approaches cannot handle them. We propose a solution method to obtain heuristic assortments with provable worst-case performance guarantees that hold even when the nest dissimilarity parameters are larger than one or there is a no-purchase alternative within each nest. We obtain a tractable upper bound that can be used to assess the practical performance of our solution approach. Computational experiments indicate that the heuristic assortments perform very well, with optimality gaps being smaller than 1% on average. Our analysis also provides sharper performance bounds for the unconstrained assortment optimization problem under the nested logit model.