1 Corrected Exercise of Branch and cut

Exercise 1

Let's consider it linear program next :

Solve by Gomory's method the problem (the first two cuts).

Solution

Let us solve the relaxed problem in real numbers. The solution is:

Gomory's cutting plane algorithm takes the variable with the largest non-integer part, here x_1. We will formulate a new constraint by considering only the fractional remainders of each coefficient:

We are creating a new slack variable for this new constraint which gives the following dictionary:

This program is not realizable, it is thus necessary to make the simplex dual. In other words, we force the output of x_5 (here x_4 enters), this gives the following dictionary:

The solution is still not satisfactory, we take the constraint with the largest fractional share therefore x_2 which gives the following cut (in fractional remainder):

Which gives a new gap variable x_6:

After applying the dual simplex (x_6 is forced out and x_5 in) we get the following result:

Note that this still does not solve our problem!