簡易檢索 / 詳目顯示

回結果列表
研究生： 張正翰
Chang, Jeng-Han
論文名稱： 以最小平方主對偶演算法求解網路問題
Solving the network flow problem by a least-squares primal-dual method
指導教授： 王逸琳
Wang, I-Lin
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業與資訊管理學系
Department of Industrial and Information Management
論文出版年： 2006
畢業學年度： 94
語文別： 英文
論文頁數： 58
中文關鍵詞： 主對偶演算法 、非負最小平方和 、退化 、最大流量問題 、最小成本流量問題 、網路最佳化
外文關鍵詞： degeneracy, network optimization, maximum flow problem, nonnegative least-squares, minimum cost flow problem, primal-dual algorithm
相關次數： 點閱：156  下載：4 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 網路問題通常可被視為具有特殊限制式結構的線性規劃問題，因此一般用來求解線性規劃問題的方法，亦可被應用於求解網路問題。其中，「最小平方主對偶演算法」是最近被提出的一種線性規劃問題的有效解法，該演算法藉由多次地求解一最小非負平方的子問題來改善其對偶解，並可避免在求解過程中陷入退化解而停滯不前，因此可用比傳統的單體法(simplex method) 更少的計算迴圈來求得最佳解。

    本研究將根據「最小平方主對偶演算法」的概念，發展一套求解網路問題的圖形化演算法，並探討如何有效地取得初始對偶可行解，以及如何求解具有流量上限的最小流量成本問題。此外，我們亦將主問題與對偶問題的角色對調，提出一套「最小平方對偶主演算法」。並發現若以該演算法求解最大流量問題時，若將各弧上的單位流量成本視為弧上兩端點的電動勢，則原先所求解的非負最小平方子問題，可視為在一個內含二極體電路上求解其電流之問題。易言之，電路學中的柯西赫夫定律可被用來求解最小平方對偶主演算法中的非負最小平方和問題。因此，最大流量問題與最小流量成本問題皆可利用最小平方對偶主演算法，結合柯西赫夫定律，來避免退化過程並有效求解。

    The network flow problem is a specialized Linear Programming problem (LP) due to its special constraint structure. An LP solution method may have a more efficient implementation when applied for solving the network flow problem. Recently, a new primal-dual algorithm called the least-squares primal-dual (LSPD) method has been proposed to solve LPs with good performance ince it guarantees nondegenerate pivoting in each iteration. In each prmial-dual iteration, the LSPD algorithm solves a nonnegative least squares (NNLS) subproblem to obtain an improving direction for its dual variables.

    In this thesis, we develop techniques related with the LSPD method for solving network flow problems. Issues regarding e±cient ways to obtain an initial dual feasible solution and techniques to deal with capacitated network flow problems will be investigated. We also propose a new least-squares dual-primal (LSDP) algorithm
    which differs from the LSPD algorithm in exchanging the roles of the primal and dual formulations. When solving for the max-flow problem, the NNLS subproblem in our LSDP algorithm can be treated as an algorithm to calculate the current on an electrical network with diodes, where the unit-flow cost associated with an arc can be treated the electrical potential. Thus the Kirchhoff's law can be applied to solve the NNLS subproblem. Similar techniques can be applied to solve the MCF problem.

    ACKNOWLEDGEMENTS : : : : : : : : : : : : : : : : : : : : : : : : : : : : i LIST OF FIGURES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : iv CHAPTER I. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 1.1 Background and motivation . . . . . . . . . . . . . . . . . . . . . .1 1.2 Objective and proposed approaches . . . . . . . . . . . . . . . . . .5 1.3 Scope and limitation . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Overview of thesis . . . . . . . . . . . . . . . . . . . . . . . . . 6 II. LITERATURE REVIEW . . . . . . . . . . . . . . . . . . . . . . . . . .8 2.1 Minimum cost network flow problem . . . . . . . . . . . . . . . . . .8 2.1.1 Notation and formulations . . . . . . . . . . . . . . . . . . . . .9 2.1.2 Solution properties . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.3 Capacitated and uncapacitated MCF . . . . . . . . . . . . . . . . 12 2.2 Review of the solution methods for solving the MCF problem . . . . .13 2.2.1 Network simplex algorithm and the degeneracy issues . . . . . . . 13 2.2.2 Generic primal-dual algorithm . . . . . . . . . . . . . . . . . . 16 2.3 Review of the least-squares related solution methods for MCF . . . .19 2.3.1 Least-squares primal-dual algorithm . . . . . . . . . . . . . . . 20 2.3.2 Least-squares network flow algorithm . . . . . . . . . . . . . . 21 2.4 Maximum flow problem . . . . . . . . . . . . . . . . . . . . . . . 25 2.5 Review of the solution methods for max-flow problem . . . . . . . . 25 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 III. SOLVING THE MCF WITH NEGATIVE ARC LENGTH AND CAPACITY CONSTRAINTS . . . . . . . . . . . . . . . . . . . . . . . . . .28 3.1 LSNF for capacitated MCF . . . . . . . . . . . . . . . . . . . . . .28 3.2 Methods to obtain an initial dual feasible solution . . . . . . . . 30 3.3 LSNF for max-flow problem . . . . . . . . . . . . . . . . . . . . . 36 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 IV. THE LEAST-SQUARES DUAL-PRIMAL ALGORITHM . . . . . . . . . . . . . . 38 4.1 LSDP for max-flow problem . . . . . . . . . . . . . . . . . . . . . 38 4.1.1 The electrical network problem . . . . . . . . . . . . . . . . . .40 4.1.2 The NNLS problem with arc-node incident matrix . . . . . . . . . .41 4.2 LSDP for MCF . . . . . . . . . . . . . . . . . . . . . . . . . . . .50 4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 V. CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 REFERENCES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 56

    Ahuja, R., Orlin, J., Sharma, P. and Sokkalingam, P. A network simplex algorithm with O(n) consecutive degenerate pivots. Operations research letters, 30, 141-148, 2002.

    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.

    Bazaraa, M. S., Jarvis, J. J. and Sherali, H. D. Linear programming and network flows. John Wiley & Sons Inc., 1990.

    Cunningham, W. A network simplex method. Mathematical programming, 11, 105-116,
    1976.

    Curet, N. Implementation of a steepest-edge primal-dual simplex method for network linear programs. Annals of Operation Research, 81, 251-270, 1998.

    Dantzig, G. 1948. Programming in a linear sructure (Tech. Rep.). United States Air Force.

    Dantzig, G. 1951. Application of the simplex method to a transportation problem. In Activity analysis of production and allocation (pp. 359{373). New York, N. Y.:John Wiley & Sons Inc.

    Dijkstra, E. W. A note on two problems in connexion with graphs. Numerische
    Mathematik, 1, 269-271, 1959.

    Edmonds, J. and Karp, R. M. Theoretical improvement in algorithmic e±ciency for
    network flow problems. Journal of the Association for Computation Machine,
    19(248-264), 1972.

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

    Ford, L. R. Network flow theory. Santa Monica, California: The RAND Corp., 1956.

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

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

    Goldberg, A. V. and Tarjan, R. E. A new approach to the maximum flow problem.
    Journal of the Association for Computation Machine, 35, 921-940, 1988.

    Gopalakrishnan, B., Barnes, E., Johnson, E. and Sokol, J. 2004. A least-squares
    network flow algorithm (Tech. Rep.).

    Hu, T. Minimum-cost flow in convex-cost networks. Naval research logistics quarterly, 13, 1-9, 1966.

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

    Leichner, S., Dantzig, G. and Davis, J. A strictly improving linear programming phase 1 algorithm. Annals of Operatins Research, 47, 409-430, 1993.

    Paparrizos, K., Samaras, N. and Stephanides, G. A new e±cient primal dual simplex algorithm. Computers & Operations Research, 30, 1383-1399, 2003.

    Wang, I.-L. 2004. On solving shortest paths with a least-squares primal-dual algorithm (Tech. Rep.).

    下載圖示 校內：2008-08-28公開
    校外：2008-08-28公開
    QR CODE