A primal-dual path-following algorithm that applies directly to a line
ar 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 boun
ds, variable upper bounds, and block diagonal structure. We also show
how the structure of time-staged problems and network flow problems ca
n be exploited, especially on a parallel computer. Finally, using our
algorithm, we obtain a complexity bound of 0(square-root n ds2 log(nka
ppa)) for transportation problems with s origins, d destinations (s <
d), and n arcs, where kappa is the maximum absolute value of the input
data.