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

考虑然后排序选择模型下分类问题的创新优化和计算框架

• 批准号: 1537536
• 负责人: Retsef Levi
• 金额: $ 30万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1537536&HistoricalAwards=false
• 关键词: Innovative; Optimization; Computational; Framework; Assortment

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.

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