94-21 An Interior Point Methodd for Bordered Block Diagonal Linear Programs

DIMACS TR: 94-21

An Interior Point Methodd for Bordered Block Diagonal Linear Programs

Authors: M.D. Grigoriadis, L.G. Khachiyan

ABSTRACT
This paper presents an interior point method for solving a {\it bordered block diagonal} linear program which consists of a number of disjoint blocks, pcoupled by a total of $p$ variables and constraints. This structure includes the well-known block-angular and dual block-angular structures, as well as their special cases, such as staircase problems, generalized bounds and multicommodity flows. When $p$ is small relative to the total dimension the problem, the method achieves a substantial speed-up relative to other general- purpose methods.

Paper not available.

DIMACS Home Page