IP2

Balas Additive Algorithm for Binary Integer Programming

We will use the Balas Additive Algorithm to solve the following problem:

Minimize: Z = 3 x₁ + 5 x₂ + 6 x₃ + 9 x₄ + 10 x₅ + 10 x₆

Subject to:

(1) -2 x₁ + 6 x₂ - 3 x₃ + 4 x₄ + x₅ - 2 x₆ ≥ 2

(2) -5 x₁ - 3 x₂ + x₃ + 3 x₄ - 2 x₅ + x₆ ≥ - 2

(3) 5 x₁ - x₂ + 4 x₃ - 2 x₄ + 2 x₅ - x₆ ≥ 3

and  xj binary for = 1, 2,....6

Recall that the Balas Additive Algorithm uses the depth-first node selection strategy.

Also, notice that the terms in the objective function are written in increasing order, and that it is a minimization problem. So having x₁=0 and  x₂=1 is worse than having x₁=1 and x₂=0, etc.