Shortest Paths and Multicommodity Network Flows

Chapter 5 Implementing new MPSP algorithms

[pdf:336kB] [ps:754kB]

        Many efficient SSSP and APSP algorithms and their implementations have been proposed in the literature. However, only few of them are targeted to solving the MPSP problems or problems with fixed topology but changeable arc lengths or requested OD pairs. These problems of course can be solved by repeated SSSP algorithms. Other methods such as the LP-based reoptimization algorithms (see Section 3.5.2) take advantage of previous optimal shortest paths and perform either primal network simplex methods (when arc lengths change) or dual network simplex methods (when OD pairs change). More recent computational experiments <cite>Bu93</cite> indicate these reoptimization algorithms are still inferior to the repeated SSSP algorithms which repeatedly solve shortest path trees for different requested origins (or destinations, depending on which one has smaller cardinality).

        A practical implementation of Carré's algorithm <cite>Ca71</cite> by Goto et al. <cite>GoOhYo76</cite> tries to exploit the sparseness and topology of the networks. For networks with fixed topology, their implementation first does a preprocessing procedure to identify a good node pivoting order so that the fill-ins in the LU decomposition phase are decreased. To avoid unnecessary triple comparisons, they record all the nontrivial triple comparisons in the LU decomposition, forward elimination and backward substitution phases, and then generate an ad hoc APSP code. Their method only stores O(m) data structures, which is the same as other combinatorial SSSP algorithms but is better than O(n²) as required in general algebraic algorithms. However, this comes with the price of storing the long codes of nontrivial triple comparisons, and may require more total hardware storage. Even worse, the long codes may not be compilable for some compilers.

        In particular, we have tested a 1025-node, 6464-arc sparse graph and generated a 500MB long code using the code generation algorithm of Goto et al. <cite>GoOhYo76</cite>. The code we generated could not be compiled even on a fast Sun workstation with 1GB memory using gcc, a C compiler by GNU, with optimization tags. If instead we only store the arc index of all the triple comparisons, the code will be short but still need temporary storage around 200MB to store these indices. Therefore, code generation is not practical for large networks.

        In this chapter, we observe that Carré's algorithm can be implemented combinatorially which resolves the need of a huge storage quota by the code generation. Furthermore, we can decompose and truncate Carré's algorithm according to the indices of the distinct origins/destinations of the requested OD pairs. Section 5.1 introduces some notation and definitions appearing in this chapter. Section 5.2 describes major procedures of our algorithm SLU, a sparse combinatorial implementation of Carré's algorithm. Section 5.3 gives detailed implementation issues, and techniques for speeding up SLU. Implementations of algorithm DLU2, our proposed MPSP algorithm that appeared in Section 4.3, are given in Section 5.4. Computational experiments including a sparse implementation of the Floyd-Warshall algorithm, many state-of-the-art SSSP codes written by Cherkassky et al. <cite>ChGoRa96</cite>, and networks that we generate, are presented in Section 5.5. Section 5.6 shows results of our computational experiments and draws conclusions.

Summary

        After these comprehensive computational experiments, we have several observations.

  1. Among the eight different pivoting rules for sparsity, the dynamic Markowitz and its variant that employs simple tie-breaking technique usually produce fewer fill-ins than other pivoting rules.
  2. Among the three different SLU implementations, the bucket implementation SLU1 outperforms the other two implementations that are based on binary heaps, for all cases. Similarly, the bucket implementation of DLU2, DLU21, has better performance than the heap implementation.
            For general larger networks, SLU1 and DLU21 can not compete with the best of the state-of-the-art SSSP codes , except for acyclic networks. Nevertheless, SLU1 and DLU21 do not perform worst for all cases.
            For dense graphs, usually DLU21 performs better than SLU1; for sparse graphs, usually SLU1 is better than DLU21. Unlike other SSSP algorithms which perform consistently regardless the number of distinct destinations, SLU1 and DLU21 perform relatively better for MPSP problems of more distinct requested destinations than for problems of fewer distinct requested destinations.
  3. The Asia-Pacific flight network is the only real-world network tested in this thesis. Although it is sparse (112 nodes, 1038 arcs), DLU21 performs better than SLU1, which in turn outperforms all of the implemented label-setting codes. The label-correcting codes perform similarly to SLU1 and DLU21. The Floyd-Warshall algorithm is in no case competitive with other SSSP algorithms or our proposed MPSP algorithms.
  4. In most SPGRID families, the label-correcting codes usually perform the best, except for the SPGRID-PH family for which the label-setting codes perform the best. SLU1 and DLU21 have better performance on the SPGRID-SQ and SPGRID-WL families than other SPGRID families.
            For each SPGRID family, label-setting codes usually perform relatively worse on smaller networks.
  5. SLU1 and DLU21 are usually slower than other label-correcting and label-setting codes for most SPRAND families. Label-correcting codes perform better for most sparse SPRAND families, but label-setting codes perform better for most dense SPRAND families.
            When the range of arc lengths decreases (e.g.,<=10 ), label-correcting codes tend to perform much worse. When the range of arc lengths increases on sparse graphs, label-setting codes will perform only slightly worse.
  6. SLU1 and DLU21 are usually slower than other label-correcting and label-setting codes for most NETGEN families. Label-correcting codes perform better for most sparse NETGEN families, but label-setting codes perform better for most dense NETGEN families.
            When the range of arc lengths increases on sparse graphs, label-setting codes tend to perform a little worse.
  7. SLU1 and GOR1 usually outperform other codes for all SPACYC families except the SPACYC-PD family, for which the label-setting codes perform asymptotically the best. DLU21 performs asymptotically the worst for cases whose arc lengths are all positive. However, all label-correcting codes (except GOR1) and label-setting codes perform significantly worse for cases with negative arc lengths.

