ネットワーク単体アルゴリズム

数学的最適化において、ネットワーク単体アルゴリズムは単体アルゴリズムのグラフ理論的特殊化である。このアルゴリズムは通常、最小コストフロー問題の観点から定式化される。ネットワーク単体法は実用上非常にうまく機能し、通常、同じ次元の一般線形計画法に適用される単体法よりも200～300倍高速である。^[1]

長い間、証明可能な効率的なネットワーク単体アルゴリズムの存在は、実際には効率的なバージョンが存在したにもかかわらず、複雑性理論における主要な未解決問題の 1 つでした。1995 年にOrlin は、実行時間が である最初の多項式アルゴリズムを提供しました。ここで、 は任意のエッジの最大コストです。^[2]その後、Tarjan は1997 年にこれを動的ツリーを使用するように改良しました。 ^[3]同じ問題に対する、グラフ内のエッジと頂点の数への依存度が高い、強多項式デュアル ネットワーク単体アルゴリズムは、以前から知られています。^[4]${\displaystyle O(V^{2}E\log(VC))}$${\displaystyle C}$${\displaystyle O(VE\log V\log(VC))}$

ネットワーク シンプレックス法は、有界変数の主シンプレックス アルゴリズムを応用したものです。基底は、基礎となるネットワークのルート付きスパニング ツリーとして表され、変数はアークで、シンプレックス乗数はノード ポテンシャルで表されます。各反復で、入力変数は、デュアル乗数 (ノード ポテンシャル) に基づく何らかの価格設定戦略によって選択され、ツリーのアークでサイクルを形成します。出力変数は、サイクルのアークのうち、増加フローが最も少ないアークです。入力アークを出力アークに置き換え、ツリーを再構築することをピボットと呼びます。入力可能な非基本アークが残っていない場合、最適解に到達しています。

ネットワークシンプレックスアルゴリズムは、次のような多くの実用的な問題を解決するために使用できます。^[5]

• 積み替え問題
• ヒッチコック輸送問題
• 割り当て問題
• 半順序集合における連鎖と反連鎖
• 明確な代表者制度
• 二部グラフの被覆とマッチング
• ケータリング業者の問題

• ネットワーク問題の解決セクション14、p B-113に実行例が示されている。