Parametric Programming and the Primal-Dual Algorithm

Abstract

This paper studies the close relation between the Gass-Saaty parametric programming algorithm and the “primal-dual” procedures recently exploited by Dantzig, Fokd, and Fulkerson. It is shown that the two procedures are equivalent. The possibility of eliminating the two-phase character of the simplex method using these techniques is discussed. Finally, the application of the techniques to problems with special structure is considered.