Research On Solving Maximum Flow Problem In Large-scale Network

In the classic operations research theory, network flow theory is one of the fastest growing branches. So far. network flow model is a very mature model both from the theory and practical applications. The establishment and continuous improvement of algorithm for network flow model provide a very useful tool to meet the challenges of many practical problems. The maximum flow problem is a special problem in the network flow theory; the study target is to compute and study the maximum flow of a circulation network. In addition, the maximum flow problem is an important part of the network flow theory. It is a classic combination of optimization problems, but also can be seen as a special linear programming problem. Addition to solve the problems in the real network, the maximum flow problem has a wide range of applications in many engineering fields, such as electricity, transportation, logistics, and physical, chemical, biological, and management science and applied mathematics and other scientific fields. Despite the efforts of many scholars greatly advanced the research progress of the maximum flow problem, but the maximum flow problem is far from over.However, in the theoretical algorithm research, people do not find the exact lower bound for the time complexity of maximum flow algorithm, not to any general algorithm to or close to the lower bound. Secondly, along with the growing scale of the networks, classic algorithms must arise’state explosion’problem that makes the classical algorithms cannot meet the needs of practical problems as well as its improved version. Moreover, due to the limitations of the computer hardware itself, for large-scale data, the classical algorithms are not able to solve the maximum flow problem even. Therefore, we need pay much more attention on the theoretical study of maximum flow problem.In this dissertation, we are aimed at how to approximately compute the maximum flow on the contracted networks in order to reducing computation scale with small error. By solving a specific structure of the network, according to the flow information analysis of the specific structure, many specific structures are selected to contract in order to reduce the network size and construct target network. Finally, we take advantage of the classic algorithms to solve maximum flow problem on target network. On the basis of this idea, this dissertation proposes two algorithms named Solving Maximum Flow Based on Contracting Community and Solving Maximum Flow Based on layer network. Two algorithms could accurately solve the maximum flow within the range of allowable error and reduce the network size to some extent. Experimental results show the effectiveness and efficiency of the proposed algorithms.The contribution of this dissertation is as follows:1. Describes the maximum flow problem, the application background, significance and domestic and international development status. Present the challenges that classic algorithms meet.Introduce network flow theory, theorem, classic algorithms about maximum flow and it’s improved versions. Make some research and analysis for classic algorithms.2. Two algorithms are presented:Solving Maximum Flow Based on Contracting Community and Solving Maximum Flow Based on layer network. Describe the processes of the two algorithms in detail. Give the experimental results over data sets theoretical analysis and experimental results.