New preconditioners for KKT systems of network flow problems

被引:16
作者
Frangioni, A
Gentile, C
机构
[1] Univ Pisa, Dipartimento Informat, I-56125 Pisa, Italy
[2] CNR, Ist Anal Sistemi & Informat Antonio Ruberti, I-00185 Rome, Italy
关键词
min cost flow problems; interior point algorithms; preconditioned conjugated gradient method; triangulated graphs;
D O I
10.1137/S105262340240519X
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We propose a new set of preconditioners for the iterative solution, via a preconditioned conjugate gradient (PCG) method, of the KKT systems that must be solved at each iteration of an interior point (IP) algorithm for the solution of linear min cost flow (MCF) problems. These preconditioners are based on the idea of extracting a proper triangulated subgraph of the original graph which strictly contains a spanning tree. We de. ne a new class of triangulated graphs, called brother-connected trees (BCTs), and discuss some fast heuristics for finding BCTs of "large" weight. Computational experience shows that the new preconditioners can complement tree preconditioners, outperforming them both in iterations count and in running time on some classes of graphs.
引用
收藏
页码:894 / 913
页数:20
相关论文
共 26 条
[1]  
Ahuja RK, 1993, NETWORK FLOWS THEORY
[2]  
Anderson W. N., 1985, Linear Multilinear Algebra, V18, P141, DOI [10.1080/03081088508817681, DOI 10.1080/03081088508817681]
[3]  
BERN M, UNPUB SIAM J MATRIX
[4]   A specialized interior-point algorithm for multicommodity network flows [J].
Castro, J .
SIAM JOURNAL ON OPTIMIZATION, 2000, 10 (03) :852-877
[5]  
Chen DR, 2003, ELECTRON T NUMER ANA, V16, P30
[6]  
CVETKOVIC DM, 1979, SPECTRA GRAPHS
[7]   Spectral analysis of (sequences of) graph matrices [J].
Frangioni, A ;
Capizzano, SS .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2001, 23 (02) :339-348
[8]  
FRANGIONI A, 2000, 539 IASICNR
[9]  
Gremban K. D., 1995, Proceedings 9th International Parallel Processing Symposium (Cat. No.95TH8052), P65, DOI 10.1109/IPPS.1995.395915
[10]   A study of preconditioners for network interior point methods [J].
Júdice, JJ ;
Patricio, J ;
Portugal, LF ;
Resende, MGC ;
Veiga, G .
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2003, 24 (01) :5-35