Intervals from an underdetermined nonnegative linear system I'm working on a problem in genomics that yields the following puzzle. Let $b\in \mathbb R^I$, $t$ and $p\in \mathbb R^J$, and $s \in \mathbb R^{I\times J}$. Suppose $t,b,p$ are known. Further suppose:


*

*$t_j = \sum_i s_{ij}$

*$b_i = \sum_j p_j s_{ij}$

*$s_{ij} > 0$
What's a simple, efficient way to infer, for all $i$, $j$, the narrowest interval $[\ell_{ij}, u_{ij}]$ that is guaranteed to contain $s_{ij}$? 
$I$ and $J$ will both be at most dozens and often much less, but I will want to repeat this hundreds of thousands of times. 
I tagged this as causal statistics even though it's not causal statistics because I know that very similar problems arise in the binary instrumental variable model when bounding the average causal effect.
 A: The set of $s$'s that fit the data is a polytope, and finding the intervals you described is the same as projecting the polytope onto each coordinate axis. Polytope projection is described on this lovely page with lots of algorithmic options. One possible solution is to find the vertices, project them, and take the max and min. 
The abstract of this paper suggests that you can't do any better than vertex enumeration in many cases. Your input is in $H$-representation (it's intersection of half-spaces), and the output can be in any representation, since it's so simple. Your target subspace is not degenerate, so according to table 2 of the paper, your problem is "VE-hard", i.e. at least as hard as vertex enumeration.
So, follow the first link and figure out the "plumbing", e.g. the values of $A$, $b$, $C$, $d$, and $x$ in terms of your $b$, $t$, $p$ and $s$. (Hint: your $s$ gets vectorized into $x$. Sums and weighted sums are implemented by entries of $C$, which will depend on your $p$. $A$ is negative identity and $b$ is 0. $d$ contains your $b$ and $t$. 
