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 j = 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.



Popular posts from this blog

Contents

Chapter 1: Introduction.  An introduction to the process of optimization and an overview of the major topics covered in the course.  Last revision: December 2020 . Chapter 2: Introduction to Linear Programming.  The basic notions of linear programming and the simplex method. The simplex method is the easiest way to provide a beginner with a solid understanding of linear programming.  Last revision: December 2020. See animation  LP1 . A good  article on formulating LPs  by Gerry Brown and Rob Dell. Example questions with solutions . March 4, 2021. Chapter 3: Towards the Simplex Method for Efficient Solution of Linear Programs.  Cornerpoints and bases. Moving to improved solutions.  Last revision: December 2020 . See animation  LP2 . Chapter 4: The Mechanics of the Simplex Method.  The tableau representation as a way of illustrating the process of the simplex method. Special cases such as degeneracy and unboundedness.  Last revision: December 2020. See animation  LP3 . Example questions
Read more