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. For many important problems, this decision making process can be formulated as selecting a set
of tuples (a package) in a relational database that collectively satisfy a set of linear constraints and maximize or minimize a linear objective function. Prior work [1] has
developed efficient algorithms for solving such “package queries”. Our research focuses on incremental maintenance of package-query solutions under a stream of data insertions.
In this dynamic setting, naively recomputing a package from scratch, when small delta changes are present, makes maintaining results up-to-date computationally tedious and
prohibitively expensive for real-time and near-real-time applications. Our preliminary work contributes two baseline Incremental Package Maintenance (IPM) algorithms,
approaching the problem both greedily (Greedy IPM) and heuristically, based on prior solutions (Accumulative IPM). Initial experimental results show orders-of-magnitude greater
runtime performance in large datasets relative to naive recomputation, while maintaining an experimentally robust approximation bound on the quality of the solution.
We intend to extend our results to further improve on our baseline algorithms as well as to handle data deletions and changes in the package query itself.
[1] Scalable computation of high-order optimization queries, M.Brucato, A.Abouzied, A.Meliou (2019)