A study on a class of linear integer programming problems
- The new technique
- Case studies
- Numerical illustrations
Linear programming (LP) is an optimization method applicable for the solution of problems in which the objective function and the constraints appear as linear functions of the decision variables. The constraint equations in a linear programming problem (LPP) may be in the form of equalities or inequalities. During the year 1800's the writings of the French Economist L.Walras (1834-1910) demonstrated the use of LP. The reinvention of the simplex algorithm by George B.Dantzig (1947) contributed to the development of LPP's with application to Economics, Business, Industrial Engineering, Operations research, Actuarial sciences and Game theory. We have other several methods like Charles M-technique, Two phase method, Revised simplex method, etc. for solving the LPP. In the paper  a method for solving integer quadratic goal programming problems, in which the objective function is a convex quadratic with linear constraints, has been discussed with the help of Gomory's cutting plane technique for integer program. The integer programming literature contains many algorithms for solving allinteger programming problems but, in general, existing algorithms are less than satisfactory even in solving problems of modest size.
[...] If a new node has integer values for the decision variables, update the current best lower bound as the lower bound of that node of its lower bound is greater than the previous current best lower node. If all terminal nodes are fathomed then 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. Otherwise, repeat the same procedure by identifying variable x k which has maximum fractional part as mentioned above until we get integer solution for ILPP. [...]
[...] Here in this paper we introduce a new technique of solving integer linear programming problem of two variables with various cases Preliminaries An integer linear programming problem (ILPP) is a special case of LPP in which some or all of the variables are required to be non-negative integers. An ILPP in which all variables are required to be integers is called a pure integer programming problem and some of the variables are required to be integers is called mixed. For solving ILPP, we have well known methods called Gomory's cutting plane and Branch and bound technique. [...]
[...] Case I - If the minimum of any one of xi 's or both are zeros, then choose the next minimum as xi and follow steps as in case I 3.1 Numerical Illustrations Problems based on case I Maximize z = 6 x1 + 8 x2 subject to 5 x1 + 10 x2 x1 + 4 x2 40, x x2 0 and are integers. Solution : Form the matrix table x Form the ratio table x1 x RHS x2 60/10 = 6 40/4 = 10 60/5 = 12 40/10 = 10 Here x1 = 10, x2 = 6 C = c2 ) = c1 x1 = c2 x2 = 48 x1 = x1 c1 c2 = 8 c1 x1 c2 x 2 = 60 48 = 12 > c1 c2 = 2 max( c1 x c 2 x 2 ) = max( 48, 48) =48 corresponds to x1 = 8 or x2 = 6. [...]