Iteration 3

 

Now the relaxed problem has two cuts. The cut just added is tight. It happens that Cut1 is now loose. Frequently, cuts created early in the procedure will become loose later.

We choose the Gomery cut with the largest constant to add to the LP relaxation. In this case there are two Gomery cuts with the same constant, C2 and C6. They both describe the same cut.

 

LP

Gomery

Cut

Gomery

Cut

in

Original

Variables