A combined gradient and feasible direction pivotal solution algorithm for general linear programming

We present an efficient gradient-feasible direction based algorithm for solving general linear programming (LP) problem. The algorithm consists of three phases. The initialization phase provides the initial tableau which may not have a full set of basis. The gradient phase uses a full gradient vector of the objective function to obtain a feasible vertex. This is then followed by the feasible direction method, which uses a reduced gradient based scheme that after the first move, proceeds along ever decreasing dimension faces of the feasible region, until an optimal vertex (if one exists) is reached. The algorithm works in the space of the original variables. The computations are based on Gauss–Jordan pivoting as used in the simplex method. The proposed solution algorithm in the worst case requires 2m iterations, m being the number of constraints including non-negativity condition on any variables. It is practical, easy for the user to understand, and contains strong theoretical components.