Scalable Algorithms for Discrete Choice Modeling and Assortment Optimization

Assortment Optimization aims at identifying a set of products to be offered to customers, so as to maximize a firm's expected revenue. One of the major challenges in solving this task stems from the fact that products demands are interdependent, due to so-called substitution and halo effects. Hence, most often a discrete choice model must be learned from historical data, in order to capture the buying behaviors of customers faced with discrete sets of alternatives. Such model can then be used as a predictive subroutine for optimizing assortment decisions. In practice, tackling the assortment optimization problem thus requires finding the right trade-off between i) flexibility of the choice model, which should be general enough to approximate well the buying behavior of customers, and ii) tractability of the optimization problem one must solve to find the revenue-maximizing set of products. In this thesis, we deal with both the predictive and prescriptive aspects of such trade-off, providing effective estimation procedures for general discrete choice models and scalable algorithms to identify high-revenue assortments. First, we propose an effective procedure to optimize assortments for scenarios in which each product is associated to a certain cost representing, e.g., the stocking or shipping one, which the firm has to pay for offering that product. We assume customers choose according to a Multinomial Logit model. This problem is NP-hard. Exact solution methods have been shown to be computationally impractical, thus motivating a number of approximate approaches. Notably, our results indicate that it is possible to identify the optimal assortment in a fraction of a second, on average, even on large-scale instances. We further show how to adapt our approach to the case in which assortments must satisfy a constraint on the maximum number of available products. Second, we propose a partially-ranked choice model that generalizes fully-ranked choice models by assuming that customers may form strict preferences only among few relevant products, while being “indifferent” among the others. Such model can theoretically approximate any model belonging to the Random Utility Maximization family, and allows to capture any pattern of substitution among products. We then provide an estimation procedure based on column generation to effectively identify customer behaviors consistent with historical sales data. Further, we show how to optimize assortment decisions based on such model. Finally, we extend our partially-ranked choice model and estimation framework to capture buying behaviors, such as halo effects, which cannot be explained by any of the models belonging to the Random Utility Maximization family. Our results on a real-world grocery sales dataset show that accounting for this type of choice behaviors allows to significantly boost predictive accuracy.