Need help with integer programming exercise

Question

This is an exercise from Wolsey that I can't solve. Show how to go from Equivalence (1) to (2) and from Equivalence (2) to (3): $$ \begin{align} X &= \{ x \in \{0, 1\}^4~\mid~97x_1 + 32x_2 + 25x_3 + 20x_4 \le 139 \} \tag{1} \\ &\equiv \{ x \in \{0, 1\}^4~\mid~2x_1 + x_2 + x_3 + x_4 \le 3 \} \tag{2} \\ &\equiv \{ x \in \{0, 1\}^4~\mid~x_1+ x_2 + x_3 \le 2, \ x_1 + x_2 + x_4 \le 2, \ x_1 + x_3 + x_4 \le 2 \} \tag{3} \end{align} $$

Answer 1

As the problem only contains four variables let's define $f$ as the feasible solution space of the problem. Then $f$ contains $12$ feasible solutions: $\{(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (1,1,0,0), (1,1,1,0), (1,0,1,0), (1,0,0,1), (0,1,1,0), (0,1,0,1), (0,0,1,1), (0,1,1,1) \}.$

Now, we can drive the second inequality by multiplying the first constraint in an appropriate multiplier, e.g. $1/50$, and rounding the coefficients. Then, we can derive the third inequality as follows:

A set $C$ is called a knapsack cover if $C = \sum_{j \in C} a_j - b$ is positive. Each knapsack cover $C$ defines the cover inequality:

$$ \sum_{j \in C} x_{j} \leq | \ C \ | - 1 $$

Now, by investigating which combination of the variables can violate the original constraint $(1)$, the violated items would be of the form $ \sum_{j} a_{j} x_{j} \geq b$, we can derive $x_1 + x_2 + x_3 \leqslant 2$ that means $ 97 + 32 + 25 \gt 139 $. To derive the remaining in the $(3)$ the procedure is the same. If you check the derived inequalities neither of them violates the original solution space, but violates the excess values.

Answer 2

Given the system you presented

$X = \{ x \in \{0, 1\}^4 : 97 x_1 + 32 x_2 + 25 x_3 + 20 x_4 \leqslant 139 \}$ (1)

We have that, if $x_1 = 1$, then $x_2 + x_3 + x_4 \leqslant 1$, since any solution where $x_2 + x_3 + x_4 > 1$ leads to infeasibility.

• $97 + 32 + 25 > 139$, for $x_1 = x_2 = x_3 = 1$;
• $97 + 32 + 20 > 139$, for $x_1 = x_2 = x_4 = 1$.

Therefore, suffices to say that $2 x_1 + x_2 + x_3 + x_4 \leqslant 3$ (2), i.e., if $x_1 = 1$, then $x_2 + x_3 + x_4 \leqslant 1$.

The same above depicted reasoning can be made without the coefficient $2$, ending up with (3):

• $x_1 + x_2 + x_3 \leqslant 2$, since $97 + 32 + 25 > 139$;
• $x_1 + x_2 + x_4 \leqslant 2$, since $97 + 32 + 20 > 139$; And
• $x_1 + x_3 + x_4 \leqslant 2$, since $97 + 25 + 20 > 139$.

I hope it helps, let me know of any doubt.