The root node solves the LP relaxation — the objective and constraints above, but allowing x₁ and x₂ to take any real value. If that optimum already lands on integers, we're done. Otherwise the search branches on the most fractional variable: one child adds x⌊≤ floor(value)⌋, the other adds x⌊≥ ceil(value)⌋, splitting the fractional point out of the feasible region.
Each child re-solves its own (smaller) LP relaxation. A branch is pruned — shown grey — the moment it's infeasible, or its relaxation's value can't beat the best integer solution found so far (the current bound). This is what makes branch-and-bound fast: whole subtrees are discarded without ever being fully explored.
if LP infeasible: prune (infeasible)
if LP value <= bound: prune (bound)
if LP solution integer: candidate; update bound if better
else: branch on most-fractional variable
- Grey nodes — pruned (infeasible or worse than the current bound).
- Amber nodes — fractional relaxation, branched into two children.
- Cyan nodes — an integer-feasible solution, but not the best found.
- Green node — the current best integer solution (incumbent); it moves as better ones are found.
Real-world relevance: this exact loop — relax, branch, bound, prune — is what solvers like CBC, Gurobi and CPLEX run millions of times a second on scheduling, routing and resource-allocation problems with thousands of integer variables.