Back

Iterations

Backtracking begins at the greatest level of the tree, level 3, and climbs up the tree until it finds a vertex that has been visited only once. In this case the vertex at level 3 is discovered, so the process stops immediately. A new vertex is created at this level branching in the opposite direction. In this case since X2 branched up at value 1, the opposite is to make X2 branch down at value 0. The tree after backtracking is shown below. The green underline at level 3 emphasizes that the level has been visited twice. On the next backtracking operation, we will not stop at level 3.

The analysis of this solution shows that its objective value is the same as the incumbent. There is no point in forcing the non-integer variables in the solution to be integer, because that can only reduce the objective value. Instead we fathom this vertex and backtrack. The tree indicates that the backtrack will take us to level 2. Both possibilities have already been considered at level 3.