Mixed Integer Programming - Solution Tree Previous Next
Because the subproblem with  has no feasible solutions, it may be fathomed by Test 2. The subproblem with  cannot be fathomed by any of the three fathoming tests. Thus, we need to branch and bound on this subproblem next. Because the optimal solution for its LP-relaxation (highlighted in purple) has a noninteger value for , this variable once again becomes the branching variable. Thus, two new subproblems are created by adding the respective constraints,  and .