linear programming with $n$ choose $r$ variables

Question

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

Answer 1

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.