Branch-and-Bound (Algorithm)

$\text{BRANCH-AND-BOUND}(LP)$:

1. Find a solution $\vec{a}$ to the linear relaxation of $LP$.
2. If $\vec{a}\in {\mathbb{Z}}^n$: Return solution $\vec{a}$
3. Otherwise choose a non-integer $x_i=a_i$ on which we branch.
   1. Let ${\vec{a}}_L=BRANCH-AND-BOUND(LP\cup \{x_i\le \lfloor a_i\rfloor \})$
   2. Let ${\vec{a}}_R=BRANCH-AND-BOUND(LP\cup \{x_i\ge \lceil a_i\rceil \})$
   3. If $f({\vec{a}}_L)\ge f({\vec{a}}_R)$: Return solution ${\vec{a}}_L$
   4. Else return solution ${\vec{a}}_R$