Nonlinear Jacobi and E-Relaxation Methods for Parallel Network Optimization

Abstract

In this thesis we develop an efficient decomposition method for large-scale convex cost multi-commodity network flow problems. The coupling constraints are moved to the objective function via augmented Lagrangian terms. A nonlinear Jacobi algorithm is then used to solve the resulting program in parallel in a fork-join manner. Several approaches to solving the coordination problem (corresponding to the join phase are investigated. In particular, a coordination method is developed that combines excellent parallel efficiency and low communication overhead with good empirical rate of convergence. parallel implementations of the algorithm on the Thinking Machines CM-5 supercomputer and a cluster of workstations running PVM demonstrate that it is competitive or superior to the best known methods. We are able to solve linear multi-commodity problems with over 200,000 variables in less that 15 minutes. The specific form of the non-strictly-convex subproblems (corresponding to the fork phase) motivates us to develop a relaxation method for separable convex network flow problems that is well-suited for problems with large variations in the magnitude of the nonlinear cost terms. The arcs are partitioned into two sets, one of which contains only arcs corresponding to strictly convex costs. The algorithm adjusts flows on the other arcs whenever possible, and terminates with primal dual pairs that satisfy complementary slackness on the strictly convex arc set and E-complementary slackness on the remaining arcs. An asynchronous parallel variant of the method is also developed. Computational results demonstrate that the method is significantly more efficient on quadratic ill-conditioned networks than existing methods, solving problems with several thousand nonlinear arcs in one second or less.