Pruning in branch and bound method (6 leaves, LP relaxations, etc)

HD5450

New member
Joined
Dec 13, 2018
Messages
4
A certain minimization integer program has two integer variables x and y (among other decision variables that are not required to be integers). Suppose that at a certain point during the solution of the problem by the branch-and-bound method, the branch-and-bound tree has exactly 6 leaves (A through F) and that the LP relaxations they represent have the following optimal solutions (“val” denotes the optimal objective function value, the values of the non-integer variables are not shown):

Branch A: val = 10, x = 3, y = 4.5
Branch B: val = 26, x = 2, y = 0
Branch C: val = 26, x = 0.5, y = 3
Branch D: val = 20, x = 2, y = 3.4
Branch E: val = 30, x = 6, y = 3
Branch F: Infeasible

So I understand that I can prune branch E by optimality and branch E for infeasibility. However, I don't know if I am able to prune other branches (since the variable are non-integer) or will I be able to continue branching.
 
Top