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

金融、交通、制造和医疗等广泛领域的决策者通常需要在给定一组约束和目标的情况下得出最佳决策;也就是说，他们需要采用“规范分析”。这种约束优化问题的传统解决方案虽然已经产生了数十亿美元，但通常是特定于应用的、复杂的、难以由非优化专家使用的，并且不能推广。此外，通常的工作流需要在数据库与预测建模和优化工具之间进行缓慢、繁琐且容易出错的数据移动。所有这些问题都因现代数据密集型优化问题的空前规模而加剧。该项目的目标是显著推进数据库内规范性分析的基础技术，以提供无缝的独立于域、易于使用和可扩展的决策工具，这些工具在数据通常驻留的数据库系统中提供支持。具体来说，该项目的目的是增加以前的工作在数据库中的支持约束优化问题的能力，以处理动态环境。这是因为决策环境通常是高度动态的，数据是不确定的和不断变化的，决策问题可能没有精确定义，并随着时间的推移而变化。研究人员将贡献新的模型和评估算法，以处理大规模的不确定和不断变化的数据和问题变体。将优化与数据库技术相结合的改进方法将有助于降低非优化专家的领域专家使用规范分析的障碍，从而扩大这些规划和管理技术对社会的好处。该项目将通过对大规模随机整数线性规划（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.