成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	李俊賢 Lee, Chun-Hsien
論文名稱：	應用子網路擴張流量方法求解最大流量問題之研究 Solving The Maximum Flow Problem by Augmenting Flows on Subnetworks
指導教授：	王逸琳 Wang, I-Lin
學位類別：	碩士 Master
系所名稱：	管理學院 - 工業與資訊管理學系 Department of Industrial and Information Management
論文出版年：	2009
畢業學年度：	97
語文別：	英文
論文頁數：	89
中文關鍵詞：	最大流量問題、網路最佳化、擴張流量、克西荷夫定律、最小平方對偶-主、等比例擴張
外文關鍵詞：	network optimization, maximum flow problem, augmenting flow, Kirchhoff's circuit laws, least-squares dual-primal algorithm, proportional arc augmenting
相關次數：	點閱：209 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

最大流量問題為一基本之網路最佳化問題，旨在於一具有流量上限的網路中尋找從起點到訖點間可流通之最大可能流量，此問題已有超過五十年以上的研究歷史。傳統的最大流量演算法大致可分為兩大類：其一為不斷自起點找出一條可擴張流量至訖點之擴張路徑來擴張流量；而另一則為先塞滿起點連結出去之弧，允許節點暫存流量，再將具有暫存流量的節點沿其鄰近之一條可行弧逐次擴張流量於其鄰近點，直至所有之暫存流量擴張至訖點或返回起點而止。這些解法在每次擴張流量時，皆僅能沿網路圖之單一路徑或單一弧進行，本論文以能一次即利用網路中所有的可行弧來擴張流量為目標，使用最短路徑所建構之子網路架構來擴張流量，提出三個新的具多項式時間複雜度之最大流量演算法。

第一個最大流量演算法根據可行子網路中各弧殘餘流量上限的比例來分配每次之擴張流量，稱為proportional arc augmenting (PAA) 演算法。PAA演算法依據可行子網路中各節點所連結出去之可行弧的殘餘流量上限比例，計算出該子網路所有弧之擴張流量向量δ，再根據此擴張流量向量計算出該次從起點到訖點之擴張流量，此種等比例擴張流量方式符合具較大流量上限之弧能擴張更多流量的直覺，並保證每次至少可塞滿一個節點。在一個具有n個節點及m條弧的網路上，PAA演算法可在O(n^2m)時間內算出其最大流量。此外，本論文亦提出一些加速PAA演算法實作效率之方法。

第二個最大流量演算法稱為flow splitting augmenting (FSA) 演算法，旨在以平分流量的方式，快速地將子網路中各節點所接收之流量依其連結出去之弧個數來平均分配，如此可保證每次擴張流量時至少會塞滿一條可行弧。在理論複雜度上，FSA演算法可在O(nm^2)時間內算出其最大流量。

第三個最大流量演算法以求解線性規劃時可避免退化問題之最小平方對偶-主 (least-squares dual-primal, LSDP)演算法為基礎，在最短路徑所建構之子網路架構上使用電路學的克西荷夫定律，計算子網路中每弧應該推送之單位流量比例以擴張流量，稱modified least-squares dual-primal (MLSDP)演算法。此演算法每次亦可保證塞滿一條節線，並可在O(nm^5)時間內算出其最大流量，解決了先前文獻中無法推估如何運用LSDP法求解最大流量問題之理論複雜度問題。由於此法必須重複計算克西荷夫定律之稀疏矩陣線性聯立方程式，因此在實作上我們亦使用專業的聯立方程式求解軟體以加快求解效率。

本論文所提出之三種最大流量演算法皆可能會得到非整數之最佳流量，因此我們提出一個流量分解的方式，以在O(m^2)時間內將其轉換為整數最佳流量。在求解效率測試上，我們將所提出之演算法與現今最常見之數種最大流量演算法在不同的模擬測試網路上做求解時間及運算次數之比較。測試結果顯示，雖然此三種新的演算法在平均求解表現上並不十分突出，我們仍可發現其求解機制可能會對某些特殊網路架構有利。最後，我們提出數種演算法效率改善之可能作法，並建議一些具挑戰性的未來研究方向。

