A modified prima-dual affine scaling algorithm for linear programming is presented. This modified algorithm generates an ellipsoid containing all optimal dual solutions at each iteration, then checks whether or not a dual hyperplane intersects this el...
A modified prima-dual affine scaling algorithm for linear programming is presented. This modified algorithm generates an ellipsoid containing all optimal dual solutions at each iteration, then checks whether or not a dual hyperplane intersects this ellipsoid. If the dual hyperplane has no intersection with this ellipsoid, its corresponding column must be optimal nonbasic. By condensing these columns, the size of LP problem can be reduced.