Authors: Dhananjay P. Mehendale
Comments: 40 Pages
In this paper we propose a new algorithm for linear programming. This new algorithm is based on treating the objective function as a parameter. We form a matrix using coefficients in the system of equations consisting objective equation and equations obtained from inequalities defining constraint by introducing slack/surplus variables. We obtain reduced row echelon form for this matrix containing only one variable, namely, the objective function itself as an unknown parameter. We analyze this matrix in the reduced row echelon form and develop a clear cut method to find the optimal solution for the problem at hand, if and when it exists. We see that the entire optimization process can be developed through the proper analysis of the said matrix in the reduced row echelon form. From the analysis of the said matrix in the reduced row echelon form it will be clear that in order to find optimal solution we may need carrying out certain processes like rearranging of the constraint equations in a particular way and/or performing appropriate elementary row transformations on this matrix in the reduced row echelon form. These operations are mainly aimed at achieving nonnegativity of all the entries in the columns corresponding to nonbasic variables in this matrix or its submatrix obtained by collecting certain rows of this matrix (i.e. submatrix with rows having negative coefficient for parameter d, which stands for the objective function as a parameter for maximization problem and submatrix with rows having positive coefficient parameter d, again representing the objective function as a parameter for minimization problem). The care is to be taken so that the new matrix arrived at by rearranging the constraint equations and/or by carrying out suitable elementary row transformations must be equivalent to original matrix. This equivalence is in the sense that all the feasible solution sets for the problem variables obtained for different possible values of d with original matrix and transformed matrix are same. We then proceed to show that this idea naturally extends to deal with nonlinear and integer programming problems. For nonlinear and integer programming problems we use the technique of Grobner bases (since Grobner basis is an equivalent of reduced row echelon form for a system of nonlinear equations) and the methods of solving linear Diophantine equations (since the integer programming problem demands for optimal integer solution) respectively.
Category: Data Structures and Algorithms