EAGER: In-Database Prescriptive Analytics under Uncertainty

规定性分析，特别是约束优化，是广泛领域（包括金融、交通、制造和医疗保健）决策制定的核心，也应用于科学研究。通常，决策者依赖于特定于应用程序的解决方案来建模和解决这些问题。这样的解决方案往往很复杂，不能一概而论。此外，通常的工作流程要求从数据库中提取数据，然后重新格式化并输入到单独的优化包中，之后必须重新格式化输出并插入到数据库中；这个过程缓慢、繁琐且容易出错。最后，现代数据密集型优化问题的规模是前所未有的。需要一种独立于领域、声明性和可伸缩的方法，并由与这些问题相关的数据通常驻留的系统（数据库）提供支持和支持。然后，建模变得不那么临时，并且从数据准备到解决和结果探索的整体优化过程变得更加高效。理想的数据管理功能——如一致性、持久性、容错性、访问控制和数据集成能力——“免费”成为系统的组成部分。该项目将开发算法和系统，为在实践中经常遇到的大规模不确定数据的规定性分析应用程序提供通用的数据库内支持。具体来说，该项目将开发SQL关系查询语言的扩展，以允许规范“随机包查询”，这是一类数据库查询，它选择满足单个元组和全局约束的元组的最优集合（“包”）。这样的查询对应于随机整数线性程序。新的解决方案算法将专注于由数据不确定性和大数据量引起的扩展挑战。该系统将在可能的情况下提供精确的解决方案，否则将提供基于蒙特卡罗的可扩展的解决方案，并提供严格的近似保证。该项目将从根本上重新设计先前的PackageBuilder系统，用于确定性包查询，结合概率数据库的技术，创建一个完整的端到端系统。该项目将通过应用程序影响广泛的领域，这些应用程序可以归结为在不确定数据上建模和解决约束优化问题，包括金融、医疗保健和交通。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Prescriptive analytics, and constrained optimization in particular, is central to decision making over a broad range of domains, including finance, transportation, manufacturing, and healthcare, and has applications to scientific research as well. Typically, decision makers have relied on application-specific solutions to model and solve these problems. Such solutions are often complex and do not generalize. Moreover, the usual workflow requires that data be extracted from a database and then reformatted and fed into a separate optimization package, after which the output must be reformatted and inserted back into the database; this process is slow, cumbersome, and error prone. Finally, modern data-intensive optimization problems are of unprecedented size. A domain-independent, declarative, and scalable approach is needed, supported and powered by the system where the data relevant to these problems typically resides: the database. Then modeling becomes less ad hoc, and the overall optimization process, from data preparation through solution and exploration of results, becomes much more efficient. Desirable data management functionality --- such as consistency, persistence, fault tolerance, access control, and data-integration capability --- become an integral part of the system "for free". This project will develop algorithms and systems to provide general-purpose in-database support for prescriptive analytics applications over the sort of large scale uncertain data that is commonly encountered in practice.Specifically, the project will develop extensions to the SQL relational query language to allow specification of ``stochastic package queries'', a class of database queries that selects an optimal set ("package") of tuples that satisfy both per-tuple and global constraints. Such queries correspond to stochastic integer linear programs. Novel solution algorithms will focus on the scaling challenges caused both by uncertainty in the data and by large data volumes. The system will provide exact solutions when possible, and otherwise provide scalable Monte-Carlo-based solutions with rigorous approximation guarantees. The project will radically re-design the prior PackageBuilder system for deterministic package queries, incorporating techniques from probabilistic databases, to create a complete end-to-end system. The project will impact a broad set of domains with applications that boil down to modeling and solving constrained optimization problems over uncertain data, including finance, healthcare, and transportation.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.