Assortment Planning under the Multinomial Logit Model with Totally Unimodular Constraint Structures

Abstract

We consider constrained assortment problems assuming that customers select according to the multinomial logit model (MNL). The objective is to find an assortment that maximizes the expected revenue per customer and satisfies a set of totally unimodular constraints. We show that this fractional binary problem can be solved as an equivalent linear program. We use this result to solve five classes of practical assortment optimization and pricing models under MNL, including (1) assortment models with various bounds on the cardinality of the assortment, (2) assortment models where we need to decide the display location of the selected products, (3) pricing models with a finite menu of possible prices, (4) quality consistent pricing models where the prices of the products have to follow a specified quality ordering, (5) assortment models with precedence constraints. We show that all of these classes of problems can be solved as linear programs. In some instances, constraints can be combined as long as total unimodularity is preserved. In addition, we show how the results extend to a larger class of attraction choice models that avoid some of the shortcomings of MNL. The problem of selecting assortments to maximize expected profits or expected welfare arises in a variety of industries ranging from transportation and retailing to travel and leisure. There is a