Dakin's Algorithm for Mixed Integer LPs

Dakin's algorithm is a version of branch and bound especially for linear programs that have at least one integer or binary variable (these are called mixed integer linear programs) . We will use Dakin's Algorithm to solve the following mixed integer linear programming problem:

Maximize : Z = 8x₁ + 5x₂

Subject to:

x₁ + x₂ ≤ 6

9 x₁ + 5 x₂ ≤ 45

x₁ , x₂ are integer and non-negative