Complexity of Finding Optimal Synergistic Set Packings

Question

Motivation: While developing tools for fast execution of machine learning workflows, we realized that many workflows require intermediate results -- sometimes we should cache these results, and sometimes we should recompute them from scratch.

We were able to reduce the problem of determining the optimal set of intermediate results to cache to the following very natural problem, which I call synergistic set-packing.

Problem: We are given a universe of $m>0$ elements $U = \{e_1, e_2, \ldots, e_m\}$, as well as a function $c : U\rightarrow \mathbb{Z}^+$ which maps each element to some positive integral cost. We are furthermore given a collection $\mathcal{C}$ containing $n>0$ nonempty subsets of $U$; $\mathcal{C} = \{S_1, S_2, \ldots, S_n\}$. Finally, we are also given a function $p : \mathcal{C} \rightarrow \mathbb{Z}^+$ which maps each $S_i$ to some positive payoff.

Our goal is to choose $X \subseteq U$ that maximizes the following benefit function of payoff - cost: $$ \left(\sum_{S_i\in\mathcal{C} \text{ with } S_i\subseteq X}p(S_i)\right) - \left(\sum_{e_j\in X} c(e_j)\right) $$

That is, if we pick all of the elements for some $S_i \in \mathcal{C}$, we get a payoff of $p(S_i)$, but we must pay for all of the elements in $S_i$ to get this payoff.

Approaches: At first glance, this problem seems pretty similar to the (somewhat obscure) NP-hard minimum K-union problem (1), where our goal is to pick the $k$ sets whose union cover the fewest elements (in our problem, in the case of unit costs / payoffs, we would try to pick the $k$ elements that hit the fewest number of sets, and then include the rest of the $m-k$ in $X$, but the analogy does not quite work since there is no requirement that we choose $X$ to have at most $m-k$ elements).

Any help with characterizing this problem's complexity is of course much appreciated!

Example: I will put the cost/payoff next to each item, after a colon. Suppose $U$ is given by (along with costs) $\{e_1: 2, e_2: 2, e_3: 1\}$, and in our collection we have: $$S_1 = \{e_1, e_2\} : 1$$ $$S_2 = \{e_2, e_3\} : 4$$

Then in this case we would pick $X = \{e_2, e_3\}$, for a total cost of 3 and a payoff of 4, for a net benefit of 1.

(1) Staal A. Vinterbo (2002). A Note on the Hardness of the k-Ambiguity Problem. DSG Technical Report 2002-006.

Answer 1

This is an instance of the standard network flow problem called "Project Selection", and hence can be solved efficiently (even in practice). See (what's currently) Section 24.6 of Jeff Erickson's lecture notes for a nice explanation. It's covered in most introductions to network flow in good undergraduate algorithms courses, so if you don't like Jeff E's notes, I'm sure you can find plenty of alternatives.

The general idea of project selection is that you have a collection of projects, each with a cost/benefit (positive or negative) and a collection of dependencies, and the goal is to find the set of projects that (1) satisfies dependencies, and (2) maximizes the benefit of all the selected projects.

For your case, you would have one project for each set $S_i$, and also one project for each $e_j$. Each $e_j$ project has no dependencies, and each $S_i$ will depend on the $e_j$ in $S_i$. The benefit of $S_i$ is its payoff, and the 'benefit' of each $e_j$ is the negative of its cost. You can see that reasonable ways of selecting projects correspond to all the ways of picking solutions to your problem, and the objective values are the same on either side of the correspondence.

I'll just add that you're really only using a special case of project selection, where there are "good" projects that only depend on "bad" projects that have no further dependencies. Project selection doesn't assume this structure, and can be solved on an arbitrary dependency graph. You might find this useful in your application where you've got multiple phases of computation.