Integer Linear Programming

Integer Programming PPT

1. INTEGER PROGRAMMING

2. INTEGER PROGRAMMING – AN INTRODUCTION An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. All the LPP assumptions are inherited except divisibility. In 1958, Ralph E. Gomory transformed the field of integer programming when he published a short paper that described his cutting-plane algorithm for pure integer programs and announced that the method could be refined to give a finite algorithm for integer programming. Applications: 1. Knapsack Problem 2. Production Planning 3. Scheduling 4. Telecommunication Networks 5. Cellular Networks

3. TYPES OF INTEGER PROGRAMMING PROBLEMS Pure – Integer Problems - Require that all decision variables have integer solutions. Mixed – Integer Problems - Require some, but not all, of the decision variables to have integer values in the final solution, whereas others need not have integer values. 0-1 Integer Problems - Require integer variables to have value of 0 or 1, such as situations in which decision variables are of the yes – no type.

4. METHODS FOR SOLVING ILP PROBLEMS Rounding – off A non-integer solution (Enumeration Method) Developed by: A. M. Geoffrion Cutting – Plane Method Developed by: Ralph E. Gomory Branch and Bound Method Developed by: A. H. Land and A. G. Doing The Additive algorithm for Zero-One integer programming problem ( Balas ’ Method) Developed by: E. Balas

5. Maximize Profit = 7X 1 + 6X 2 Subject to: 2X 1 + 3X 2 <= 12 6X 1 + 5X 2 <= 30 X 1 , X 2 >= 0 and Integer 1. ENUMERATION METHOD

6. We found that optimal solution to LPP relaxation i.e. X 1 = 3.75 and X 2 = 1.5 do not have integer values. Rounding the values X 1 = 4 and X 2 = 2. However, this is not in feasible solution. Rounding X 2 down to 1 gives a feasible solution, but it may not be optimal. This could be solved using the enumeration method but it is generally not possible for large problems. 1. ENUMERATION METHOD - Continue

7. The Rounding solution of X 1 = 4 and X 2 = 1 gives a profit of 34 Optimal solution to integer programming problem is X 1 = 5 and X 2 = 0 with Maximum Z = 35 The optimal integer solution is less than the optimal LP solution. An integer solution can never be better than the LP solution. X 1 X 2 Z = 7X 1 + 6X 2 1 2 3 4 6 12 18 24 1 1 2 3 7 13 19 25 2 1 2 14 20 26 3 1 2 21 27 33 4 1 28 34 5 35* 1. ENUMERATION METHOD - Continue

8. An Algorithm for solving pure and mixed integer programming problems Developed by Ralph E. Gomory Steps to solve: 1. Relax the integer requirements. 2. Solve the resulting LP problem using Simplex Method 3. If all the basic variables have integer values, Optimality of the Integer programming problem is reached. So, go to step 7; otherwise go to step 4. 4. Examine the constraints corresponding to the current optimal solution. For each basic variable with non – integer solution in the current optimal table , find the fraction part f i , Therefore b i = [b i ] + f i where [b i ] is integer part and f i is fraction part of b i 5. Choose the largest fraction among various f i ; i.e. Max (f i ). Treat the constraint corresponding to the maximum fraction as the source row. Based on the source row, develop an additional constraint ( Gomory’s constraint/ fractional cut) as shown: -Summation[positive fraction for non-basic variables] + S i = -f i 6. Add the fractional cut as the last row in the latest optimal table and proceed further using dual simplex method, and find the new optimum solution. If the new optimum solution is integer then go to step 7; otherwise go to step 4. 7. Print the integer solution and optimal value 2. CUTTING – PLANE METHOD

9. Example: Max Z = 5X 1 + 8X 2 Subject to: X 1 + 2X 2 <= 8 4X 1 + X 2 <= 10 X 1 , X 2 >= 0 and Integers Solution: Introducing slack variables Max Z = 5X 1 + 8X 2 Subject to: X 1 + 2X 2 + S 1 = 8 4X 1 + X 2 + S 2 = 10 X 1 , X 2 >= 0 and Integers 2. CUTTING – PLANE METHOD - CONTINUE

10.   C j 5 8     C B X B X 1 X 2 S 1 S 2 RHS Ratio S 1 1 2 1 8 4 S 2 4 1 1 10 10 C j - Z j 5 8   Initial table Iteration 1   C j 5 8     C B X B X 1 X 2 S 1 S 2 RHS Ratio 8 X 2 0.5 1 0.5 4 8 S 2 3.5 -0.5 1 6 1.714286 C j - Z j 1 -4 32  

11. Iteration 2   C j 5 8   C B X B X 1 X 2 S 1 S 2 RHS 8 X 2 1 0.571429 -0.14286 3.142857 5 X 1 1 -0.14286 0.285714 1.714286 C j - Z j -3.85714 -0.28571 33.71429 Optimal solution to relaxation problem is achieved as C j – Z j <=0 for all j but both the variables have non – integer values so, X B b i [b i ] f i X 2 3.142857 3 0.142857 X 1 1.714286 1 0.714286 Maximum fraction is 0.714286 for X 1 the we will make Gomory’s fractional cut constraint corresponding to second row (1-0.14286)S 1 + 0.285714S 2 >= 0.714286 -0.85714S 1 - 0.285714S 2 <= -0.714286 -0.85714S 1 - 0.285714S 2 + S 3 = -0.714286 Adding the constraint into the problem and then 2. CUTTING – PLANE METHOD - CONTINUE