The s-t maximum flow problem is a fundamental network optimization problem which computes for the largest amount of flow sent through a network from a source node s to a sink node t. This problem often appears in many business applications as an optimization subproblem, and has been investigated extensively over the recent five decades. Conventional maximum flow algorithms either augment flow via a simple path to t, or via admissible arcs from those nodes of excess flow to their neighbors at each iteration. In this thesis, we propose three new maximum flow algorithms that ship flow via all the arcs in an admissible subnetwork composed by shortest augmenting paths at each iteration.

With the intuition to ship more flow along more spacious admissible arcs at each iteration, our proposed proportional arc augmenting algorithm (PAA) calculates an
augmenting-flow vector δ along all arcs in an admissible subnetwork based on the proportion of the residual capacity for each arc emanating from a node to their sum. In particular, PAA ships as much flow as possible along the augmenting-flow vector until one admissible arc is saturated, then all of its neighbor admissible arcs are saturated as well. PAA iteratively saturates at least one node at each iteration, and calculates the maximum flow in polynomial time. Several speed-up techniques are also proposed to improve the practical efficiency of PAA.

In order to save more overhead than PAA in calculating a different δ while still shipping flow via all the admissible arcs at each iteration, we proposed flow splitting augmenting algorithm (FSA) which equally distributes all the flow entering a node to each of its outgoing arcs in an admissible subnetwork. FSA saturates at least one arc at each iteration, instead of one node as PAA. We also show FSA calculates the maximum flow in polynomial time.

Our third algorithm, called as modified least-squares dual primal algorithm(MLSDP), exploits the least-squares primal-dual algorithm that was designed for solving LPs without degenerate pivots. In particular, the augmenting-flow vector calculated by MLSDP guarantees nondegenerate pivots at each iteration, which may lead to fewer iterations of flow augmentation than other algorithms. Instead of solving a quadratic nonnegative least squares problem for calculating an augmenting-flow vector, MLSDP solves systems of linear equations composed by Kirchhoff's circuit laws. We show the polynomial-time complexity for MLSDP, and also suggest more efficient implementation that exploits sparse matrix operations.

All of our proposed maximum flow algorithms give fractional optimal flow, which can be further converted into integral optimal flow within polynomial-time by techniques based on flow decomposition. Comprehensive computational experiments have been conducted to analyze the practical efficiency of our proposed algorithms in comparison to several state-of-the-art maximum flow algorithms over several families of simulated networks. Although the results indicate our current implementations on proposed algorithms perform less efficient than the state-of-the-art preflow-push algorithms, we observe that our proposed algorithms tend to terminate in fewer iterations and make several speed-up suggestions for future research.

Contents
List of Tables...........................................iv
List of Figures...........................................v
Chapter 1. INTRODUCTION...................................1
1. Background and Motivation............................1
2. Objective and Proposed Approaches....................4
3. Scope and Limitations................................5
4. Overview of Thesis...................................6
Chapter 2. PRELIMINARIES..................................7
1. Notations and Definitions............................7
2. Network Simplex Methods..............................9
3. Augmenting Path Methods.............................10
4. Preflow Push Methods................................12
5. Scaling Methods.....................................13
6. Maximum Adjacency Ordering Methods..................14
7. Least-square Dual-primal Method.....................15
8. Summary.............................................21
Chapter 3. ALGORITHMS TO FAIRLY AUGMENT FLOWS............22
1. Proportional Arc Augmenting Algorithm (PAA).........22
1.1. Steps and Properties of PAA.......................23
1.2. Comparison of the Augmenting Flow Step between PAA and DA...................................................27
2. Complexity Analysis for PAA.........................28
3. An Illustrative Example for PAA.....................30
4. Converting Fractional Optimal Flow to Integral Optimal Flow.............................................32
5. Speed-up Techniques for PAA.........................34
5.1. Skipping Exhausted Nodes..........................35
5.2. Pushing and Pulling Flow Augmentations............36
5.3. A Scaling Phase Technique.........................39
6. Ideas of Flow Splitting.............................40
6.1. Flow Splitting Augmenting Algorithm (FSA).........41
6.2. Complexity Analysis for FSA.......................42
6.3. An Illustrative Example for FSA...................43
7. Summary.............................................45
Chapter 4. MODIFIED LEAST-SQUARES DUAL-PRIMAL METHOD.....47
1. Steps of MLSDP......................................47
2. Complexity Analysis for MLSDP.......................52
3. An Illustrative Example for MLSDP...................54
4. Another MLSDP Implementation........................57
5. Speed-up Techniques.................................59
6. Summary.............................................60
Chapter 5. COMPUTATIONAL EXPERIMENTS AND ANALYSES........61
1. Computational Setup.................................61
2. Problem Instances...................................62
3. Testings among Proposed Algorithms..................65
3.1. Comparing Different PAA Implementations...........66
3.2. Comparing PAA2 with FSA...........................66
3.3. Comparing PAA with MLSDP..........................69
4. Testings on Proposed Algorithms and Other Algorithms ..............................................70
5. Summary.............................................77
Chapter 6. CONCLUSIONS AND FUTURE RESEARCH...............78
1. Summary and Contributions...........................78
2. Suggestions for Future Research.....................81
2.1. Constructing Layered Networks More Efficiently....81
2.2. Augmenting Flows Along at most k Outgoing Arcs in PAA......................................................82
2.3. Running PAA for Fair Networks.....................82
2.4. Additional Information to Identify Appropriate Nodes and Arcs to Augment Flow by PAA....................83
2.5. Efficient Pushing and Pulling Flow Augmentations..83
2.6. Integrating PAA and Preflow Push Algorithms.......83
2.7. Path Flow Augmentations in MLSDP..................83
References...............................................86

