Optimal algorithms for assortment selection under ranking-based consumer choice models

A retailer's product selection decisions are largely driven by her assumptions on how consumers make choices. We use a ranking-based consumer choice model to represent consumer preferences: every customer has a ranking of the potential products in the category and purchases his highest ranked product (if any) offered in the assortment. We consider four practically motivated special cases of this model, namely the one-way substitution, the locational choice, the outtree, and the intree preference models, and study the retailer's product selection problem when products have different price and cost parameters. We assume that the retailer incurs a fixed carrying cost per product offered, a goodwill penalty for each customer who does not purchase his first choice and a lost sale penalty for each customer who does not find an acceptable product to buy. For the first three models, we obtain efficient solution methods that simplify to either a shortest path method or a dynamic program. For the fourth model, we construct an effective algorithm and show numerically that, in practice, it is much faster than enumeration. We also obtain valuable insights on thestructure of the optimal assortment