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

The out-of-kilter algorithm, which was published by D.R. Fulkerson [1], is an algorithm that computes the solution to the minimum-cost flow problem in a flow network. The Out-of-Kilter algorithm can be applied to solve the maximum flow and minimum cost – maximum flow problems as well as problems that can be formulated as such problems e.g. the transportation problem. To begin, the algorithm starts with an initial flow along the arcs and a number for each of the nodes in the network. By making use of Complementary Slackness Optimality Conditions (CSOC) see e.g. Bazaraa, Jarvis & Sherali [2], the algorithm searches for out-of-kilter arcs (those that do not satisfy CSOC conditions). If none are found the algorithm is complete. For arcs that do not satisfy the CSOC theorem the flow needs to be increased or decreased to bring them into kilter. The algorithm will look for a path that either increases or decreases the flow according to the need. This is done until all arcs are in-kilter, at which point the algorithm is complete. If no paths are found to improve the system then there is no feasible flow. The Out-of-Kilter algorithm is applied to find the optimal solution of any problem that involves network flows. This includes problems such as the transportation, assignment and shortest path problems. Computer solutions using a Pascal program and Matlab are demonstrated.