Searches an IPP’s feasible integer solutions by treating the LP relaxation as a search tree, splitting (branching) a fractional solution into 2 stricter subproblems and discarding (bounding) subproblems that can’t beat the best integer solution found so far.
A subproblem is the IPP’s LP relaxation with extra or bound constraints on individual variables, added by earlier branching steps. The search starts with 1 subproblem: the LP relaxation with no added bounds.
Steps
- Solve the LP relaxation of the current subproblem.
- If the solution is integral, it’s a candidate solution. Update the best solution found so far if it’s better.
- If the subproblem’s relaxed objective value is worse than the best solution found so far, discard it (bound). The relaxation’s value is an upper bound (maximization) on any integer solution inside the subproblem, so none of them can beat the best solution either.
- Otherwise, pick any variable whose value in the relaxed solution isn’t an integer, e.g. . Branch on it: make 2 copies of the current subproblem, keep every constraint the same in both, then add (here ) to 1 copy and (here ) to the other. No integer lies strictly between and , so every integer point feasible in the parent subproblem stays feasible in 1 of the 2 children, just not itself.
- Repeat on each open subproblem until none remain.
The best solution found when the search ends is the IPP’s optimal solution. An infeasible subproblem (empty feasible region) is discarded without branching.
Worked Example
Maximize subject to , , and integer.
LP relaxation optimum: , , .
- Branch on into and .
LP optimum , . Branch on into and .
LP optimum , integral, . Best solution so far.
infeasible, since forces . Discard.
LP optimum , integral, . Better than the best solution so far. New best.- The branch’s bound (12.5) is below the best solution (13). No open subproblems remain.
Optimal solution: , , .