The out-of-kilter algorithm is an algorithm that computes the solution to the minimum-cost flow problem in a flow network. It was published in 1961 by D. R. Fulkerson  and is described here. The analog of steady state flow in a network of nodes and arcs may describe a variety of processes. Examples include transportation systems &amp; personnel assignment actions. Arcs generally have cost &amp; capacity parameters. A recurring problem is trying to determine the minimum cost route between two points in a capacitated network. The idea of the algorithm is to identify out-of-kilter arcs and modify the flow network until all arcs are in-kilter and a minimum cost flow has been reached. The algorithm can be used to minimize the total cost of a constrained flow in an oriented network.
Algorithm.
To begin, the algorithm takes a single cycle and a set of node numbers. It then searches for out-of-kilter arcs. If none are found the algorithm is complete. If the flow needs to be increased or decreased to bring an arc into kilter, the algorithm will look for a path that increases or decreases the flow respectively. If no paths are found to improve the system then there is no feasible flow. This is done until all arcs are in-kilter, at which point the algorithm is complete.
Suppose that the network has n nodes and m oriented arcs. We write formula_1 if arc formula_2 has initial node formula_3 and terminal node formula_4. Let formula_5 be the flow along arc formula_2 (from node formula_3 to node formula_4). Define formula_9 and formula_10 to be the lower and upper capacity bounds on the flow in arc formula_2. The capacities may be either finite, or infinite on some or all arcs for either the lower or upper bounds. The problem that is at hand to solve is to minimize: formula_12 subject to:
formula_13 for each formula_14 (1)
, and:
formula_15 for each formula_16 (2)
If a given flow x satisfies (1), then the flow is conserved at each node and we call the flow a circulation. If the flow x satisfies (2) we say it is feasible.
Complexity.
Runtime:
References.
 ;templatestyles src="Reflist/styles.css" / ;