Illustrative Example of Branch-and-Bound
John Mitchell

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:

1. 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 .
2. 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 .
3. 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.
4. 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.
5. 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