No Title

Illustrative Example of Branch-and-Bound
John Mitchell

$\begin{displaymath} \begin{array}{lrcrclrr} \mbox{maximize} & 13x_1 & + & 8x_2 \... ...5}{l}{\phantom{00}\mbox{$x_1,\ x_2$\space 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:

L is the set of active nodes.
$\mbox{{\underline{$z$ }}$_{ip}$ }$ is the value of the best known integer solution. This is initialized to $-\infty$ .
z_i^R is the value of the relaxation of problem $\mbox{IP}^i$ .

Progress of the algorithm:

1.: Initially, L consists of just the problem $\mbox{IP}^0$ . The solution to the LP relaxation is x₁⁰=2.5, x₂⁰=3.75, with value z₀^R=59.5. The most infeasible integer variable is x₁, 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₁¹=3, x₂¹=2.5, with value z₁^R=59. The most infeasible integer variable is x₂, 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₁²=2, x₂²=4, with value z₂^R=58. Since x² 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₁⁴=3.2, x₂⁴=2, with value z₄^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² is optimal for the integer programming problem $\mbox{IP}^0$ .

About this document ...

Next: About this document ...

John E Mitchell
2001-03-22