|Start Page Number:||125|
|End Page Number:||190|
|Publication Date:||Aug 1988|
|Journal:||Annals of Operations Research|
|Authors:||Bertsekas Dimitri P., Tseng Paul|
|Keywords:||networks, programming: network|
The authors describe a relaxation algorithm for solving the classical minimum cost network flow problem. The present implementation if compared with mature state-of-the-art primal simplex and primal-dual codes and is found to be several times faster on all types of randomly generated network flow problems. Furthermore, the speed-up factor increases with problem dimension. The codes, called RELAX-II and RELAXT-II, have a facility for efficient reoptimization and sensitivity analysis, and are in the public domain.