# Branch and cut corrected exercises

This page presents a detailed corrected exercise solved by the branch and cut algorithm (also known as Gomory cutting plane). Contenus

## 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! FR FR EN ES