This page presents a detailed corrected exercise solved by the branch and cut algorithm (also known as Gomory cutting plane).
Let's consider it linear program next :
Solve by Gomory's method the problem (the first two cuts).
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!