Branch and Bound

Searches the IPP’s feasible integer solutions by repeatedly splitting (branching) the LP relaxation’s feasible region and discarding (bounding) subproblems that can’t improve the best integer solution found so far.

Steps

• Solve the LP relaxation of the current subproblem.
• If the solution is integral, it’s a candidate solution. Update the best known integer solution (incumbent) if it’s better.
• If the subproblem’s relaxed objective value is worse than the incumbent, discard it (bound).
• Otherwise, pick a fractional variable $x_j = k.\text{frac}$ and branch into 2 subproblems: $x_j \le \lfloor k \rfloor$ and $x_j \ge \lceil k \rceil$.
• Repeat on each open subproblem until none remain.

The incumbent when the search ends is the IPP’s optimal solution. An infeasible subproblem (empty feasible region) is discarded without branching.