List of Tables
1 Summary of maximum flow algorithms...................21
1 Comparing running time of PAA with its implementation algorithms...............................................67
2 Comparing total number of augmentations of PAA with its implementation algorithms............................67
3 Comparing PAA with FSA...............................68
4 Comparing PAA with MLSDP.............................70

List of Figures
1 A maximum flow example................................2
1 Constructing the residual network G(x)................8
2 An example of residual network and its corresponding admissible subnetwork.....................................9
3 Dinic's algorithm....................................11
4 An example of solving electron flow by using the Kirchhoff's laws.........................................17
5 DR algorithm.........................................18
6 An example of LSDP for max-flow problem..............20
1 Pseudo-code for constructing a layered network.......24
2 Pseudo-code to delete nodes not accessible from s or to t.....................................................24
3 Pseudo-code for calculating the augmenting-flow vector...................................................25
4 Pseudo-code for augmenting flow......................26
5 Proportional arc augmenting algorithm................27
6 An example of PAA for max-flow problem...............31
7 An example of converting fractional flow to integral flow.....................................................34
8 An example of storing additional informations to skip exhausted nodes..........................................35
9 The amount of flow augmented in each iteration (i.e. θ) for a given layered network...........................37
10 An example shows that pulling flow augmentation may augment more flow than pushing flow augmentation.........39
11 Proportional arc augmenting scaling algorithm.......40
12 Pseudo-code for splitting proportional flow.........41
13 Pseudo-code for augmenting split flow...............42
14 Flow splitting augmenting algorithm.................42
15 An example of FSA for max-flow problem..............44
1 Pseudo-code for constructing a layered network using for LSDP.................................................48
2 Pseudo-code for deleting nodes using for LSDP........49
3 Pseudo-code for calculating nonnegative electron flow.....................................................49
4 Pseudo-code for updating tree........................51
5 Pseudo-code for augmenting flow using for LSDP.......51
6 MLSDP algorithm......................................52
7 An example of MLSDP for max-flow problem-Iteration1..55
8 An example of MLSDP for max-flow problem-Iteration2..56
9 Pseudo-code for reconnecting arc.....................58
10 MLSDPI algorithm....................................58
1 Genrmf network.......................................63
2 The subnetwork N(1) of AK generator..................63
3 The subnetwork N(2) of AK generator..................64
4 Washington-10 network................................65
5 Acyclic-dense with equal capacity arcs network.......65
6 An example of layered network constructed from AK family...................................................69
7 Computational results on GENRMF-LONG family data.....72
8 Computational results on GENRMF-WIDE family data.....73
9 Computational results on AK family data..............74
10 Computational results on WAS-10 family data.........75
11 Computational results on ACU family data............76
1 An example of using path flows to calculate electron flow of each arc.........................................84
                                    

Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. Network flows: theory, algorithms, and applications, Prentice-Hall, New Jersey, 1993

