An Innovative Optimization and Computational Framework for Assortment Problems Under Consider-Then-Rank Choice Models

越来越多的行业已经认识到，在不同的客户群面前，寻找各种选定的替代方案(如产品或服务)以最大限度地提高总收入、利润或福利，这一挑战已经被越来越多的行业认识到是成功的主要战略和运营驱动因素。这类一般性的问题抓住了基本的规划挑战，例如：“电子零售商应该为每个搜索查询显示什么产品选择？”，“实体零售商如何确定每个商店的产品分类？”以及“一个中央规划者应该提供什么服务，以最大限度地提高不同种族人口的社会福利？”尽管人们越来越认识到分类决策的重要性，支持分类决策的可用商业软件工具也越来越多，但许多公司(如果不是大多数公司)仍然难以做出有效的、以数据为导向的分类决策。一个关键的挑战是如何准确有效地捕获客户选择模型，即客户对备选方案的偏好。随着“大数据”可用性的不断提高，我们可以构建更细粒度的模型来分析客户的选择方式。不幸的是，这些相同的细粒度选择模型导致了极具挑战性的分类优化模型。这个项目的目标是开发一种统一的方法来研究关于客户如何做出购买选择的有案可查的行为特征与相应分类优化问题的计算可处理性之间的关系。该项目旨在促进对各种分类模型学习和计算局限性的理论理解，以及开发有效的计算方案来解决大规模的实际分类问题。该项目旨在开发一个创新的基于优化和计算动态规划的框架来研究和解决考虑然后等级选择模型下的分类优化问题，这在营销学和心理学中已经得到了广泛的研究。在考虑优先选择模型下，假设顾客分两个阶段进行选择。首先，他们应用各种启发式方法来建立他们愿意考虑的产品的考虑集，然后他们在考虑集内排名。在给定分类的情况下，假设客户从他们考虑的集合中选择最喜欢的产品。如果成功，将开发的框架将允许研究关于启发式客户的不同假设如何应用以形成他们各自的考虑集和排名，从而影响所产生的分类问题的计算可处理性。这将通过对底层动态程序的创新图形描述来完成，该图形描述产生了动态编程子问题的“最小”列举。理论分析将集中在对数子问题的严格界定上。此外，“最小”枚举技术将被用来开发有效的实用算法来解决大规模的实际分类问题。与业界合作伙伴的合作将被用来增强本研究项目的实际影响，并丰富学生的课堂体验。

The challenge of finding an assortment of selected alternatives (e.g., products or services) that maximize the total revenue, profit or welfare in the face of heterogeneous customer segments, who have different preferences across alternatives, has been recognized by an increasing number of industries to be a major strategic and operational driver of success. This generic class of problems captures fundamental planning challenges, such as: "What selection of products should an e-retailer display for each search query?", "How does a brick and mortar retailer determine the product assortment in each store?" and "What services should a central planner offer to maximize the social welfare of heterogeneous population?" In spite of increased awareness to the importance of assortment decisions, and an increasing number of available commercial software tools to support them, many if not most firms, still struggle to make effective and data-driven assortment decisions. A key challenge is how to accurately and effectively capture a customer choice model, namely the preferences of customers across alternatives. The increasing availability of `big' data allows us to build more granular models of how customers choose. Unfortunately, these same granular choice models give rise to assortment optimization models that are extremely challenging to solve. The goal of this project is to develop a unified approach to study the relationship between documented behavioral features regarding how customers make purchasing choices, and the computational tractability of the corresponding assortment optimization problems. The grant aims to significantly advance the theoretical understanding of the learning and computational limitations of various assortment models, and the development of effective computational schemes to solve practical assortment problems at large scale.This project aims to develop an innovative optimization and computational dynamic-programming based framework to study and solve assortment optimization problems under consider-then-rank choice models, which have been studied extensively in marketing and psychology. Under consider-than-rank choice models, customers are assumed to make choices in two phases. First they apply various heuristics to establish a consideration set of products they are willing to consider, and then they rank within the consideration set. Given an assortment, customers are assumed to choose the most preferred product available from within their consideration set. If successful, the framework to be developed would allow the study of how different assumptions regarding the heuristics customers apply to form their respective consideration sets and rankings affect the computational tractability of the resulting assortment problems. This will be done via an innovative graphical description of the underlying dynamic program that gives rise to "minimal" enumeration of dynamic programming sub-problems. The theoretical analysis will focus on developing tight bounds on the number sub-problems. Moreover, the "minimal" enumeration techniques will be leveraged to develop efficient practical algorithms to solve large scale practical assortment problems. Collaboration with industry partners will be used to enhance the practical impact of this research project, and to enrich the classroom experience for students.