Implementing the simplex method as a cutting-plane method, with a view to regularization

We show that the simplex method can be interpreted as a cutting-plane method, assuming that a special pricing rule is used. This approach is motivated by the recent success of the cutting-plane method in the solution of special stochastic programming problems. We focus on the special linear programming problem of finding the largest ball that fits into a given polyhedron. In a computational study we demonstrate that ball-fitting problems have such special characteristics which indicate their utility in regularization schemes. Copyright Springer Science+Business Media New York 2013