Out-of-kilter algorithm

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 ^[1] and is described here.^[2] The analog of steady state flow in a network of nodes and arcs may describe a variety of processes. Examples include transportation systems & personnel assignment actions. Arcs generally have cost & 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 ${\displaystyle j~(i,i^{1})}$ if arc ${\displaystyle j}$ has initial node ${\displaystyle i}$ and terminal node ${\displaystyle i^{1}}$. Let ${\displaystyle x(j)}$ be the flow along arc ${\displaystyle j}$ (from node ${\displaystyle i}$ to node ${\displaystyle i^{1}}$). Define ${\displaystyle c^{-}(j)}$ and ${\displaystyle c^{+}(j)}$ to be the lower and upper capacity bounds on the flow in arc ${\displaystyle j}$. 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: ${\displaystyle \sum _{j=1}^{m}d(j)x(j)}$ subject to:

${\displaystyle \sum _{j:j~(i,i^{1})}x(j)-\sum _{j:j~(i^{1},i)}x(j)=0}$ for each ${\displaystyle i=1,....,n}$ (1)

, and:

${\displaystyle c^{-}(j)\leq x(j)\leq c^{+}(j)}$ for each ${\displaystyle j=1,....,n}$ (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:

• The algorithm terminates within ${\displaystyle O(mU)}$ iterations
• Dominant computation is shortest path computation
• Total runtime is: ${\displaystyle O(m^{2}U+mUn\log(n))}$

References

^[1]

External links

• Algoritmo Out-of-Kilter on YouTube (in Spanish)

This page was last edited on 24 August 2023, at 05:26