Contents

1 Introduction

1.1 Overview of this Thesis

2 Background

2.1 Notations and Definitions
2.2 Original Network Simplex Algorithm
2.3 Premultiplier Network Simplex Algorithm

2.3.1 Nonscaling Premultiplier Algorithm
2.3.2 Scaling Version of Premultiplier Algorithm

3 Implementing the Premultiplier Algorithm

3.1 Nonscaling Premultiplier Algorithm

3.1.1 Pseudo Code
3.1.2 More about our implementing

3.2 Scaling Premultiplier Algorithm

3.2.1 Pseudo Code for the Generic Scaling Version
3.2.2 Pseudo Code for the Modified Scaling Version

4 Computational Testing Results

4.1 Testing Setup

4.1.1 NETGEN network generator
4.1.2 GRIDGEN network generator

4.2 Testing Codes
4.3 Results of NETGEN Families

4.3.1 Sensitivity

4.4 GRIDGEN Families

5 Discussion and Conclusion

5.1 CPU Time Analysis and Bottleneck
5.2 More Insights in Premultiplier Algorithm
5.3 Conclusion

A Detailed Pseudo Codes and Output of Our Codes

A.1 Detailed Pseudo Code for the procedure find_in_arc in the Nonscaling Premultiplier Algorithm
A.2 Sample Output of our premultiplier codes

List of Figures

2-1 a network example of minimum cost flow
2-2 A minimum cost flow problem solved by nonscaling premultiplier algorithm
2-3 the same example solved by the generic scaling premultiplier algorithm
2-4 same example solved by the modified scaling premultiplier algorithm
3-1 An example for the procedure update_tree1
3-2 An example for the procedure update_tree2
4-1 plot of CPU time for NETGEN-HI families
4-2 CPU time distribution plot for 2 NETGEN-HI families
4-3 plot of CPU time for NETGEN-LO families
4-4 CPU time distribution plot for 2 NETGEN-LO families
4-5 plot of CPU time for GRIDGEN-WIDE families
4-6 CPU time distribution plot for 2 GRIDGEN-WIDE families
4-7 plot of CPU time for GRIDGEN-LONG families
4-8 CPU time distribution plot for 2 GRIDGEN-LONG families
4-9 plot of CPU time for GRIDGEN-SQUARE families
4-10 CPU time distribution plot for 2 GRIDGEN-SQUARE families
5-1 an example of nodes scanned history by PNS

List of Tables

2.1 arc information for initial tree in Figure 2.1(b)
2.2 node information in Figure 2.1(b)
4.1 NETGEN-HI family data
4.2 NETGEN-LO family data
4.3 GRIDGEN-WIDE family data
4.4 GRIDGEN-LONG family data
4.5 GRIDGEN-SQUARE family data
5.1 CPU time proportion of 4 procedures running GRIDGEN-WIDE networks by PNS
5.2 CPU time proportion of 4 procedures running GRIDGEN-WIDE networks by PS1
5.3 CPU time proportion of 4 procedures running GRIDGEN-WIDE networks by PS2

Previous: Return Acknowledgment
Next: Go to Chapter1
Go to Premultiplier C Codes