Conclusion and Future Research

        Although our computational experiments are already extensive, more thorough tests may still be required to draw more solid conclusions. There are too many factors that may affect the performance of MPSP algorithms, such as requested OD pairs, arc lengths, network topologies, and node orderings.

        In our experiments, for each test case, we generate only one set of requested OD pairs. Different requested OD pairs may affect the performance since the distribution of requested pairs in the OD matrix will not affect the SSSP algorithms but may affect our MPSP algorithms.

        By specifying the same numbers of nodes and arcs but different random seeds, we may generate several different test cases with the same topology but different arc lengths. A more thorough experiment could generate several such networks and test all of the algorithms on these cases to compute their average performance. Due to time constraints, in this chapter we use only one random seed for each topology.

        Different node orderings will significantly affect our MPSP algorithms. In this chapter, we choose a node ordering aimed at reducing the total fill-ins in the LU factorization. As discussed in Section 4.4, another ordering consideration is to group the requested OD pairs and assign them higher indices. This is difficult to test for randomly generated networks and requested OD pairs. It may be worth trying for some real-world applications where both the network topology and requested OD pairs are fixed.

        Our limited results show that our MPSP algorithms seem to perform worse for general larger networks. This may make sense since after all SLU and DLU are algebraic algorithms, although we create graphical implementations for testing. In particular, SLU and DLU are more suitable for cases whose arc lengths are randomly distributed for all cases since they are designed to work independent of arc lengths. They are based on the ordering of triple comparisons. The sequence of triple comparisons is fixed and unavoidable in our MPSP algorithms. Thus, even if there exists some arc with a very large length, our algorithms could not avoid some trivial triple comparisons involving this arc, although intuitively we know in advance these operations are wasteful. Conventional SSSP algorithms, on the other hand, are based more on the comparison of arc lengths. For example, the greedy algorithm (Dijkstra's) only does triple comparisons on nodes with the smallest distance label in each iteration. Adding some "greedy" ideas to our MPSP algorithms might help them avoid many wasteful operations. However, it is still not clear how to integrate these two different methodologies.

        If we suspect our MPSP algorithms may perform worse than conventional SSSP algorithms for most cases, we can design an experiment by generating the requested OD pairs most favorable to our MPSP algorithms. In particular, since both SLU and DLU can compute optimal distance faster for OD pairs with larger indices, the most favorable settings for our MPSP algorithms are: (a) find an optimal (or a very good) sparse node ordering, and (b) in that ordering, generate k requested OD pairs that span the k entries in the OD matrix in a line perpendicular to the diagonal entries. That is, entries (n,n-k+1), (n-1,n-k+2), …, (n-k+2,n-1), (n-k+1,n) will be the set of requested OD pairs. Such a setting will force the conventional SSSP to solve k SSSP problems, but will be most advantageous for our MPSP algorithms since they are not only in the sparse ordering but are also the closest to the "southeastern" corner of the OD matrix in the new ordering. If experiments on many random graphs with such settings still show that our MPSP algorithms do not outperform the conventional SSSP algorithms, we would conclude that our MPSP algorithms are indeed less efficient.

        The experiments in this chapter are just a first step in evaluating algorithmic efficiency when solving general MPSP problems. More thorough experiments will be done in the future.