Say $S=\{g\in G\}$ is a set of elements in an abelian group $G$ whose group operation $(+)$ is expensive to compute. Given a subset $T\subset S$, we want to compute the sum of $T$'s elements, $\sigma_T=\sum_{g\in T}g$. Say we have a collection of other subsets of $S$, $U=\{T_i\}$, for which the sums $\sigma_{T_i}=\sum_{g\in T_i}g$ are already known. We can assume $U$ contains the singleton subsets of $S$, since $\sigma_{\{g\}}=g$. Hence $\sigma_T$ can always be expressed as a linear combination of the $\sigma_{T_i}$'s, namely $\sum_{g\in T}\sigma_{\{g\}}=\sum_{g\in T}g=\sigma_T$. I'd like to find the linear combination$\sum_i a_i\sigma_{T_i}=\sigma_T$, which minimizes $\sum_i|a_i|$, i.e., which computes the sum with the least number of group operations.
It seems likely that the problem of actually finding this optimum is NP-complete, so I'm looking for good heuristics, ideally with some reasonable bound on the distance from optimality. Also, any references to papers discussing this problem would be great. Finally, storing the $\sigma_{T_i}$'s is somewhat expensive for me, too, so I'm also interested in heuristics for deciding which $\sigma_{T_i}$'s should be stored, given a sequence $\{T_1, T_2, \ldots\}$, and fixed costs for storage, retrieval and group operations.
If $a_i\in\{0,1\}$, this is the exact cover problem, which is NP-complete. There are specialized algorithms for it, or you can use integer linear programming as follows. Let binary variable $a_i$ indicate whether subset $T_i \in U$ is used. The problem is to minimize $\sum_i a_i$ subject to linear constraints: $$ \sum_{i: g\in T_i} a_i = \begin{cases}1&\text{if $g\in T$}\\0&\text{if $g\in S \setminus T$}\end{cases} $$
More generally, let $a_i\in \mathbb{Z}$ be the (signed) number of times that $T_i$ is used. Let $b_i$ represent $|a_i|$. The problem is to minimize $\sum_i b_i$ subject to linear constraints: \begin{align} \sum_{i: g\in T_i} a_i &= \begin{cases}1&\text{if $g\in T$}\\0&\text{if $g\in S \setminus T$}\end{cases}\\ b_i &\ge a_i &&\text{for all $i$}\\ b_i &\ge -a_i &&\text{for all $i$} \end{align}