Table 4.1: NETGEN-HI family data
We use six network families produced by two network generator: NETGEN and GRIDGEN. Both of them are available in DIMACS ftp site. Here we use the similar setup as Goldberg did in [4] so that we can compare our codes with other codes he evaluated. We generate 2 categories of networks by NETGEN, and 3 categories by GRIDGEN. Each category contains 6 network families with different size. Each network family contains 50 networks with the same configurations except the random seed. All the CPU time we list in this Chapter for a network family is the average of its 50 networks. The same simplex code may have different performance for different network generators.
NETGEN is a network generator developed by Klingman, Napier, and Stutz [5] in 1974. We use its C version to create our testing categories--NETGEN-HI and NETGEN-LO. The 15 input parameters are as follows:
1 seed random number seed (a positive integer, we create it by a random number function) 2 problem problem number (a positive integer, set to be 1 in our code) 3 nodes number of nodes, we set it to be 2n, n=9~14 in our testing 4 sources number of source nodes: 2n-2 5 sinks number of sink node: 2n-2 6 density number of arcs: 2n+3 7 mincost min arc cost: 0 8 maxcost max arc cost: 4096 9 supply total supply: 22(n-2) 10 tsources number of transshipment source nodes: 0 11 tsinks number of transshipment sink nodes: 0 12 hicost percent of arcs with max cost: 100% 13 capacitated percent of capacitated arcs: 100% 14 mincap min arc capacity: 1 15 maxcap max arc capacity: (1) for NETGEN-HI: 16384 (2) for NETGEN-LO: 16
The NETGEN-HI and NETGEN-LO only differ in their max arc capacity. We tested 6 network families starting from n=9 to n=14 for each category. We did not test larger networks with n>14 since it would take too long to complete the same scale of tests.
GRIDGEN is a network generator developed by Lee [3] written in C language. This network generator generates a grid-like network plus a supernode. To be consistent with some configurations of the NETGEN generator, we set the input parameters as follows:
1 problem number of problems (a positive integer, set to be 1 in our code) 2 output name output file name 3 two-way 1 if arcs are linked in both direction; 0 otherwise; we set this to be 0 4 seed random number seed (a positive integer, we create it by a random number function) 5 nodes number of nodes, we set it to be 2n, n=9~14 in our testing 6 grid width we run 3 different geometries: (1) SQUARE: set grid width=nodes1/2 (2) LONG: set grid width=nodes/16 (3) WIDE: set grid width=16 7 sources number of source nodes: 2n-2 8 sinks number of sink node: 2n-2 9 avg. degree average degree for a node: 23 10 supply total supply: 22(n-2) 11 cost flag 1 for UNIFORM; 2 for EXPONENTIAL; we set this to be 1 12 mincost min arc cost: 0 13 maxcost max arc cost: 4096 14 capacity flag 1 for UNIFORM; 2 for EXPONENTIAL; we set this to be 1 15 mincap min arc capacity: 1 16 maxcap max arc capacity: 16384
We use GRIDGEN to create three categories of networks: SQUARE, LONG and WIDE. They only differ in geometries. We also tested 6 network families starting from n=9 to n=14 for each category. The costs and capacities are uniformly distributed in our test. One can set them to be exponentially distributed by changing some input parameters.
We run three premultiplier codes: (1) the nonscaling version (2) the generic scaling version and (3) the modified scaling version. To compare their performance with other codes, we also run two other codes: (1) a simplex code developed by Lee [3] that used the original network simplex algorithm and (2) a cost scaling simplex code developed by Goldberg [4].
To simplify the notation, let's call the nonscaling premultiplier simplex code "PNS"; the generic scaling premultiplier simplex code "PS1"; the modified scaling version "PS2"; the simplex code by Lee "OLD"; and the cost scaling code by Goldberg "CS2".
OLD was not optimal speeding the original simplex algorithm. It has two pivot-in rules for the entering arc. One is the first pivot-in rule which scans arcs from some node and pivots in the first eligible arc it encounters. The other rule uses a heuristic that scanning for the entering arc from those nodes with larger node potential. This heuristic did speed up the algorithm a lot. From our experience, we found the first pivot-in rule is too slow, especially when the network is large. Therefore, we choose that heuristic version to compare with our codes.
CS2 followed the algorithm used in [4]. We use the version 3.4 for our testing. It can be obtained by ftp theory.stanford.edu. According to Goldberg [4], the code is typically faster than many other simplex codes [4].
We tested two categories : NETGEN-HI and NETGEN-LO. Since NETGEN-HI families have higher capacity than NETGEN-LO, they have less severe capacity constraints. Thus all the codes should run faster for NETGEN-HI families. According to our tests, CS2 is much faster than all the other codes.
For NETGEN-HI families, OLD performs well if nodes < 2048. However, it becomes slower rapidly, and even much worse than other codes when nodes=16384. Our nonscaling premultiplier code, PNS, runs approximately as PS2 initially, but becomes worse when network size grows. Our generic scaling code, PS1, runs not so fast, but the running time does not grow as fast as PNS and OLD for larger networks. The modified scaling code, PS2, is the second fast one for larger networks. Its running time converges better than PS1.
For NETGEN-LO families, all codes run slower except PS1. Interestingly, PS1 runs about twice as fast as its performance for the NETGEN-HI families. PS2 still performs well, it only runs a little slower under this severe capacity constraint. Both PNS and CS2 run about 100% slower. However, CS2 is still the fastest code. OLD and PNS are the slowest.
We found that PNS and PS1 are more sensitive than other codes. That is, with the same size of networks, their CPU time may vary a lot, especially for larger networks. We tested 50 networks for each family to ensure that we would not draw the wrong conclusions.
PS2, OLD and CS2 perform very consistently for networks with the same size. Figure 4.2 and 4.4 illustrate the CPU time distribution of 50 networks from the 2 different network families with 2 different sizes.
We tested three categories : GRIDGEN-WIDE, GRIDGEN-LONG, and GRIDGEN-SQUARE. They are different in their shapes.
However, all the codes perform approximately the same for these three categories despite their different shapes. Like its performance in NETGEN families, OLD performs well if nodes < 2048, but becomes slower rapidly, and is the slowest one when nodes=16384. PNS runs approximately as PS2 initially, but becomes worse when network size grows. PS1 performs not well for all cases.
PS2 is still the second fast code for larger networks. Still, PNS and PS1 are more sensitive than other codes. It is interesting that there are 2 networks of 16384 nodes in the GRIDGEN-WIDE family made CS2 run twice as slow as its usual performance. However, CS2 is still much faster than all the other codes.
Table 4.1: NETGEN-HI family data
Table 4.2: NETGEN-LO family data
Table 4.3: GRIDGEN-WIDE family data
Table 4.4: GRIDGEN-LONG family data
Table 4.5: GRIDGEN-SQUARE family data
