# 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\,?$$

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 $$$$\|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{**}$$$$ 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 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.