linear programming with $n$ choose $r$ variables Given parameters $r < n$, define $m = {n \choose r}$ and let $A$ be the $n\times m$ matrix whose columns are all the vectors with $r$ $1$'s and $n-r$ $0$'s. Let $b$ be a positive $n$-vector. Is there a simple solution to the linear program:
$$ \max \sum_i x_i$$
subject to
$$ Ax \le b$$
and
$$ x\ge 0\,?$$
 A: Let $\|\cdot\|=\|\cdot \|_1$ be the $1$-norm.
Let $C$ be the convex cone generated by the columns of your matrix. So you need to find $b^*\in C$ such that $b^*\leq b$ (entry-wise) and $\|b^*\|$ is maximal (the required maximum will be $\|b^*\|/r$).
Notice that all generators (and hence all $y=[y_i]\in C$) satisfy the following constraints:
\begin{align*}
  y_i&\geq 0, &i&\in[n];\\
  \sum_{i\notin \mathcal I}y_i&\geq \left(1-\frac{|\mathcal I|}r\right)\|y\|, &\mathcal I&\subset[n], \quad 1\leq |\mathcal I|\leq r-1. \tag{$*$}
\end{align*}
Hence, if we assume that $b=[b_i]$ with $b_1\geq \dots\geq b_n\geq 0$, then we have
\begin{equation}
  \|b^*\|\leq \mu(b):=\min_{0\leq j\leq r-1}\left(1-\frac jr\right)^{-1}
    \sum_{i=j+1}^n b_i. \tag{$**$}
\end{equation}
We will show that the equality can always be met (in particular, ths yields that $C$ is determined by the above inequalities).
Induction on $n+r$. If $r=1$ or $r=n$, the claim is obvious. If $b_n=0$, then we may decrease $n$ by $1$. So, in the sequel we assume that $n>r>0$ and $b_1>0$.
Let $j_0$ be the maximal minimizer in $(**)$. Two cases are possible.
Case 1. $j_0>0$. Notice that
$$
  \left(1-\frac {j_0}r\right)^{-1} \sum_{i=j_0+1}^n b_i\leq
  \left(1-\frac {j_0-1}r\right)^{-1} \sum_{i=j_0}^n b_i,
$$
which yields
$$
  (r-j_0)b_{j_0}\geq \sum_{i=j_0+1}^n b_i=\frac{r-j_0}r\mu(b),
$$
so that $b_1\geq\dots\geq b_{j_0}\geq \mu(b)/r$. Informally, this means that we may harmlessly use the vectors having ones at coordinates $1,2,\dots,j_0$.
So, now consider $b'=[b_{j_0+1},\dots,b_n]$, and set $n'=n-j_0$ and $r'=r-j_0$. For a new set up, for every $0\leq j<r'$ we have
$$
  \sum_{i=j+1}^{n'}b_{i+j_0}\geq \left(1-\frac {j+j_0}r\right)\mu(b)
  =\frac{r-j-j_0}{r-j_0}  \sum_{i=1}^{n'}b_{i+j_0}=\frac{r'-j}{r'}\sum_{i=1}^{n'}b_{i+j_0}.
$$
This means that $b'$ satisfies the inequalities $(**)$ and thus, by the hypothesis, $b'$ is represented as a nonnegative combination of the  $n'$-columns with $r'$ ones in each. Augmenting those vectors by the prefix of $j_0$ ones we get a required vector
$$
  b^*=[\underbrace{\mu(b),\dots,\mu(b)}_{j_0},b_{j_0+1},\dots,b_n]^T
$$
with $\|b^*\|=\mu(b)$.
Case 2. $j_0=0$. This means that $b$ satisfies all inequaliies in $(*)$; moreover, they are all strict.
In this case, subtract from $b$ a positive multiple $\alpha\mathbf{1}$ of the all-ones vector (which is clearly in $C$) so that either the last coordinate vanishes or some inequality in $(*)$ turns into equality (so that the new vector $b'=b-\alpha\mathbf{1}$ will have a positive minimizer in $(**)$). Then apply the above arguments.
