アウトオブキルタ法

アウトオブキルタ法（アウトオブキルタほう、英: out-of-kilter algorithm）とは、フローネットワークにおける最小費用流問題を解くアルゴリズムの一種である。1961年にデルバード・レイ・ファルカーソン（英語版）により初めて提案された解法である^[1][2]。頂点と枝からなるネットワークにおいて定常流を求める問題は、さまざまな事象を記述するために応用することができる。例として輸送システムや人員の配置割当などが挙げられる。一般的に枝には費用および容量が与えられている。そして、容量制約付きネットワーク内においてある2点間の最短経路を求めることがしばしば発生する。アウトオブキルタ法ではアウトオブキルタな枝を特定し、すべての枝がインキルタとなり、最小費用のフローが得られるまでその時点で得られているフローを修正していくこととなる。そのため、制約付きの有向ネットワークにおいて総費用が最小となるフローを求めることができる。

アルゴリズム

始めに、アウトオブキルタ法では単一の閉路およびその頂点の集合を得る。そしてアウトオブキルタな枝を探す。もしキルタ内の枝においてフローを増加あるいは減少させられるならば、それぞれフローを増加あるいは減少させる道を求める。もしそのような道が存在しなければ、実行可能なフローは存在しない。この手順はすべての枝がインキルタになるまで続け、やがて最適なフローが求まる。

今、${\displaystyle n}$ 個の頂点および、${\displaystyle m}$ 個の有向枝のネットワークについて考える。もし枝 ${\displaystyle j}$ が始点に ${\displaystyle i}$ を持ち、終点に ${\displaystyle i^{1}}$ を持っているならば、${\displaystyle j~(i,i^{1})}$ と記述する。ここで、${\displaystyle x(j)}$ を枝 ${\displaystyle j}$ に流れる（頂点 ${\displaystyle i}$ から頂点 ${\displaystyle i^{1}}$への）フローの量とする。また、${\displaystyle c^{-}(j)}$、${\displaystyle c^{+}(j)}$ はそれぞれ枝 ${\displaystyle j}$ におけるフローの容量の下限および上限を表すとする。容量については下限・上限のいずれも一部あるいはすべての枝において有限の値として与えられる場合もあれば、無限の容量とする場合もある。このとき、最適化する問題は以下の通りに表される:

${\displaystyle \min }$		${\displaystyle \sum _{j=1}^{m}d(j)x(j)}$
${\displaystyle \mathrm {s.t.} }$		${\displaystyle \sum _{j:j~(i,i^{1})}x(j)-\sum _{j:j~(i^{1},i)}x(j)=0}$		${\displaystyle i=1,....,n}$ (1)
		${\displaystyle c^{-}(j)\leq x(j)\leq c^{+}(j)}$		${\displaystyle j=1,....,n}$ (2)

もし与えられたフロー x が (1) を満たすとき、各頂点においてフローは保存され、それらは循環フローといえる。もしフロー x が (2) を満たすとき、実行可能であるといえる。

計算複雑性

計算量:

• 反復では ${\displaystyle O(mU)}$ の計算量
• この計算量は最短経路の計算が主に占める
• 総計算量: ${\displaystyle O(m^{2}U+mUn\log(n))}$