12. Cj 5 8 CB XB X1 X2 S1 S2 S3 RHS 8 X2 1 0.571429 -0.14286 3.142857 5 X1 1 -0.14286 0.285714 1.714286 S3 -0.85714 -0.28571 1 -0.71429 Cj - Zj -3.85714 -0.28571 33.7143 ( C j - Z j )/ y rj { y rj <0} - - 4.5 1 - 47.2 Cj 5 8 CB XB X1 X2 S1 S2 S3 RHS 8 X2 1 1 -0.5 3.5 5 X1 1 -1 1 1 S2 3 1 -3.5 2.5 Cj - Zj -3 -1 33 Iteration 3 Iteration 3 2. CUTTING – PLANE METHOD - CONTINUE

13. Now maximum fraction is 0.5 for X 2 so we will use first row to make fractional cut constraint then new constraint is -0.5S 3 + S 4 = -0.5 2. CUTTING – PLANE METHOD - CONTINUE Cj 5 8 CB XB X1 X2 S1 S2 S3 S4 RHS 8 X2 1 1 -0.5 3.5 5 X1 1 -1 1 1 S2 3 1 -3.5 2.5 S4 -0.5 1 -0.5 C j - Zj -3 -1 33 ( C j - Z j )/ y rj { y rj <0} 2 Cj 5 8 CB XB X1 X2 S1 S2 S3 S4 RHS 8 X2 1 1 -1 4 5 X1 1 -1 2 S2 3 1 -7 6 S4 1 -2 1 C j - Zj -3 -2 32 Iteration 5 Iteration 4

14. Optimal solution to integer programming is achieved as X 1 = 0 and X 2 = 6 and Max Z = 32 2. CUTTING – PLANE METHOD - CONTINUE

15. Creates and solves a sequence of sub – problems to the original problem that are increasingly more restrictive until an optimal solution is found. BRANCHING Selection of an integer value of a decision variable to examine for a possible integer solution to a problem. If the solution to the LPP contains non – integer values for some or all decision variables, then the solution space is reduced by introducing constraints with respect to anyone of those decision variables. If the value of the decision variable X 1 is 3.5, then two more problems will be created by using each of the following constraints. X 1 <= 3 and X 1 >=4. BOUND An upper or lower limit on the value of the objective function at a given stage of the analysis of an integer programming problem. Lower Bound: Value of the objective function corresponding to the integer parts of the decision variables in a node. Upper Bound: Value of the objective function corresponding to the LPP solution in that node. 3. BRANCH-AND-BOUND METHOD

16. FATHOMED NODE: A sub-problem is said to be fathomed if any of the following three conditions is true: The values of the decision variables of the problem are integer. The upper bound of the problem which has non-integer values for its decision variables is not greater than the current best lower bound. The problem has infeasible solution. This means that further branching is not necessary. CURRENT BEST LOWER BOUND: This is the best lower bound among the lower bounds of all the fathomed nodes. Initially, it is assumed as infinity for the root node. 3. BRANCH-AND-BOUND METHOD (continue)

17. Branch and bound algorithm applied to maximization problem Solve the given linear programming problem. Set, the current best lower bound Z B as ∞ Check, whether the problem has integer solution. If yes, print the current solution as the optimal solution and stop; Otherwise go to step 3. Identify the variable x k which has the maximum fractional part as the branching variable. (In case of tie, select the variable which has the highest objective function coefficient.) Create two more problems by including each of the following constraints to the current problem and solve them. X k <= [ X k ] X k >= [ X k ] + 1 If any one of the new sub – problems has infeasible solution or fully integer values for the decision variables, the corresponding node is fathomed. If a new node has integer values for the decision variables, update the current best lower bound as the lower bound of that node if its lower bound is greater than the previous current best lower bound. Are all terminal nodes fathomed? If yes, go to step – 7; otherwise, identify the node with the highest lower bound and go to step – 3. Select the solution of the problem with respect to the fathomed node whose lower bound is equal to the current best lower bound as the optimal solution. 3. BRANCH-AND-BOUND METHOD (continue)

18. Example: Max Z = 10X 1 + 20X 2 Subject to: 6X 1 + 8X 2 <= 48 X 1 + 3X 2 <= 12 X 1 , X 2 >= 0 and Integers 3. BRANCH-AND-BOUND METHOD (continue) Max Z = 96 at X 1 = 4.8 and X 2 = 2.4 Z upper = 96 Z lower = 80 Maximum fraction is 0.8 for X 1 Sub-Problem 1: X 1 <= 4 Sub-Problem 2: X 1 >= 5 Extreme Points Z = 10X 1 + 20X 2 A (0, 4) 80 B(4.8, 2.4) 96 C(8, 0) 80

