A regularized simplex method

In case of a special problem class, the simplex method can be implemented as a cutting-plane method that approximates a certain convex polyhedral objective function. In this paper we consider a regularized version of this cutting-plane method, and interpret the resulting procedure as a regularized simplex method. (Regularization is performed in the dual space and only affects the process through the pricing mechanism. Hence the resulting method moves among basic solutions.) We present favorable test results with this regularised simplex method. For general linear programming problems, we propose a Newton-type approach which requires the solution of a sequence of special problems.



View A regularized simplex method