MSPA-MCS: Collaborative Research: Algorithms for Near-Optimal Multistage Decision-Making under Uncertainty: Online Learning from Historical Samples

MSPA-MCS：协作研究：不确定性下近乎最优的多阶段决策算法：历史样本在线学习

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

Collaborative Research: Algorithms for Near-Optimal Multistage Decision-Making under Uncertainty: Online Learning from Historical SamplesAbstractRecent advances in information technologies enable firms to collect and maintain huge amounts of raw data regarding demand, sales history and other aspects of their operations. However, little is known about using this data effectively and efficiently within their decision-making processes, which can often be modeled as multi-stage stochastic optimization problems. In many application domains, such as supply chain management and revenue management, these give rise to complex problems, where the decision in each stage must be made under uncertainty about the future evolution of an underlying stochastic process. Traditional approaches to these problems assume that the uncertainty is defined through explicitly specified probability distributions that are known a priori; the knowledge of these distributions is crucial to the development of the corresponding optimization algorithms. However, in most practical situations the exact distributions are not known, and only historical data is available. This research project aims to develop a general-purpose sampling-based algorithmic framework for these models that, unlike traditional approaches, uses the raw historical data as the source of samples. First, we plan to develop sampling-based algorithmic approaches to approximately solve complex stochastic dynamic programming formulations, the dominant paradigm used for these problems. Second, we focus on sampling-based algorithms for models that combine optimization and learning simultaneously. A common theme between these two research thrusts, and a central feature of our research project, is the development of explicit quantitative analysis of the performance of our algorithms that provide guarantees on the sample-size needed to assure a specified error bound with respect to optimal solution for the true underlying probability distribution.Consider a firm like Amazon that provides millions of different items to customers throughout the US. Clearly, it is important for the company to have the inventory that its customers want, since if an item is out of stock, then the customer is likely to purchase the item from elsewhere. On the other hand, maintaining extra inventory for undesired items has the disadvantage of tying up capital in obtaining them, using significant resources in warehousing this supply, which is further compounded by the risk of perishability and obsolesce. If one had a crystal ball with which one could predict the future, then the company could know how many requests there will be, day by day, for each of the items it sells, and therefore know how much of what should be on hand in each of its warehouses. Instead, one can model the future probabilistically (similar to what a weather forecaster does when saying that there is a 40% chance of showers tomorrow), and then one can cast the problem of making the optimal decisions for these inventory levels as a problem of maximizing the average profit that can be obtained (or minimizing the average costs incurred), where the notion of average is with respect to the randomness used to model our inability to exactly predict the future. This project has the goal of using past historical data as a means for modeling the predictions for future data, and then designing algorithms that produce provably near-optimal decisions based on this approximation. This type of decision-making in the face of uncertainty arises in a wide range of application domains, from selling different classes of airlinetickets for a portfolio of flight legs to manufacturing a suite of products that rely on overlapping sets of components. This project focuses on settings in which there are multiple stages of decision-making that must be made in the face of an evolving view of the predictions of futurerequirements. The aim is to provide tools to automate such decision-making with algorithms that are guaranteed to quickly produce reliable solutions.

协作研究：不确定性下的近乎最佳多阶段决策的算法：信息技术的历史样品中的在线学习，使公司能够收集和维护有关需求，销售历史和运营其他方面的大量原始数据。 但是，对于在决策过程中有效，有效地使用这些数据知之甚少，这些数据通常可以建模为多阶段随机优化问题。 在许多应用领域（例如供应链管理和收入管理）中，这些领域引起了复杂的问题，在每个阶段的决定都必须在不确定性的情况下对基本随机过程的未来演变做出。 这些问题的传统方法认为，不确定性是通过已知的明确指定的概率分布来定义的。这些分布的知识对于相应优化算法的发展至关重要。但是，在大多数实际情况下，确切的分布尚不清楚，只有历史数据可用。 该研究项目旨在为这些模型开发基于通用抽样的算法框架，与传统方法不同，它使用原始的历史数据作为样品来源。首先，我们计划开发基于抽样的算法方法，以近似求解复杂的随机动态编程公式，即用于这些问题的主要范式。 其次，我们专注于基于抽样的算法，用于同时结合优化和学习的模型。 这两个研究的推力与我们研究项目的主要特征之间的一个共同主题是对我们的算法的性能进行明确的定量分析，这些算法的性能为确保确保针对真正的潜在概率分布的最佳解决方案所需的样本尺寸保证提供了保证。为您提供了整个客户的数百万美元的公司。显然，对于公司而言，重要的是要拥有其客户想要的库存，因为如果某物品没有库存，则客户可能会从其他地方购买商品。另一方面，维持不希望物品的额外库存是缺点，因为它使用大量资源来仓库来获得资本，这在仓库中，这是由于易腐性和过时的风险而进一步加剧了这一供应。 如果一个人拥有一个可以预测未来的水晶球，那么该公司可以知道，每天都有多少要求其出售的物品，因此知道每个仓库中应该有多少东西。取而代之的是，人们可以概率地对未来进行建模（类似于天气预报员在说明天有40％的阵雨的可能性40％），然后可以提出一个问题的问题，即为这些库存水平做出最佳决策，即最大化可以获得的平均利润的最大利润（或最小化平均成本的概念），在这种情况下，可以预测平均能力，以确切地使用该型号，以确切地使用我们的未来，以确切地模型。该项目的目标是使用过去的历史数据作为对未来数据进行预测进行建模的手段，然后设计基于此近似值的算法，这些算法可产生近乎最佳的决策。 面对不确定性的这种决策类型是在各种应用程序域中出现的，从出售不同类别的飞机票组合的飞行腿投资组合到制造一套依靠重叠组件的产品。该项目的重点是在面对不断发展的未来预测的观点时必须做出多个决策阶段的设置。目的是提供工具以使用算法来自动化此类决策，这些算法可以迅速产生可靠的解决方案。