0
$\begingroup$

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:
enter image description here

The first question asks me to show that the given constraint implies the following cuts:
enter image description here

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

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:
enter image description here

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.

$\endgroup$
10
  • $\begingroup$ Is there any constraint on $y_5$? $\endgroup$ Commented Mar 12, 2021 at 14:25
  • $\begingroup$ Only constraint is that it is 0-1 ILP. All yi values are either 0 or 1 integers. $\endgroup$ Commented Mar 12, 2021 at 14:31
  • $\begingroup$ So there is no typo, and the first equation actually is intended to be equivalent to $(9)y_1 + (21)y_2 + (13)y_3 + (15)y_4 + (18)y_6 \leq 52$? $\endgroup$ Commented Mar 12, 2021 at 14:36
  • $\begingroup$ What does "ILP" refer to? Also, assuming no typo, does this mean that it needs to be proven that since $1$ is an upper bound for $y_5$, that it needs to be proven that $y_1 + y_2 + y_3 + y_4 + y_6 \leq 4$ and $y_2 + y_3 + y_4 + y_6 \leq 3$? Further, if $1$ is also an upper bound for $y_1$, does this mean that the second inequality implies the first? $\endgroup$ Commented Mar 12, 2021 at 14:43
  • $\begingroup$ There is a typo, thank you for catching it, y6 should be y5.ILP refers to Integer Linear Programming. After solving the LP relaxation using simplex method, if the solution is non-integer then new cuts are needed to be added to the tableau, which will produce primal infeasibility. My guess is that the question requires us to show this infeasibility but I am unsure. $\endgroup$ Commented Mar 12, 2021 at 14:54

2 Answers 2

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I think I understand the constraint of the form, I shall look into cover inequalities more thoroughly. Lastly could you expound on how I would convert the constraint in the last question to the one you derived in this answer? $\endgroup$ Commented Mar 12, 2021 at 21:54
  • $\begingroup$ I don't understand the last question. Can you please provide a link to the source of the problem? $\endgroup$ Commented Mar 12, 2021 at 22:19
  • $\begingroup$ Sorry, I still don't understand what is being asked. Please edit the question to match the exact wording. $\endgroup$ Commented Mar 12, 2021 at 22:53
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I understand the reasoning behind this but this only applies to the first constraint as the second constraint gives us 50 which does not cause a contradiction as far as I can tell. $\endgroup$ Commented Mar 12, 2021 at 15:49
  • $\begingroup$ @Songaro Answer edited for Part 2. Unclear if I have made a mistake on the meaning of the constraints on the variables. If so, please advise. $\endgroup$ Commented Mar 12, 2021 at 16:06
  • $\begingroup$ I do not understand why y5=0=y6, could you clarify that statement? $\endgroup$ Commented Mar 12, 2021 at 18:40
  • $\begingroup$ @Songaro see the Addendum that I just added to my answer. $\endgroup$ Commented Mar 12, 2021 at 20:48

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.