zbMATH — the first resource for mathematics

Exploiting special structure in primal dual interior point methods. (English) Zbl 0770.90042
Summary: 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.

90C05 Linear programming
90B80 Discrete location and assignment
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI