A specialized interior-point algorithm for multicommodity network flows

作     者：Castro, J 

作者机构：Univ Politecn Cataluna Stat & Operat Res Dept E-08028 Barcelona Spain 

出 版 物：《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期：2000年第10卷第3期

页      面：852-877页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：interior-point methods linear programming multicommodity flows network programming 

摘      要：Despite the efficiency shown by interior-point methods in large-scale linear programming, they usually perform poorly when applied to multicommodity ow problems. The new specialized interior-point algorithm presented here overcomes this drawback. This specialization uses both a preconditioned conjugate gradient solver and a sparse Cholesky factorization to solve a linear system of equations at each iteration of the algorithm. The ad hoc preconditioner developed by exploiting the structure of the problem is instrumental in ensuring the efficiency of the method. An implementation of the algorithm is compared to state-of-the-art packages for multicommodity flows. The computational experiments were carried out using an extensive set of test problems, with sizes of up to 700,000 variables and 150,000 constraints. The results show the effectiveness of the algorithm.