Shortest Paths and Multicommodity Network Flows


Download whole Ph.D. Thesis [pdf:1.3MB] [ps:2.4MB]

       The shortest path problem is a classic and important combinatorial optimization problems. It often appears as a subproblem when solving difficult combinatorial problems like multicommodity network flow (MCNF) problems.

       Most shortest path algorithms in the literature are either to compute the 1-ALL single source shortest path (SSSP) tree, or to compute the ALL-ALL all pairs shortest paths (APSP). However, most real world applications require only multiple pairs shortest paths (MPSP), where the shortest paths and distances between only some specific pairs of origin-destination nodes in a network are desired. The traditional single source shortest path (SSSP) and all pairs shortest paths (APSP) algorithms may do unnecessary computations to solve the MPSP problem.

       We survey and summarize many shortest path algorithms, and discuss their pros and cons. We also investigate the Least Squares Primal-Dual method, a new LP algorithm that avoids degenerate pivots in each primal-dual iteration, for solving 1-1 and 1-ALL shortest path problems with nonnegative arc lengths, show its equivalence to the classic Dijkstra's algorithm, and compare it with the original primal-dual method.

      We propose two new shortest path algorithms to save computational work when solving the MPSP problem. Our MPSP algorithms are especially suitable for applications with fixed network topology but changeable arc lengths. We discuss the theoretical details and complexity analyses. We test several implementations of our new MPSP algorithms extensively and compare them with many state-of-the-art SSSP algorithms for solving many families of artificially generated networks and a real Asia-Pacific flight network.

      Our MPSP computational experiments show that there exists no "killer" shortest path algorithm. Our algorithms have better performance for dense networks, but become worse for larger networks. Although they do not have best performance for the artificially generated graphs, they seem to be competitive for the real Aisa-Pacific flight network.

      We provide an extensive survey on both the applications and solution methods for MCNF problems in this thesis. Among those methods, we investigate the combination of the primal-dual algorithm with the key path decomposition method. In particular, to efficiently solve the restricted primal problem (RPP) in each primal-dual iteration, we relax the nonnegativity constraints for some set of basic variables, which makes the relaxed RPP smaller and easier to solve since the convexity constraint will be implicitly maintained.

      We implement our new primal-dual key path method (KEY), propose new methods to identify max step length, and suggest perturbation methods to avoid degenerate pivots and indefinite cycling problems caused by primal and dual degeneracy. We perform limited computational experiments to compare the running time of the generic primal-dual (PD) method, the Dantzig-Wolfe (DW) decomposition method, and the CPLEX LP solver that solves the node-arc form (NA) of the MCNF problems, with our method KEY. Observations from the computational experiments suggest directions for better DW implementation and possible remedies for improving PD and KEY.