An efficient graph technique based dual-type algorithm for NMNF problems with large capacity constraints

摘要

In this paper, we propose a Graph Method Decomposition Technique based dual-type (GbDt) algorithm to solve the Nonlinear Multi-commodity Network Flow (NMNF) problems with large number of capacity constraints. The GbDt algorithm is imbedded with two techniques, the first is the Graph Method Decomposition (GmD) technique which can decouple the large dimension projection problem induced by the large number of capacity constraints into several independent small dimension projection problems, the second is the Modified Successive Projection and Truncated (MSPT) technique can solve the disjoint projection problems efficiently. We have combined these two techniques with a Successive Quadratic Programming (SQP) method and a Dual Projected Pseudo-Quasi-Newton (DPPQN) method possessing decomposition effects. With the decomposition, our algorithm is computationally efficient. We have tested our method in solving numerous examples of NMNF problems. The simulation results show that the proposed algorithm is efficient in solving the NMNF problems and successfully handle the large number of coupling capacity constraints. Furthermore, the computational efficiency of the proposed algorithm is more significant while the numbers of commodity are increased.