## December 22, 2011

### MB0048 [OPERATIONS RESEARCH] Set1 Q6

Q6. Describe the Integer Programming Problem. Describe the Gomory’s All-I.P.P. method for solving the I.P.P. problem.

Ans:
The Integer Programming Problem (IPP) is a special Linear Programming Problem where all or some variable are constrained to assume non-negative integer values. This type of problem has lot of application in business and industry where quite often discrete nature of the variable in involved in many decision making solution.

Gomory’s All- IPP Method: An optimum solution to an IPP is first obtained by using Simplex method ignoring the restriction of integral values. In optimum solution if the variables have integer values, the current solution will be described as optimum Integer solution. Otherwise the given IPP is modified by inserting by inserting a new constraint called Gomory’s or secondary constraint which represents necessary condition for integrability and  eliminate some non linear solution without loosing any integral solution. After adding the secondary constraint the problem is solved by dual Simplex method to get an optimum integral solution.

If all the values of the variable in the problem are integer, an optimum integer solution is obtained. Otherwise another new constraint is added to the modified LPP and the procedure is repeated. An optimum integer solution will be reached eventually after introducing enough new constraints to eliminate all the superior non integer solutions. The construction of additional constraints, called secondary or Gomory’s constraints is so very important that it needs special attention.

An integer programming problem can be described as follows:
Determine the value of unknowns x1, x2, … , xn
so as to optimize z = c1x1 +c2x2 + . . .+ cnxn
subject to the constraints
ai1 x1 + ai2 x2 + . . . + ain xn =bi , i = 1,2,…,m
and xj ³ 0 j = 1, 2, … ,n
where xj being an integral value for j = 1, 2, … , k ≤ n.

If all the variables are constrained to take only integral value i.e. k = n, it is called an all(or pure) integer programming problem. In case only some of the variables are restricted to take integral value and rest (n – k) variables are free to take any non negative values, then the problem is known as mixed integer programming problem.

The iterative procedure for the solution of an all integer programming problem is as follows:
Step 1: Convert the minimization I.P.P. into that of maximization, if it is in the minimization form. The integrality condition should be ignored.
Step 2: Introduce the slack or surplus variables, wherever necessary to convert the inequations into equations and obtain the optimum solution of the given L.P.P. by using simplex algorithm.
Step 3: Test the integrality of the optimum solution
a) If the optimum solution contains all integer values, an optimum basic feasible integer solution has been obtained.
b) If the optimum solution does not include all integer values then proceed onto next step.
Step 4: Examine the constraint equations corresponding to the current optimum solution. Let these equations be represented by ( i 0 , 1, 2 , ........, m1 )
Where n’ denotes the number of variables and m’ the number of equations.
Choose the largest fraction of bis ie to find {bi}i
Let it be [bk 1] or write is as Step 5: Express each of the negative fractions if any, in the k th row of the optimum simplex table as the sum of a negative integer and a nonnegative fraction.
Step 6: Find the Gomorian constraint Gsla ( 1 )= 