Ahuja, R. K. and Orlin, J. B. A fast and simple algorithm for the maximum flow problem. Operations Research, 37, 748-759, 1989

Ahuja, R. K. and Orlin, J. B. Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems. Naval Research Logistics, 38, 413-430, 1991

Ahuja, R. K., Orlin, J. B. and Tarjan, R. E. Improved time bounds for the maximum flow problem. SIAM Journal on Scientific Computing. 18, 939-954, 1989

Armstrong, R. D., Chen, W., Goldfarb, D. and Jin, Z. Strongly polynomial dual simplex methods for the maximum flow problem. Mathematical Programming, 80, 17-33, 1998

Barnes, E., Chen, V., Gopalakrishnan, B. and Johnson, E. L. A least-squares primal-dual algorithm for solving linear programming problems. Operations research letters, 30, 289-294, 2002

Cerulli, R., Gentili, M. and Iossa, A. Efficient preflow-push algorithms. Computers and Operations Research, 35, 2694-2708, 2008

Chang, J. H. 2006. Solving the network flow problem by a least-squares primal-dual method. Unpublished master's thesis, National Chen Kung University.

Cheriyan, J., Hagerup, T. and Mehlhorn, K. An O(n^3/logn)-time maximum-flow algorithm. SIAM Journal on Scientific Computing. 25, 1144-1170, 1996

Cheriyan, J. and Maheshwari, S. N. Analysis of Preflow Push Algorithms for Maximum Network Flow. SIAM Journal on Computing, 6, 1057-1086, 1989

Cherkassky, B.V. and Goldberg A.V. On Implementing the Push-Relabel Method for the Maximum Flow Problem. Algorithmica, 19, 390-410, 1997

Cheung, T. Y. Computational Comparison of Eight Methods for the Maximum Network Flow Problem. ACM Transactions on Mathematical Software, 6, 1-16, 1980

Davis, T. A. and Duff, I. S. An unsymmetric-pattern multifrontal method for sparse LU factorization. SIAM Journal on Matrix Analysis and Applications, 18, 140-158, 1997

Davis, T. A. and Duff, I. S. A combined unifrontal/multifrontal method for unsymmetric sparse matrices. ACM Transactions on Mathematical Software, 25, 1-19,1999

Davis, T. A. A column pre-ordering strategy for the unsymmetric-pattern multifrontal method. ACM Transactions on Mathematical Software, 30, 165-195, 2004

Davis, T. A. Algorithm 832: UMFPACK, an unsymmetric-pattern multifrontal method. ACM Transactions on Mathematical Software, 30, 196-199, 2004

Davis, T. A. unsymmetric multifrontal sparse LU factorization package. available: http://www.cise.ufl.edu/research/sparse/umfpack

Dinic, E. A. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Mathematics Doklady, 11, 1277-1280, 1970

Dinitz, Y. Dinitz' Algorithm: The Original Version and Even's Version. Lecture Notes in Computer Science, 3895, 218-240, 2006

Edmonds, J. and Karp, R. M. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the Association for Computing Machinery, 19, 248-264, 1972

Even, S. Graph algorithms. Rockville, M.D.: Computer Science Press, 1979

Ford, L. R. and Fulkerson, D. R. Maximal flow through a network. Canadian Journal of Mathematics, 8, 399-404, 1956

Ford, L. R. and Fulkerson, D. R. Flows in networks. Princeton, N.J.: Princeton University Press, 1962

Fulkerson, D. R. and Dantzig, G. B. Computation of maximum flow in networks. Naval Research Logistics Quarterly, 2, 277-283, 1955

Fujishige, S. A maximum flow algorithm using MA ordering. Operations Research Letters, 31, 176-178, 2003

Fujishige, S. and Isotani, S. New maximum flow algorithms by MA orderings and scaling, Journal of the Operations Research, 46, 243-250, 2003

Gabow, H. N. Scaling Algorithms for Network Problems. Journal of Computer and System Sciences, 31, 148-168, 1985

