0

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

  1. $\sum_{j\neq i}u_j>d$ for all $i=1,\dots,n$
  2. $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:

  1. Construct a set of $2n$ affinely independent points in $P$, or
  2. 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?

David M.
  • 2,623

1 Answers1

1

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.$$

funda
  • 131
  • In particular, this seems like a proof about the LP relaxation rather than the convex hull. – David M. Jan 22 '18 at 17:16
  • You are right, I was assuming the relaxation was contained in the convex hull, which is not true. – funda Jan 22 '18 at 19:11
  • Thank you for the update. I'm a little confused on the existence of the $n-1$ dimensional set. We assert that the only linear constraint satisfied is sum(y)=d...but isn't that what we're trying to prove? – David M. Jan 22 '18 at 19:39
  • Well in this case it is much easier: Taking $\lambda \in (0,1)$ such that $\lambda \sum_{i=1}^n u_i = d$, the point $y = \lambda u$ is in the interior of the hyperrectangle, and so it is free to move on the hyperplane. – funda Jan 22 '18 at 19:56
  • I don't think I follow. The proof asserts that $\sum y_i=d$ is the only linear constraint satisfied by all $y$. How do we know there can't be another? – David M. Jan 22 '18 at 20:14
  • By the argument on my comment above, the dimension is exactly $n-1$, and having another would mean the dimension is at most $n-2$. – funda Jan 22 '18 at 20:19