Linear Programming Cutting Problem

Question

I'm doing some self studying and I have come across a problem I don't quite understand. The problem only gives me the single constraint:

The first question asks me to show that the given constraint implies the following cuts:

The second questions requires me to come up with a general rule for making cuts like the second cut from the given constraint:

The last question asks me how would I use this constraint to derive such cuts and wants me to convert it to the form in the second question:

I can see the constraint requiring less than four or five "1" values at minimum but I'm not quite sure how I would go about showing it. I haven't been able to find a question of similar nature anywhere else so I turn to people here hoping they might understand what I don't.

Answer 1

Based on comments exchanged with OP.

If it is not the case that $(y_1 + \cdots + y_6) < 5$

then $(y_1 + \cdots + y_6) \geq 6.$

This implies that $9 \times (y_1 + \cdots + y_6) \geq 54.$

However, it is given that

$9 \times (y_1 + \cdots + y_6) \leq (9)y_1 + (10)y_2 + (11)y_3 + (11)y_4 + (13)y_5 + 16(y_6) = 52 < 54.$

Thus, the original constraint implies that $9 \times (y_1 + \cdots + y_6) \leq 52.$

Therefore, since the assumption that
it is not the case that $(y_1 + \cdots + y_6) < 5$
led to the conclusion that
$9 \times (y_1 + \cdots + y_6) \geq 54$,

the assumption that it is not the case that $(y_1 + \cdots + y_6) < 5$
has caused a contradiction.

Therefore, the assumption must be false.

---

The 2nd part is reasoned in the following way.

If $y_2 + \cdots + y_6 \geq 5$, then

$y_2 + \cdots + y_6 = 5 \implies$

$10(y_2 + \cdots + y_6) = 50$.

From the original constraint, this implies that $y_1 = 0.$

Further, from the original constraint, since each variable must be in $\{0,1\}$, it is immediate that $y_5 = 0 = y_6$ (else the original constraint would have to be violated, since the sum would have to be at least $53$).

However, with $0 = y_1, y_5, y_6$, you can't have $y_2 + y_3 + y_4 = 5$, since the max value of each variable is $1$.

Thus, the assumption that $y_2 + \cdots + y_6 = 5$ has led to a contradiction.

Addendum
Responding to the question/comment of Songaro.

Assume that the following constraints are satisfied:

$$9y_1 + 10y_2 + 11y_3 + 11y_4 + 13y_5 + 16y_6 \leq 52.\tag1$$

$$ y_2 + y_3 + y_4 + y_5 + y_6 = 5. \tag2 $$

$$ y_1, y_2, \cdots, y_6 ~~\text{are each in}~~ \{0,1\}. \tag3$$

From (2) above, you know that $$ 10y_2 + 10y_3 + 10y_4 + 10y_5 + 10y_6 = 50. \tag4$$

Subtracting (4) from (1) gives $$9y_1 + y_3 + y_4 + 3y_5 + 6y_6 \leq 2.\tag5$$

Jointly considering (3) and (5) indicates that
If any of $y_1, y_5,$ or $y_6$ are non-zero, (5) above will have to be violated.

Alternatively, assuming that $y_1, y_5, y_6$ are all zero indicates that (2) and (3) above can not jointly be satisfied.

Thus, (2) above has caused a contradiction.

Answer 2

These cuts are called cover inequalities or no-good cuts. If your original constraint is $$\sum_{i=1}^n a_i y_i \le a_0,$$ any subset $C \subseteq \{1,\dots,n\}$ with $$\sum_{i\in C} a_i > a_0$$ yields a cover inequality $$\sum_{i\in C} y_i \le |C|-1.$$ You can derive this via conjunctive normal form as follows: $$ \lnot \bigwedge_{i\in C} y_i \\ \bigvee_{i\in C} \lnot y_i \\ \sum_{i\in C} (1 - y_i) \ge 1 \\ \sum_{i\in C} y_i \le |C|-1 $$ Your first cut arises from $C=\{1,\dots,6\}$ with $\sum_{i\in C} a_i = 70 > 52$, and your second cut arises from $C=\{2,\dots,6\}$ with $\sum_{i\in C} a_i = 61 > 52$.