I have the following problem assigned to me. (I found out it was from Conforti- Zambelli Integer Programming Book, Exercise 2.1)
Can someone please help me how to proceed. I am stuck with this and am not able to think of anything. Have been working on this problem for hours now. Otherwise, I wouldn't have asked since it is a homework problem.
Let $S\stackrel{\rm def}{=}\{ x\in\{0,1\}^4: 2x_1+x_2+x_3+x_4\leq 3\}$, and $S'\stackrel{\rm def}{=}\{ x\in\{0,1\}^4: 2x_1+x_2+x_3+x_4\leq 3,\ x_1+x_2+x_3\leq 2,\ x_1+x_2+x_4\leq 2,\ x_1+x_3+x_4\leq 2\}$.
Clearly, $S'\subseteq S$, so it suffices to prove $S\subseteq S'$.
By contradiction, suppose $S\setminus S' \neq \emptyset$, and let $x\in S\setminus S'$. This means at least one of the 3 "new" constraints is violated by $x$. Without loss of generality, assume $x_1+x_2+x_3 > 2$ (without loss of generality, because of the symmetry).
Then, since $x_1,x_2,x_3\in\{0,1\}$ by definition of $S$, we have that the integer $x_1+x_2+x_3$ satisfies $$2<x_1+x_2+x_3 \leq 3$$ that is $x_1+x_2+x_3=3$; from which $x_1=x_2=x_3=1$.
But then, $2x_1+x_2+x_3 = 2+1+1=4 > 3$, and $x\notin S$ — contradiction.