Branch-and-bound example

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:

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

Progress of the algorithm:

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\}$ .
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\}$ .
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.
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.
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$ .

About this document ...

John Mitchell
2009-03-05