An Exact Method for (Constrained) Assortment Optimization Problems with Product Costs

We study the problem of optimizing assortment decisions in the presence of product-specific costs when customers choose according to a multinomial logit model. This problem is NP-hard, and approximate solutions methods have been proposed in the literature to obtain both lower and upper bounds in a tractable manner. We propose the first exact solution method for this problem and show that provably optimal assortments of instances with up to 1,000 products can be found, on average, in about 2/10 of a second. In particular, we propose a bounding procedure to enhance an approximation method originally proposed by Feldman and Topaloglu and provide tight lower and upper bounds at a fraction of a second. We show how these bounds can be used to effectively identify an optimal assortment. We also describe how to adapt our approach to handle cardinality or space/resource capacity constraints on the assortment as well as assortment optimization under a mixed-multinomial logit model. In both cases, our solution method provides significant computational boosts compared with exact methods from the literature.