A Column Generation Technique for the Computation of Stationary Points

摘要

In two recent papers, Eaves showed that Lemke's algorithm can be used to compute a stationary point of an affine function over a polyhedral set. This paper proposes an alternative method which is based on parametric principal pivoting. The proposed method involves solving systems of linear equations and parametric linear subprograms over the given polyhedral set. An obvious advantage of the method is that any special structure of the polyhedral set can be exploited profitably in the solution of the subprograms. (Author)