Problem
I am reading the paper "Valid Linear Inequalities for Fixed Charge Problems" by Padberg et. al. (1985). In the paper, they consider the polytope
$$ P:=\text{conv}\left\{\begin{array}{l}x\in\{0,1\}^n\\y\in\mathbb{R}_+^n\end{array}:\begin{array}{l}\sum_{i=1}^ny_i=d\\y_i\leqslant u_ix_i\text{ for }i=1,\dots,n\end{array}\right\} $$
They state, without proof or reference, that under the assumptions
- $\sum_{j\neq i}u_j>d$ for all $i=1,\dots,n$
- $0<u_i\leqslant d$ for all $i=1,\dots,n$
that $\text{dim}(P)=2n-1$. I am attempting to prove this claim.
Attempted Solution
We have that
$$ P\subseteq\left\{\begin{array}{l}x\in\mathbb{R}^n_+\\y\in\mathbb{R}^n_+\end{array}:\sum_{i=1}^ny_i=d\right\} $$
that is, $P$ is a subset of a polytope defined by rank-one equality-constraints. Thus $\text{dim}(P)\leqslant2n-1$.
In order to show that this holds with equality, we may either:
- Construct a set of $2n$ affinely independent points in $P$, or
- Suppose that every point in $P$ satisfies $$\sum_{i=1}^n\alpha_ix_i+\sum_{i=1}^n\beta_iy_i=\delta$$ and show that this constraint is a scalar multiple of $\sum y_i=d$.
I haven't been able to do either of these. Any tips or references?
Let's use the second technique: Namely, assume there is some equation $$ \sum_{i=1}^n \alpha_i x_i + \sum_{i=1}^n \beta_i y_i = \delta,$$ valid for all $(x,y) \in P$, and let's show that this can only be a multiple of $$ \sum_{i=1}^n y_i = d.$$
First, if we set $x_i=1$ for all $i$, we obtain the equation $$ \sum_{i=1}^n \beta_i y_i = \delta - \sum_{i=1}^n \alpha_i.$$
For this choice of $x$, the set of feasible $y$ is exactly the intersection between the hyperrectangle $\prod_{i=1}^n [0, u_i]$ and the equality $\sum_{i=1}^n y_i = d$. Since $\sum_{i=1}^n u_i > d$, this intersection is $n-1$ dimensional, and so the only linear constraint satisfied by all $y$ is $\sum_{i=1}^n y_i = d$. Hence, $\beta_i = \beta$ and $\delta = \beta d + \sum_{i=1}^n \alpha_i$. Rewriting our inequality we must have $$ \sum_{i=1}^n \alpha_i x_i + \beta\sum_{i=1}^n y_i = \beta d + \sum_{i=1}^n \alpha_i,$$ or equivalently $$ \sum_{i=1}^n \alpha_i x_i = \sum_{i=1}^n \alpha_i.$$ But the condition $\sum_{i\neq j} u_i > d$, implies that there are feasible points for which $x_i = 0$, and $x_j = 1$ for all $j \neq i$, each of these implies that $\alpha_i=0$, and we have recovered the equality $$ \sum_{i=1}^n y_i = d.$$