When solving a min IP problem using the BnB method I do understand that the upper bound is found from valid solutions and how this is used for pruning. I do however have some problems understanding the best global lower bound is found, such that the gap to the solutions are found.
I have read that it is found by optimal solutions in leaf nodes, but doesn't optimal solutions to the subproblems create valid solutions to the main problem, and therefor are candidates to the upper bound?
The lower bound is obtained by relaxing integrality. In particular, solving the linear programming (LP) relaxation of the original problem yields a global lower bound at the root node. Once you start branching, the minimum of the LP lower bounds among all active nodes yields a global lower bound. More generally, for any partition of the original feasible region, the minimum of the lower bounds of the parts yields a global lower bound.