Binary Integer Programming

Binary Integer Programming

1. Concept

   • Variables
     • Restricted to be either 0 or 1
     • N-th variables are taken in decision values
   • Main Objective
     • Decision-making

2. Solving Algorithms

   • Egon Balas' Additive Method
     • Check the initial solution (0,0,..,0)
       • When
         • ZMax = ∞
         • K = 0
     • Branching
       • Create two new partial solutions
         • xk+1=1
         • xk+1=0 and k=k+1
     • Ending Solution
       • if Z< ZMax then ZMax=Z
         • End of solution
     • Sounding
       • If any constraint is satisfied
         • There is no feasible solution
   • Implicit Enumeration
     • Enumerate all solutions
       • Analize every combination
   • Branch and Bound

3. Applications

   • Project Selection
   • Energy Distribution
   • Investment Analysis
   • Knapsack Problem
   • Multiple Traveling Salesman Problem
   • Plant Building

4. Advantages

   • Covers a wide range of Application Problems
   • Problems may have prompt solutions

5. Software

   • IBM Cplex
   • Lingo
   • WinQSB
   • Gurobi

6. Disadvantages

   • Implicit Enumeration
     • Exponential complexity
   • Branch and Bound
     • May create pointless branches
     • Creates a considerable quantity of subproblems

Imágenes y archivos del mapa