A ``build-down'' scheme for linear programming (Q912758)

The author proposes a so-called build-down scheme for the Karmarkar algorithm and the simplex method. The scheme starts with the candidate set of all columns of the constraint matrix, then constructs a dual ellipsoid containing all optimal dual solutions. A pricing rule is developed for checking whether or not a dual hyperplane corresponding to a column intersects the containing ellipsoid. If the dual hyperplane has no intersection with the ellipsoid, its corresponding column will not appear in any of the optimal bases, and can be eliminated from the candidate set. Numerical experiences are not reported.