From predictive choice models to near-optimal algorithms

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2017.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Cataloged from student-submitted PDF version of thesis.Includes bibliographical references (pages 251-256).Finding optimal product offerings is a fundamental operational issue in modern retailing, exemplified by the development of recommendation systems and decision support tools. The challenge is that designing an accurate predictive choice model generally comes at the detriment of efficient algorithms, which can prescribe near-optimal decisions. This thesis attempts to resolve this disconnect in the context of assortment and inventory optimization, through theoretical and empirical investigation. First, we tightly characterize the complexity of general nonparametric assortment optimization problems. We reveal connections to maximum independent set and combinatorial pricing problems, allowing to derive strong inapproximability bounds. We devise simple algorithms that achieve essentially best-possible factors with respect to the price ratio, size of customers' consideration sets, etc. Second, we develop a novel tractable approach to choice modeling, in the vein of nonparametric models, by leveraging documented assumptions on the customers' consider-then-choose behavior. We show that the assortment optimization problem can be cast as a dynamic program, that exploits the properties of a bi-partite graph representation to perform a state space collapse. Surprisingly, this exact algorithm is provably and practically efficient under common consider-then-choose assumptions. On the estimation front, we show that a critical step of standard nonparametric estimation methods (rank aggregation) can be solved in polynomial time in settings of interest, contrary to general nonparametric models. Predictive experiments on a large purchase panel dataset show significant improvements against common benchmarks. Third, we turn our attention to joint assortment optimization and inventory management problems under dynamic customer choice substitution. Prior to our work, little was known about these optimization models, which are intractable using modern discrete optimization solvers. Using probabilistic analysis, we unravel hidden structural properties, such as weak notions of submodularity. Building on these findings, we develop efficient and yet conceptually-simple approximation algorithms for common parametric and nonparametric choice models. Among notable results, we provide best-possible approximations under general nonparametric choice models (up to lower-order terms), and develop the first constant-factor approximation under the popular Multinomial Logit model. In synthetic experiments vis-a-vis existing heuristics, our approach is an order of magnitude faster in several cases and increases revenue by 6% to 16%.by Ali Aouad.Ph. D