On combined phase 1-phase 2 projective methods for linear programming

We compare the projective methods for linear programming due to de Ghellinck and Vial, Anstreicher, Todd, and Fraley. These algorithms have the feature that they approach feasibility and optimality simultaneously, rather than requiring an initial feasible point. We compare the directions used in these methods and the lower-bound updates employed. In many cases the directions coincide and two of the lower-bound updates give the same result. It appears that Todd's direction and Fraley's lower-bound update have slight advantages, and this is borne out in limited computational testing.This research was partially supported by NSF Grant DMS-8904406 and by ONR Contract N00004-87-K0212. The computations were carried out in the Cornell Computational Optimization Laboratory with support from NSF Grant DMS-8706133.