Computational behavior of a feasible direction method for linear programming

Computational behavior of a feasible direction method for linear programming

0.00 Avg rating0 Votes
Article ID: iaor1989713
Country: Netherlands
Volume: 40
Issue: 3
Start Page Number: 322
End Page Number: 328
Publication Date: Jun 1989
Journal: European Journal of Operational Research
Authors: ,
Abstract:

The authors 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.

Reviews

Required fields are marked *. Your email address will not be published.