Editing Branch and bound (section)

== Optimization Example ==
Branch and bound can be used to solve this problem

Maximize <math>Z=5x_1+6x_2</math> with these constraints

<math>x_1+x_2\leq 50</math>

<math>4x_1+7x_2\leq280</math>

<math>x_1, x_2\geq0</math>

<math>x_1</math> and <math>x_2</math> are integers. 

The first step is to relax the integer constraint. We have two extreme points for the first equation that form a line: <math>\begin{bmatrix} x_1  \\ x_2 \end{bmatrix}=\begin{bmatrix}50 \\0\end{bmatrix}</math> and <math>\begin{bmatrix}0 \\50\end{bmatrix}</math>. We can form the second line with the vector points <math>\begin{bmatrix}0\\40\end{bmatrix}</math> and <math>\begin{bmatrix} 70\\0\end{bmatrix}</math>. 
[[File:Branch and Bound optimization example with linear constraints in BricsCad Ultimate Academic Edition.png|thumb|the two lines.]]
The third point is <math>\begin{bmatrix}0\\0\end{bmatrix}</math>. This is a [[Convex hull|convex hull region]] so the solution lies on one of the vertices of the region. We can find the intersection using row reduction, which is <math>\begin{bmatrix}70/3\\80/3\end{bmatrix}</math>, or <math>\begin{bmatrix} 23.333\\26.667\end{bmatrix}</math> with a value of 276.667. We test the other endpoints by sweeping the line over the region and find this is the maximum over the reals.  

We choose the variable with the maximum fractional part, in this case <math>x_2</math> becomes the parameter for the branch and bound method. We branch to <math>x_2\leq26</math> and obtain 276 @ <math>\langle 24,26\rangle</math>. We have reached an integer solution so we move to the other branch <math>x_2\geq27</math>. We obtain 275.75 @<math>\langle 22.75, 27\rangle</math>. We have a decimal so we branch <math>x_1</math> to <math>x_1\leq22</math> and we find 274.571 @<math>\langle 22,27.4286\rangle</math>. We try the other branch <math>x_1\geq23</math> and there are no feasible solutions. Therefore, the maximum is 276 with <math>x_1\longmapsto 24</math> and <math>x_2\longmapsto 26</math>.