%A Armand A. Zakarian
%T Nonlinear Jacobi and Epsilon-Relaxation Methods for Parallel Network Optimization
%D October 20, 1995
%R 95-17
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X 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 a good empirical rate of convergence.
Parallel implementations of the algorithm on a 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 than 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 epsilon-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.