Galil, Z. An O(V^(5/3)E^(2/3)) algorithm for the maximal flow problem, Acta Informatica, 14, 221-242, 1980

Galil, Z. and Naamad, A. An O(EVlog^2V) Algorithm for the Maximal Flow Problem, Journal of computer and system sciences, 21, 203-217, 1980

Gopalakrishnan, B., Barnes, E., Johnson, E. and Sokol, J. A least-squares network flow algorithm. Tech. Rep., Georgia Institute of Technology, 2004

Goldberg, A. V. 1985. A New Max-Flow Algorithm. Technical Report MIT/LCS/TM-291, Laboratory for Computer Science, M.I.T., Cambridge, MA

Goldberg, A.V. Network Optimization Library. available: http://www.avglab.com/andrew/soft.html

Goldberg, A.V. Synthetic Maximum Flow Families. available: http://www.avglab.com/andrew/CATS/maxflow_synthetic.html

Goldberg, A. V., Grigoriadis, M. D. and Tarjan, R. E. Use of dynamic trees in a network simplex algorithm for the maximum flow problem. Mathematical Programming, 50, 277-290, 1991

Goldberg, A. V. and Tarjan, R. E. A new approach to the maximum-flow problem. Proceedings of the 18th Association for Computing Machinery Symposium on the Theory of Computing, 136-146, 1986. Full paper in Journal of the Association for Computing Machinery, 35, 921-940, 1988

Goldfarb, D. and Grigoriadis, M. D. A computational comparison of the dinic and network simplex methods for maximum flow. Annals of Operations Research, 13, 83-123, 1988

Goldfarb, D. and Hao, J. A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n^2m) time. Mathematical Programming, 47, 353-365, 1990

Hu, T. C. Minimum-cost flows in convex-cost networks. Naval Research Logistics Quarterly, 13, 1-9, 1966

Johnson, D.S. and McGeoch, C.C. Network Flows and Matching: First DIMACS Implementation Challenge, American Mathematical Society, Providence, RI, 1993

Karzanov, A. V. Determining the maximal flow in a network by the method of preflows. Soviet Mathematics Doklady, 15, 434-437, 1974

Matsuoka, Y. and Fujishige, S. Practical efficiency of maximum flow algorithms using MA ordering and preflows. Journal of the Operations Research Society of Japan, 48, 297-307, 2005

Malhotra, V., Kumar, M. P. and Maheshwari, S. N. An O(|V|^3) algorithm for finding maximum flows in networks. Information Processing Letters, 7, 277-278, 1978

Nagamochi, H. and Ibaraki, T. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics, 5, 54-66, 1992

Nagamochi, H. and Ibaraki, T. Graph connectivity and its augmentation: applications of MA orderings. Discrete Applied Mathematics, 123, 447-472, 2002

Sedeño-Noda, A. and González-Martín, C. A O(nmlog(U/n)) Time Maximum Flow Algorithm. Naval Research Logistics, 47, 511-520, 2000

Setubal, J. S. Implementations and variations of a maximum-flow algorithm. Doctoral Thesis. UMI Order Number: UMI Order No. GAX93-12742., University of Washington, 1992

Shioura, A. The MA-ordering max-flow algorithm is not strongly polynomial for directed networks. Operations Research Letters, 32, 31-35, 2004

Sleator, D. D. and Tarjan, R. E. A data structure for dynamic trees. Journal of Computer and system Sciences, 24, 362-391, 1983

Tarjan, R. E. A simple version of Karzanov's blocking flow algorithm. Operations Research Letters, 2, 265--268, 1984

Wang, I.-L. On solving shortest paths with a least-squares primal-dual algorithm, Asia Pacific Operations Research, 2008 (to appear)

Wang, I.-L., Chang, C.H., Chen, Y.Y, and Kang, Y.C. A least-squares dual-primal algorithm for the maximum flow problem, Proceedings of the 3rd Annual Conference of the Operations Research Society at Taiwan (ORSTW), Chun-li, Taiwan, 2006.

The first DIMACS international algorithm implementation challenge: Network Flows and Matching, 1990, Available: ftp://dimacs.rutgers.edu/pub/netflow/.

校內：2012-07-27公開
校外：2012-07-27公開

簡易檢索 / 詳目顯示

相關論文