-1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ In my copy of Wolsey (1998), Exercise 4 in Chapter 1 is to show that the three sets are equal. The only related example in that chapter explicitly lists the feasible solutions and invites the reader to check that three given constraint sets are valid formulations. I think the intent of the exercise is to show that the $12$ feasible solutions satisfy all inequalities and the remaining $2^4-12=4$ solutions in $\{0,1\}^4$ violate at least one inequality in each set. $\endgroup$
    – RobPratt
    Dec 6, 2023 at 0:29
  • $\begingroup$ Cross-posted: math.stackexchange.com/questions/4820413/… $\endgroup$
    – RobPratt
    Dec 6, 2023 at 2:04

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ You have shown that the new inequalities are valid but have not shown the reverse direction. $\endgroup$
    – RobPratt
    Dec 5, 2023 at 17:20
  • 2
    $\begingroup$ @RobPratt Actually this might be a misunderstanding of the OP that needs to be addressed. The OP wrote: "Show how to go from Equivalence (1) to (2) and from Equivalence (2) to (3)". This kind of suggests that the OP might not realise that showing $(1) \implies (2) \implies (3)$ is not sufficient to conclude $(1) \iff (2) \iff (3)$. $\endgroup$
    – Stef
    Dec 5, 2023 at 17:51
  • $\begingroup$ Dear @RobPratt, what I understood from OP was how we can derive the mentioned cover cuts from the original inequality (1). $\endgroup$
    – A.Omidi
    Dec 5, 2023 at 18:18
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ You have shown that the new inequalities are valid but have not shown the reverse direction. $\endgroup$
    – RobPratt
    Dec 5, 2023 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.