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

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

• 批准号: 0732196
• 负责人: Paat Rusmevichientong
• 金额: $ 17.27万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0732196&HistoricalAwards=false
• 关键词: 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% 的可能性会下阵雨），然后我们可以将针对这些库存水平做出最佳决策的问题转化为以下问题：最大化可以获得的平均利润（或最小化产生的平均成本），其中平均的概念是关于用于模拟我们无法准确预测未来的随机性。该项目的目标是使用过去的历史数据作为对未来数据的预测进行建模的手段，然后设计算法，根据该近似值生成可证明的接近最优的决策。 这种面对不确定性的决策出现在广泛的应用领域中，从销售不同类别的机票组合的航班到制造依赖于重叠组件集的一套产品。该项目的重点是在面对未来需求预测的不断变化的观点时必须做出多个决策阶段的环境。目的是提供工具来自动执行此类决策，并使用保证快速生成可靠解决方案的算法。