Applying steepest-edge techniques to a network primal–dual algorithm

Applying steepest-edge techniques to a network primal–dual algorithm

0.00 Avg rating0 Votes
Article ID: iaor1998947
Country: United Kingdom
Volume: 24
Issue: 7
Start Page Number: 601
End Page Number: 609
Publication Date: Jul 1997
Journal: Computers and Operations Research
Authors:
Keywords: networks
Abstract:

This article addresses the computational efficacy of applying steepest-edge criteria in a primal–dual algorithm for solving the minimum cost network flow problem. It is shown for the incremental primal–dual method, steepest-edge directions can be calculated directly without any additional data structures or computational overhead. The resulting implementation outperformed a network simplex code by over an order of magnitude in CPU time on medium sized problems from the NETGEN benchmark problem suite, and also compared favourably with the relaxation method on uncapacitated transportation and transshipment problems.

Reviews

Required fields are marked *. Your email address will not be published.