  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 one thousand products
can be found, on average, in about two tenths of a second. In particular, we
propose a bounding procedure based on the approximation method of Feldman and
Topaloglu (2015a) to provide tight lower and upper bounds at a fraction of
their computing times. 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
to exact methods from the literature.
