Illustrative Example of Branch-and-Bound
John Mitchell


\begin{displaymath}
\begin{array}{lrcrclrr}
\mbox{maximize} & 13x_1 & + & 8x_2 \...
...lumn{5}{l}{\phantom{00}\mbox{$x_1,\ x_2$\ integer}}
\end{array}\end{displaymath}






The most infeasible integer variable is used as the branching variable, and best-bound is used for node selection. Each box in the tree contains the optimal solution to the relaxation and its value.

Notation:

Progress of the algorithm:

  1. Initially, \(L\) consists of just the problem \(\mbox{IP}^0\). The solution to the LP relaxation is \(x_1^0=2.5\), \(x_2^0=3.75\), with value \(z_0^R=59.5\). The most infeasible integer variable is \(x_1\), so two new subproblems are created, \(\mbox{IP}^1\) where \(x_1 \geq 3\) and \(\mbox{IP}^2\) where \(x_1 \leq 2\), and \(L=\{\mbox{IP}^1,\mbox{IP}^2\}\).
  2. Both problems in \(L\) have the same bound \(59.5\), so assume the algorithm arbitrarily selects \(\mbox{IP}^1\). The optimal solution to the LP relaxation of \(\mbox{IP}^1\) is \(x_1^1=3\), \(x_2^1=2.5\), with value \(z_1^R=59\). The most infeasible integer variable is \(x_2\), so two new subproblems of \(\mbox{IP}^1\) are created, \(\mbox{IP}^3\) where \(x_2 \geq 3\) and \(\mbox{IP}^4\) where \(x_2 \leq 2\), and now \(L=\{\mbox{IP}^2,\mbox{IP}^3, \mbox{IP}^4\}\).
  3. The algorithm next examines \(\mbox{IP}^2\), since this is the problem with the best bound. The optimal solution to the LP-relaxation is \(x_1^2=2\), \(x_2^2=4\), with value \(z_2^R=58\). Since \(x^2\) is integral feasible, \(\mbox{{\underline{$z$}}$_{ip}$}\) can be updated to \(58\) and \(\mbox{IP}^2\) is fathomed.
  4. Both of the two problems remaining in \(L\) have best bound greater than 58, so neither can yet be fathomed. Since these two subproblems have the same bound \(59\), assume the algorithm arbitrarily selects \(\mbox{IP}^3\) to examine next. The LP relaxation to this problem is infeasible, since it requires that \(x\) satisfy \(x_1 \geq 3\), \(x_2 \geq 3\) and \(5x_1+2x_2\leq 20\) simultaneously. Therefore, \(z_3^R=-\infty\), and this node can be fathomed by infeasibility.
  5. That leaves the single problem \(\mbox{IP}^4\) in \(L\). The solution to the LP relaxation of this problem is \(x_1^4=3.2\), \(x_2^4=2\), with value \(z_4^R=57.6\). Since \(z_4^R\leq\mbox{{\underline{$z$}}$_{ip}$}\), this subproblem can also be fathomed by bounds. The set \(L\) is now empty, so \(x^2\) is optimal for the integer programming problem \(\mbox{IP}^0\).




John Mitchell
2009-03-05