Iteration 2

 

The cut added in the first iteration is placed at the top of the constraint set. It is labeled 5, for the fifth constraint, and has the name Cut1. The LP solution shows that this cut is necessarily tight. Notice that at each iteration a cut is added and a variable is added. The variable is the slack variable for the cut. For this iteration, the variable is assigned the index 11, the number of structural variables (6) plus the number of original slack variables (4), plus the number of cuts (1). Since the number of nonbasic variables is the total number of variables (11) minus the number of constraints (5), that number remains fixed at 6 throughout the iterations.

For this example we will always choose the Gomery cut with the greatest constant. We will never choose the Dantzig cut.

 

LP

Gomery

Cut

Gomery

Cut

in

Original

Variables