Implementing the Premultiplier Method for Minimum-Cost
Flow Problem


I-Lin Wang

Submitted to the Department of Aeronautics and Astronautics on January, 1996, in partial fulfillment of the requirements for the degree of Master of Science in Operations Research


In this thesis, I implemented the new network simplex algorithm called "premultiplier algorithm"; introduced by Professor James B. Orlin. First I implemented the pseudopolynomial variant of that algorithm, then I finished the cost-scaling version which has a polynomial running time O(min(n2mlognC, n2m2logn)). I also implemented a slightly different version of the scaling algorithm in which I use a different policy for updating the premultipliers, and found it did speed up the algorithm although its theoretical running time O(min(nm2lognC, nm3logn)) is a little worse. Finally, I compared my codes with Goldberg's cost-scaling simplex code called "cs2". Although my codes still can't compete with cs2 at this moment, this premultiplier algorithm does have some good characteristics different from the original network simplex algorithm. From some graphs and charts of this thesis, we can get more insights of the premultiplier algorithm which contains some interesting aspects for future researches.

Thesis Supervisor: James B. Orlin
Title: Professor