Exploiting Special Structure in Primal Dual Interior Point Methods

This paper examines special sparsity structures in linear programs that can accelerate calculations in the primal dual method. Our results extend previous research by quantifying more precisely conditions for retaining sparsity during iterations. Special structures that meet these conditions include simple upper bounds, variable upper bounds, and chained upper bounds. We describe an implementation and illustrate the benefits for the uncapacitated facility location problem.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.