A feasible direction method for linear programming

Abstract

We discuss a finite method of a feasible direction for linear programming problems. The method begins with a feasible basic vector for the problem, constructs a profitable direction to move using the updated column vectors of the nonbasic variables eligible to enter this basic vector. It then moves in this direction as far as possible, while retaining feasibility. This move in general takes it though the relative interior of a face of th set of a feasible solutions. The final point, , obtained at the end of this move will not in general be a basic solution. Using the method then constructs a basic feasible solution at which the objective value is better than, or the same as that at . The whole process repeats with the new basic feasible solution. We show that this method can be implemented using basis inverses. Initial computer runs of this method in comparison with the usual edge following primary simplex algorithms are very encouraging.