The most infeasible integer variable is used as the branching variable, and best-bound is used for node selection. Each box in the tree contains the optimal solution to the relaxation and its value.

**Notation:**

- is the set of active nodes.
- is the value of the best known integer solution. This is initialized to .
- is the value of the relaxation of problem .

**Progress of the algorithm:**

- Initially, consists of just the problem . The solution to the LP relaxation is , , with value . The most infeasible integer variable is , so two new subproblems are created, where and where , and .
- Both problems in have the same bound , so assume the algorithm arbitrarily selects . The optimal solution to the LP relaxation of is , , with value . The most infeasible integer variable is , so two new subproblems of are created, where and where , and now .
- The algorithm next examines , since this is the problem with the best bound. The optimal solution to the LP-relaxation is , , with value . Since is integral feasible, can be updated to and is fathomed.
- Both of the two problems remaining in have best bound greater than 58, so neither can yet be fathomed. Since these two subproblems have the same bound , assume the algorithm arbitrarily selects to examine next. The LP relaxation to this problem is infeasible, since it requires that satisfy , and simultaneously. Therefore, , and this node can be fathomed by infeasibility.
- That leaves the single problem in . The solution to the LP relaxation of this problem is , , with value . Since , this subproblem can also be fathomed by bounds. The set is now empty, so is optimal for the integer programming problem .

John Mitchell

2009-03-05