Implementing the Premultiplier Method for Minimum-Cost
Flow Problem
by
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
Abstract
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