### IP3

## 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