Dhananjay P. Mehendale. New Algorithms: Linear, Nonlinear, and Integer Programming
Natural Sciences / Mathematics / Computation
Submitted on: Jan 31, 2013, 03:16:23
Description: 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. 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.