Scalable Algorithms for Discrete Choice Modeling and Assortment Optimization

L'optimisation de l'assortiment vise à identifier un ensemble de produits à offrir aux clients, de manière à maximiser le revenu attendu d'une entreprise. L'un des principaux défis à relever pour résoudre cette tâche provient du fait que les demandes de produits sont interdépendantes, en raison des effets dits de substitution et de halo. Par conséquent un modèle de choix discret doit être appris à partir des données recensées, afin de capturer les comportements d'achat des clients confrontés à des ensembles discrets d'alternatives. Un tel modèle peut ensuite être utilisé comme une sous-routine prédictive pour optimiser les décisions d'assortiment. En pratique, la résolution d'un problème d'optimisation de l'assortiment nécessite donc de trouver le bon compromis entre i) la flexibilité du modèle de choix, qui doit être suffisamment général pour bien représenter le comportement d'achat des clients, et ii) la difficulté de résolution du problème d'optimisation pour trouver l'ensemble de produits qui maximise les revenus. Dans cette thèse, nous traitons à la fois les aspects prédictifs et prescriptifs de ce compromis, en fournissant des procédures d'estimation efficaces pour des modèles de choix discrets généraux et des algorithmes pour identifier des assortiments à revenu élevé. Tout d'abord, nous proposons une procédure efficace pour optimiser les assortiments pour des scénarios dans lesquels chaque produit est associé à un certain coût que l'entreprise doit payer pour offrir ce produit. Nous supposons que les clients choisissent selon un modèle Multinomial Logit. Ce problème est NP-hard. Néanmoins, nos résultats indiquent qu'il est possible d'identifier l'assortiment optimal en une fraction de seconde, en moyenne, même pour des instances avec mille produits. Nous montrons également comment adapter notre approche au cas où les assortiments doivent satisfaire une contrainte sur le nombre maximum de produits disponibles. Deuxièmement, nous proposons un modèle de choix partiellement rangé, qui généralise les modèles de choix entièrement rangé en supposant que les clients forment des préférences strictes uniquement parmi quelques produits pertinents, tout en étant “indifférents” parmi les autres. Ce modèle permet de capturer tout effet de substitution entre les produits. Nous proposons ensuite une procédure d'estimation basée sur la génération de colonnes pour identifier efficacement les comportements des clients en fonction des données historiques de vente. De plus, nous montrons comment optimiser les décisions d'assortiment basées sur un tel modèle. Enfin, nous étendons notre modèle de choix partiellement rangé et notre cadre d'estimation pour capturer les comportements d'achat, tels que les effets de halo, qui ne peuvent être expliqués par aucun des modèles appartenant à la famille de la maximisation de l'utilité aléatoire. Nos résultats sur un ensemble de données de ventes d'épicerie dans le monde réel montrent que la prise en compte de ce type de comportements de choix permet d'augmenter de manière significative la précision prédictive.

Abstract

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.