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, , is presented. This algorithm explicitly handles upper bounds, generalized upper bounds, variable upper bounds, and block diagonal structure. The authors also show how the structure of time-staged problems and network flow problems can be exploited, especially on a parallel computer. Finally, using the present algorithm, they obtain a complexity bound of for transportation problems with s origins, destinations , and n arcs, where is the maximum absolute value of the input data.