---

Presenter: Henry Philip Booth

Faculty Sponsor: Alexandra Meliou

School: UMass Amherst

Research Area: Computer Science

Session: Poster Session 3, 1:15 PM - 2:00 PM, 163, C19

ABSTRACT

In the relational database setting, a package query returns a multiset of tuples that maximizes or minimizes a linear objective function subject to local and global linear constraints. Prior advancements have shown the correspondence of package queries to Integer Linear Programs(ILPs) and constructed algorithms like ProgressiveShading for reliable package query evaluation in billion-tuple datasets. However, existing package query algorithms treat constraint bounds as absolute thresholds, never returning packages that violate any constraint, even by a small margin. In practice, users may not be as particular about the constraint thresholds as the solvers, and would happily explore alternative packages that (i) significantly improve objective values at the cost of minor constraint violations, or (ii) significantly ease demand on resources through tightened constraints, with a small loss of objective value. In this paper, we propose an algorithm for alternative package recommendation through constraint perturbation. By formulating the alternative packages problem as a mixed-ILP, with individual perturbation variables for each constraint and total constraint perturbation bound, our algorithm can identify desirable alternative package recommendations that optimally balance package solution objective value with total constraint perturbation. We believe that our mixed ILP approach will outperform naive modifications of progressive shading to solve the alternative package finding problem, and are currently running experiments to confirm that hypothesis. Further, our algorithm recommends a selection of optimized and varied alternatives, providing users the flexibility to select the package that is most desirable to them.