ネットワーク単体法

ネットワーク単体法（ネットワークたんたいほう、別称：ネットワークシンプレックス法、英: network simplex algorithm）とは、数理最適化においてグラフ理論に特化した単体法のことを指す。ネットワーク単体法は主に最小費用流問題（英語版）を解くために使用される。実践においてネットワーク単体法は同じ規模のネットワーク問題に対する線形計画問題を解く速度は一般の単体法と比べて約200から300倍速く解くことも可能とされる^[1]。

歴史

ネットワーク単体法は提案されて以降、実践では非常に効率よく問題を解くことが可能であることは知られていたが、アルゴリズムの計算複雑性については長らく多項式時間のアルゴリズムであるかが未解決問題とされてきた。1995年、ジェームズ・オーリン（英語版）によってネットワーク単体法の時間計算量が頂点数 $V$ 、辺数 $E$ 、重みの最大値 $C$ に対して $O(V^{2}E\log(VC))$ であることが証明された^[2]。また、1997年にはロバート・タージャンによって動的木（英語版）を使用することでネットワーク単体法の時間計算量が $O(VE\log V\log(VC))$ に改良された^[3]。同じ問題に対する解法の双対ネットワーク単体法の計算量については辺数および頂点数に依存度が高いものの、強多項式時間アルゴリズムであることが古くから知られている^[4]。

概要

ネットワーク単体法は有界変数単体法^{[注釈 1]}の変種の解法である。ネットワーク単体法において基底は元のネットワークでの根付き全域木として表され、変数は有向辺によって、単体乗数（双対変数）は各頂点で求まるポテンシャルによって表される。各反復においてある価格戦略（ピボット選択）に基づいて、入る変数については単体乗数（頂点のポテンシャル）の値によって選択し、それにより既に存在する木構造の辺と合わせて閉路が形成される。出る変数についてはこの閉路上で増加可能な流量が最も小さい枝を選択する。各反復において入る辺と出る辺の入替や木の再構築の過程をピボットと呼ぶ。反復が進み入ることのできる非基底枝が存在しなくなったとき、最適解に到達したことになる。

応用

ネットワーク単体法は以下に挙げられる実践的な問題を解くために使用されている^[5]:

輸送問題（英語版）
ヒッチコック型輸送問題（英語版）
割当問題（英語版）
半順序集合における鎖と反鎖（英語版）
二部グラフにおける被覆とマッチング

脚注

[脚注の使い方]

注釈

^ 英: primal simplex algorithm

出典

^ Bazaraa, Mokhtar S.; Jarvis, John J.; Sherali, Hanif D. (2010). Linear Programming and Network Flows (4th ed.). Wiley. p. 453
^ Orlin, James B. (1997-08-01). “A polynomial time primal network simplex algorithm for minimum cost flows”. Mathematical Programming 78 (2): 109–129. doi:10.1007/BF02614365. hdl:1721.1/2584. ISSN 0025-5610.
^ Tarjan, Robert E. (1997-08-01). “Dynamic trees as search trees via euler tours, applied to the network simplex algorithm”. Mathematical Programming 78 (2): 169–177. doi:10.1007/BF02614369. ISSN 0025-5610.
^ Orlin, James B.; Plotkin, Serge A.; Tardos, Éva (June 1993). “Polynomial dual network simplex algorithms”. Mathematical Programming 60 (1–3): 255–276. doi:10.1007/bf01580615.
^ Chvatal, Vasek (1983). “20”. Linear Programming. Macmillan. pp. 320–351. ISBN 9780716715870