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

University Of Massachusetts Amherst, Amherst MA

Investigators

Abstract

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.