What is the convex hull of nonconvex polytopes defined by mixed integer linear inequalities (with only binaries)

43 Views Asked by At

Define $$S=\{(x_1,x_2,y)|0\le x_1\le y\overline{x},0\le x_2\le (1-y)\overline{x},x_1,x_2\in\mathbb{R},y\in\{0,1\}\},$$ $\operatorname{conv}(S)$ is the convex hull of $S$. $\le$ is componentwise. $\overline{x}$ is the constant upper limit of $x$.

Is $$\operatorname{conv}(S)=\{(x_1,x_2,y)|0\le x_1\le y\overline{x},0\le x_2\le (1-y)\overline{x},x_1,x_2,y\in\mathbb{R},0\le y\le 1\},$$ which just calculates the relaxation of $y$?

Besides, what if the dimension is increased? Consider the set $$S_n=\{(x_1,x_2,y)|0\le x_1\le y\overline{x},0\le x_2\le (1-y)\overline{x},x_1,x_2\in\mathbb{R}^n,y\in\{0,1\}^n\},$$ where $n$ is the dimension.

For example, when $n=3$, is $$\operatorname{conv}(S_3)=\{(x_1,x_2,y)|0\le x_1\le y\overline{x},0\le x_2\le (1-y)\overline{x},x_1,x_2,y\in\mathbb{R}^3,0\le y\le 1\}?$$

1

There are 1 best solutions below

2
On

A simple approach is to show that a fractional $y$ cannot yield an extreme point. Explicitly, let $P$ be the polytope obtained from $S$ by relaxing integrality of $y$, and suppose $(x_1^*,x_2^*,y^*)\in P$ with $0 < y^* < 1$. Then note that \begin{align} \left(\frac{x_1^*}{y^*},0,1\right)&\in P \\ \left(0,\frac{x_2^*}{1-y^*},0\right)&\in P \\ y^*\left(\frac{x_1^*}{y^*},0,1\right) + (1-y^*)\left(0,\frac{x_2^*}{1-y^*},0\right) &= (x_1^*,x_2^*,y^*) \end{align} So $(x_1^*,x_2^*,y^*)$ is not an extreme point of $P$.