標題: A computationally efficient method for nonlinear multicommodity network flow problems
作者: Lin, SY
Lin, CH
交大名義發表
電控工程研究所
National Chiao Tung University
Institute of Electrical and Control Engineering
公開日期: 1-七月-1997
摘要: In this paper, we present a new method for solving nonlinear multicommodity network flow problems with convex objective functions. This method combines a well-known projected Jacobi method and a new dual projected pseudo-quasi-Newton (DPPQN) method which solves multicommodity flow quadratic subproblems induced in the projected Jacobi method. The DPPQN method is a dual Newton-type method that differs very much from the conventional Lagrangian Newton method; our method fully exploits the structural advantages of network-type linear equality constraints to obtain a constant sparse approximate Hessian matrix with a decoupling structure and includes a novel finite-iteration successive projection and (truncated) seal algorithm to resolve the difficulty caused by coupling capacity constraints. The DPPQN method also consists of two decomposition effects, the commodity decomposition effect and the are decomposition effect, which resolve the potential numerical difficulties caused by large dimensions. We show the convergence of our method including the convergence of the finite-iteration successive projection and (truncated) seal algorithm. Compared with the Frank-Wolfe with PARTAN algorithm in which a price-directive decomposition method is used to solve linearized multicommodity flow problems, our method is dramatically faster in terms of the CPU time on a Sparc-10 workstation at solving numerous nonlinear multicommodity network flow examples. (C) 1997 John Wiley & Sons, Inc.
URI: http://hdl.handle.net/11536/461
ISSN: 0028-3045
期刊: NETWORKS
Volume: 29
Issue: 4
起始頁: 225
結束頁: 244
顯示於類別:期刊論文


文件中的檔案:

  1. A1997XE31600006.pdf