The role of the augmented system in interior point methods

We present a way to use the augmented system approach in interior point methods. We elaborate on the increased freedom in determining the pivot order which makes this approach computationally very competitive. This means that with the pivot search heuristics presented here, in most of the cases we can achieve a performance not worse than the AD^–1A^T method, and in several cases much better. In reality, the augmented system seems to be the only safe method in case of dense columns or ‘bad’ nonzero pattern. We found that both methods are important for their usefulness. Our implementation includes both. It is also equipped with an analyzer that is able to determine which of them to use. It is based on the evaluation of the nonzero pattern of the constraint matrix. We also point out that the treatment of free variables is also more efficient in the framework of the augmented system. We report on some very favorable computational experiences achieved with our implementation of the augmented system based on these ideas.