A smooth penalty function algorithm for network-structured problems

We discuss the design and implementation of an algorithm for the solution of large scale optimization problems with embedded network structures. The algorithm uses a linear-quadratic penalty function to eliminate the side constraints and produces a differentiable, but non-separable, problem. A simplicial decomposition is subsequently used to decompose the problem into a sequence of linear network problems. Numerical issues and implementation details are also discussed. The algorithm is particularly suitable for vector architectures and was implemented on a CRAY Y-MP. We report very promising numerical results with a set of large linear multicommodity network flow problems drawn from a military planning application.