8
$\begingroup$

enter image description here

In my textbook, to generate cutting planes, they tell you to proceed as follows:

A procedure for generating cutting planes:

  1. Select a ($\le$) constraint that has only nonnegative coefficients.

  2. Find a group of variables such that

a) The constraint is violated when all variables in the group equals 1 and the remaining variables equal to 0.

b) But the constraint is satisfied if any one of the variables in the group is changed from 1 to 0.

  1. Suppose there are $K$ variables in the group add the following constraint as a new cutting plane: Sum of variables in the group $\le 𝐾 − 1$

My Question: Why isn't $x_2+x_3+x_4\le 2$ a cutting plane? Since if we go by 2a) , and put $x_2=1 , x_3=1 , x_4=1$ and $x_1=0$ , then it violates the inequality? Since $11>7$

$\endgroup$
13
$\begingroup$

It is a cutting plane, but it is implied by $x_2+x_4\le 1$ and $x_3\le 1$ so not very useful.

$\endgroup$
1
  • 1
    $\begingroup$ Oh okay, i see. Thanks! $\endgroup$
    – Slim Shady
    Jan 1 '20 at 1:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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