19. Sub-Problem 1: X 1 >= 5 Z upper = 95 at X 1 = 5 and X 2 = 2.25 X 2 is not integer then Z lower = 80 Extreme Points Z = 10X 1 + 20X 2 A (5, 0) 50 B(5, 2.25) 95 C(8, 0) 80 3. BRANCH-AND-BOUND METHOD (continue)

20. Sub-Problem 2: X 1 <= 4 Z upper = 93.333 at X 1 = 4 and X 2 = 2.667 X 2 is not integer then Z lower = 80 Z lower is same for both problems but Z upper is highest in sub-problem 1 So, Sub-Problem 3: X 2 <= 2 and Sub-Problem 4: X 2 >= 3 Extreme Points Z = 10X 1 + 20X 2 A (0, 4) 80 B(4, 2.667) 93.333 C(4, 0) 40 3. BRANCH-AND-BOUND METHOD (continue)

21. Sub-Problem 3: X 2 >= 3 No feasible solution exists. So, sub – problem 4 is infeasible problem and this node is fathomed Now, we will make branches of Sub – problem 2. Sub-Problem 5: X 2 <= 2 and Sub-Problem 6: X 2 >= 3 3. BRANCH-AND-BOUND METHOD (continue)

22. Sub-Problem 4: X 2 <= 2 Z upper = 93.333 at X 1 = 5.333 and X 2 = 2 X 1 is not integer then Z lower = 90 Extreme Points Z = 10X 1 + 20X 2 A (5, 0) 50 B(5, 2) 90 C(5.333, 2) 93.333 D(8,0) 80 3. BRANCH-AND-BOUND METHOD (continue)

23. Sub-Problem 5: X 2 <= 2 Z upper = 60<80 at X 1 = 4 and X 2 = 2 X 2 is not integer then Z lower = 60 So, it is fathomed. Extreme Points Z = 10X 1 + 20X 2 A (0, 2) 20 B(4, 2) 60 C(4, 0) 40 3. BRANCH-AND-BOUND METHOD (continue)

24. Sub-Problem 5: X 2 >= 3 Z upper = Z lower = 90 at X 1 = 4 and X 2 = 2 Both variables have integer values. So, it is feasible solution. And this node is terminated. Sub – Problem 3 will be sub divided. Extreme Points Z = 10X 1 + 20X 2 A (0, 4) 60 B(3, 3) 90 C(0, 3) 60 3. BRANCH-AND-BOUND METHOD (continue)

25. Max Z = 10X 1 + 20X 2 Subject to: 6X 1 + 8X 2 <= 48 X 1 + 3X 2 <= 12 X 1 , X 2 >= 0 Max Z = 95 X 1 = 4.8, X 2 = 2.4 Z lower = 80 Max Z = 10X 1 + 20X 2 S.t. 6X 1 + 8X 2 <= 48 X 1 + 3X 2 <= 12 X 1 <=4 X 1 , X 2 >= 0 Max Z = 10X 1 + 20X 2 S.t. 6X 1 + 8X 2 <= 48 X 1 + 3X 2 <= 12 X 1 >=5 X 1 , X 2 >= 0 X 1 >=5 X 1 <=4 Sub – Problem 1 Sub – Problem 2 Z upper = 95 X 1 = 5, X 2 = 2.25 Z lower = 80 Z upper = 93.333 X 1 = 4 and X 2 = 2.667 Z lower = 80 Max Z = 10X 1 + 20X 2 S.t. 6X 1 + 8X 2 <= 48 X 1 + 3X 2 <= 12 X 1 >=5 X 2 >=3 X 1 , X 2 >= 0 Max Z = 10X 1 + 20X 2 S.t. 6X 1 + 8X 2 <= 48 X 1 + 3X 2 <= 12 X 1 >=5 X 2 <=2 X 1 , X 2 >= 0 Sub – Problem 3 Sub – Problem 4 X 2 >=3 Max Z = 10X 1 + 20X 2 S.t. 6X 1 + 8X 2 <= 48 X 1 + 3X 2 <= 12 X 1 <=4 X 2 >=3 X 1 , X 2 >= 0 Max Z = 10X 1 + 20X 2 S.t. 6X 1 + 8X 2 <= 48 X 1 + 3X 2 <= 12 X 1 <=4 X 2 <=2 X 1 , X 2 >= 0 Sub – Problem 5 Sub – Problem 6 X 2 <=2 X 2 <=2 X 2 >=3 Z upper = 93.333 X 1 = 5.333 X 2 = 2 Z lower = 90 Infeasible Problem Fathomed Z upper = 90 X 1 = 3 X 2 = 3 Z lower = 90 Z upper = 60 X 1 = 4 X 2 = 2 Z lower = 60 Feasible Solution Feasible Solution It will be terminate at X 1 = 5 and X 2 = 2 with Z = 90

26. 3. BALAS’ ALGORITHM

27. THANK YOU