The Out-of-Kilter Algorithm and Its Network Flow Implementations

D.R. Fulkerson [1] published the out-of-kilter algorithm, which computes the solution to the minimum-cost flow issue in a flow network. The Out-of-Kilter technique can be used to solve problems like the transportation problem, which can be described as a maximum flow and minimal cost – maximum flow problem. To begin, the algorithm creates an initial flow along the arcs and assigns a number to each of the network’s nodes. See, for example, Bazaraa, which employs Complementary Slackness Optimality Conditions (CSOC). The method developed by Jarvis and Sherali [2] looks for out-of-kilter arcs (those that do not satisfy CSOC conditions). If there aren’t any, the algorithm is finished. The flow must be increased or decreased to bring arcs that do not satisfy the CSOC theorem into alignment. According to the demand, the algorithm will hunt for a path that either enhances or decreases the flow. This is repeated until all of the arcs are aligned, at which time the procedure is finished. There is no conceivable flow if no paths to improve the system are found. The Out-of-Kilter algorithm is used to determine the best solution to any network flow problem. This comprises transit, assignment, and shortest path problems, among others. Computer solutions are presented using a Pascal programme and Matlab.

Author(s) Details

W. H. Moolman
Department of Mathematical Sciences and Computing, Walter Sisulu University, Mthatha, South Africa.

View Book :-

Leave a Reply

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

Previous post Computing and Applications: The Maximum Flow and Minimum Cost – Maximum Flow Problems
Next post Theory and Application of Average fs-Aggregate Algorithm