Computational behavior of a feasible direction method for linear programming

Abstract

We discuss a finite method of feasible directions for linear programs. The method begins with a BFS (basic feasible solution) and constructs a profitable direction by combining the updated columns of several nonbasic variables eligible to enter. Moving in this direction as far as possible, while retaining feasibility, leads to a point which is not in general a basic solution of the original problem, but corresponds to a BFS of an augmented problem with a new column. So this is called an interior move or a column adding move. Next we can either carry another interior move, or a reduction process which starts with the present feasible solution and leads to a BFS of the original problem with the same or better objective value. We show that interior moves and reduction processes can be mixed in many ways leading to different methods, all of which can be implemented by maintaining the basis inverse or a factorization of it. Results of a computational experiment are presented.