Out-of-kilter algorithm: Difference between revisions

Revision as of 05:45, 11 February 2018

Latest revision as of 15:09, 8 September 2024

(17 intermediate revisions by 11 users not shown)

Line 1:

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]]{{nnbsp}}<ref>{{cite journal |title=An Out-of-Kilter Method for Minimal-Cost Flow Problems |author=D. R. Fulkerson |journal=[[Journal of the Society for Industrial and Applied Mathematics]] |volume=9|issue=1 |date=March 1961|pages=18-2718–27 |doi=10.1137/0109002 |jstor=2099013}}</ref> and is described here.<ref name="durbin-and-kroenke-1967">{{cite book

{{cite book

| last1 = Durbin | first1 = EP

| last2 = Kroenke | first2 = DM

Line 10 ⟶ 9:

| access-date = 2018-01-16

}}

</ref> 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.

</ref>

{{== Algorithm-stub}} ==

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 <math>j ~ (i,i^1)</math> if arc <math>j</math> has initial node <math>i</math> and terminal node <math>i^1</math>. Let <math>x(j)</math> be the flow along arc <math>j</math> (from node <math>i</math> to node <math>i^1</math>). Define <math>c^-(j)</math> and <math>c^+(j)</math> to be the lower and upper capacity bounds on the flow in arc <math>j</math>. 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: <math>\sum_{j=1}^md(j) x(j)</math> subject to:

<math>\sum_{j:j~(i,i^1)}x(j) -\sum_{j:j~(i^1,i)}x(j) = 0 </math> for each <math>i = 1,....,n</math> (1)

, and:

<math>c^-(j)\leq x(j)\leq c^+(j) </math> for each <math>j = 1,....,n</math> (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 <math> O(mU) </math> iterations

* Dominant computation is shortest path computation

* Total runtime is: <math> O(m^2 U+mUn\log(n)) </math>

==References==

{{reflist|30em}}<ref>{{Cite web|url=https://www.maths.cam.ac.uk/sites/www.maths.cam.ac.uk/files/pre2014/undergrad/catam/committee/STATS/8pt4.pdf|title=Out of Kilter Algorithm|last=Cambridge|first=University of|date=July 2012|website=www.maths.cam.ac.uk}}</ref>

{{reflist|30em}}

==External links==

* {{YouTube|id=JaDnsMbeUkE|title=Algoritmo Out-of-Kilter}} (in Spanish)

[[Category:FlowNetwork networkflow problem]]

{{Algorithm-stub}}