Let $a_1,\ldots,a_n>0$, and let $S_1,\ldots,S_d\subset\{1,\ldots,n\}$ (all non-empty). For any $I\subseteq\{1,\ldots,d\}$, define $S(I)=\bigcap_{i\in I} S_i$. Given some $1\leq s < d$, consider the problem $$ \mathop{\mathrm{minimize}}_{I\subset\{1,\ldots,d\}:\,1\leq|I|\leq s} \frac{\sum_{j\in S(I)} a_j}{\left|S(I)\right|}, $$ where $\left|S(I)\right|$ is the cardinality of $S(I)$, i.e., $\frac{\sum_{j\in S(I)} a_j}{\left|S(I)\right|}$ is simply the average of the $a_j$ which are indexed by $j\in S(I)$ (we let $\frac{0}{0}=\infty$, i.e., $I$ such that $S(I)=\emptyset$ are not allowed, but if it makes things simpler we can assume that never happens).
Does this look familiar? I highly doubt there is a computationally tractable solution (as a function of both $n$ and $d$), but perhaps an approximation/convex relaxation? Seems like it could be related to some normalized weighted cut problem, but I don't see a straightforward exact equivalence.
This problem occurs as a sub-subroutine in a problem I'm trying to solve, and there may be further conditions I can squeeze out to make things simpler -- such as upper bounds on $a_j$, or on $|S_i|$, etc. If there are any conditions under which the problem is easier, please do tell.
Thanks.
EDIT: So it's an integer program with a linear fractional objective. Let $b_1,\ldots,b_d\in\{0,1\}^n$ be indicator vectors for the sets $S_1,\ldots,S_d$. Then the problem is I think equivalent to
\begin{align} \mathop{\mathrm{minimize}}_{I\in\{0,1\}^d,x\in\{0,1\}^n} & \frac{a^Tx}{\mathbf{1}^Tx}&\\ \text{subject to}\;\;\; & 1\leq \mathbf{1}^TI\leq s &\\ & x_i\geq \left(\sum_{j=1}^d 1-(1-b_{ji})I_j\right)-d+1 &\forall i=1,\ldots,n\\ & x_i\leq 1-(1-b_{ji})I_j & \forall i=1,\ldots,n;\; j=1,\ldots,d \end{align} where the last two lines encode the constraint $x_i=\prod_{j:\,I_j=1} b_{ji}$.
