Recent Developments in Computer Implementation Technology for Network Flow Algorithms

Publisher Website
Google Scholar
Abstract
The application of computer implementation technology to network optimization has brought about unprecedented advances in solution efficiency. The remarkable gains of the early to mid 1970s for solving transportation and transhipment problems are widely known, enabling network codes to out-perform LP codes by two orders of magnitude for these problems. The pioneering study by Gilsinn and Witzgall demonstrated that effective use of computer implementation technology could reduce solution times for shortest path problems from one minute to slightly more than one second, using the same general shortest path algorithm, computer, and compiler. The momentum launched by these studies has not dwindled, but continues into the present. New advances in all areas of network optimization have recently superseded the procedures previously found to be best. Latest computer implementations clearly outstrip the best codes of the recent past, as our understanding of the important relation between algorithmic de:sign and implementation continues to grow. We undertake to report on some of the major computer implementation studies of the past few years and to present preliminary results on the new developments.