III: SMALL: Scalable In-Database Prescriptive Analytics for Dynamic Environments

金融、交通、制造和医疗等广泛领域的决策者通常需要在给定一组约束和目标的情况下得出最优决策；也就是说，他们需要使用“说明性分析”。这类约束优化问题的传统解决方案虽然产生了数十亿美元，但通常是特定于应用程序的、复杂的、难以被非优化专家使用的，并且不能泛化。此外，通常的工作流程需要在数据库与预测建模和优化工具之间进行缓慢、繁琐且容易出错的数据移动。所有这些问题都因规模空前的现代数据密集型优化问题而加剧。该项目的目标是显著提高数据库内规范分析的基础技术，以提供无缝的、独立于域的、易于使用和可扩展的决策工具，这些工具由数据通常驻留的数据库系统提供支持。具体地说，该项目旨在通过处理动态环境的能力来增强数据库中对受限优化问题的支持。这是因为决策环境通常是高度动态的，具有不确定和不断变化的数据，决策问题可能不是精确定义的，并且随着时间的推移而变化。研究人员将提供新的模型和评估算法，在规模上处理不确定和不断变化的数据和问题变体。将优化与数据库技术相结合的改进方法将有助于降低非优化领域专家使用说明性分析的障碍，从而扩大这些规划和管理技术对社会的好处。具体而言，该项目将扩展现有方法，通过在数据库内支持大型随机整数线性规划(ILP)来处理大规模数据不确定性，这些ILP由用户使用SQL数据库查询语言的扩展指定为“随机包查询(SPQ)”。这样的查询选择满足每个元组和全局约束的元组的最优集合(包)。为了支持SPQ的高效处理，需要开发具有精度保证的快速近似查询求值算法。调查人员接下来将开发快速、增量和渐进式的查询评估技术，以实现快速的假设分析和规划。他们将首先关注确定性数据，并研究当底层数据或查询稍有变化时允许增量维护包结果的策略。研究团队将研究几种途径，例如重新设计ILP解算器，以利用包查询的特殊结构，以加快初始查询评估的中间步骤，并促进增量重新优化。然后，这些结果将被利用和扩展，以支持对不确定数据的增量评估。该项目将调查数据不确定性如何影响为确定性数据设计的增量评估战略，以及如何处理在随机环境中引起变化的其他因素，如不确定项目的概率分布随时间的变化。对于后者，要考虑的技术包括通过随机搜索更新包解决方案，通过随机敏感度分析评估查询和数据变化的影响，以及使用预计算技术加速增量SPQ处理。该项目的最后阶段将把上述算法和扩展集成到一个成熟的系统中，该系统配备有处理大规模不确定数据的能力，能够采用增量评估策略来适应数据和查询变化。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Decision makers in a broad range of domains, such as finance, transportation, manufacturing, and healthcare, often need to derive optimal decisions given a set of constraints and objectives; that is, they need to employ "prescriptive analytics". Traditional solutions to such constrained optimization problems, while having generated billions of dollars, are typically application-specific, complex, hard to use by non-optimization-experts, and do not generalize. Further, the usual workflow requires slow, cumbersome, and error-prone data movement between a database and predictive-modeling and optimization tools. All of these problems are exacerbated by the unprecedented size of modern data-intensive optimization problems. The goal of this project is to significantly advance the technology underlying in-database prescriptive analytics to provide seamless domain-independent, easy-to-use, and scalable decision-making tools powered in the database system where the data typically reside. Specifically, the project aims to augment prior work on in-database support for constrained optimization problems with capabilities to handle dynamic environments. This is because decision environments are typically highly dynamic, with data that is uncertain and evolving, and decision problems that may be not precisely defined and changing over time. The investigators will contribute new models and evaluation algorithms that handle uncertain and evolving data and problem variants at scale. The improved methods for integrating optimization with database technology will help lower the barriers to use of prescriptive analytics by domain experts who are not experts in optimization, thereby amplifying the benefits of these planning and management techniques to society.In detail, the project will extend prior methods to handle data uncertainty at scale via in-database support for large-scale stochastic integer linear programs (ILPs) that are specified by the user as "stochastic package queries" (SPQs) using an extension of the SQL database query language. Such a query selects an optimal set ("package") of tuples that satisfy both per-tuple and global constraints. Supporting efficient processing of SPQs entails development of fast approximate query evaluation algorithms with accuracy guarantees. The investigators will next develop fast incremental and progressive query evaluation techniques to allow for rapid what-if analysis and planning. They will first focus on deterministic data and investigate strategies to allow for incremental maintenance of a package result when the underlying data or query changes slightly. The team of researchers will investigate several pathways, such as reengineering the ILP solvers to exploit the special structure of package queries in order to speed up intermediate steps in the initial query evaluation and also facilitate incremental re-optimization. These results will then be leveraged and extended to support incremental evaluation over uncertain data. The project will investigate both how data uncertainty impacts the incremental evaluation strategies designed for deterministic data and how to handle additional factors that instigate change in the stochastic setting, such as changes over time to the probability distribution of uncertain items. For the latter, techniques to be considered include updating a package solution via stochastic search, evaluating the effect of query and data changes via stochastic sensitivity analysis, and speeding up incremental SPQ processing using pre-computation techniques. The final stage of the project will integrate the foregoing algorithms and extensions into a full-fledged system equipped to handle large-scale uncertain data, with the ability to employ incremental evaluation strategies to adapt to data and query changes.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.