Early Stopping Heuristics that Compute Optimal Solutions for Interior-Point Linear Programming Algorithms

As Karmarkar has remarked, knowledge of which inequalities in a linear programming problem can be slack in an optimal solution should be enough to let one compute such a solution. Interior- point algorithms for linear programming often quickly identify the set S of possibly slack inequalities. 

The same linear algebraic machinery one needs for carrying out these algorithms can be used to check whether one has correctly identified S. Computational evidence on a dual variant of Karmarkar's algorithm suggests one can often compute an optimal solution with relatively little overhead.