EXPLOITING SPECIAL STRUCTURE IN A PRIMAL DUAL PATH-FOLLOWING ALGORITHM

A primal-dual path-following algorithm that applies directly to a linear program of the form, min{c(t)x\Ax = b, Hx less-than-or-equal-to u, x greater-than-or-equal-to 0, X is-an-element-of R(n)}, is presented. This algorithm explicitly handles upper bounds, generalized upper bounds, variable upper bounds, and block diagonal structure. We also show how the structure of time-staged problems and network flow problems can be exploited, especially on a parallel computer. Finally, using our algorithm, we obtain a complexity bound of 0(square-root n ds2 log(nkappa)) for transportation problems with s origins, d destinations (s < d), and n arcs, where kappa is the maximum absolute value of the input data.