Loading article…
「オークションアルゴリズム」[ 1 ]という用語は、割り当て問題や、線形および凸/非線形コストを持つネットワーク最適化問題を解決する組み合わせ最適化アルゴリズムのいくつかのバリエーションに適用されます。オークションアルゴリズムは、複数の購入者に提供される一連の製品の最良の価格を決定するためにビジネスの場面で使用されてきました。これは反復的な手順であるため、「オークションアルゴリズム」という名前は、複数の入札を比較して最良のオファーを決定し、最終的な販売が最高入札者に渡る販売オークションに関連しています。
オークションアルゴリズムの原型は、二部グラフにおける純利益を最大化する最適な価格と割り当てを見つける反復法であり、最大重みマッチング問題（MWM）である。[ 2 ] [ 3 ]このアルゴリズムは、1979年にディミトリ・ベルツェカス によって初めて提案された。
オークションアルゴリズムとεスケーリング[ 1 ]の考え方は、単一商品線形ネットワークフロー問題に対するプリフロープッシュアルゴリズムにおいても中心的な役割を果たしています。実際、最大フローに対するプリフロープッシュアルゴリズムは、割り当て問題として再定式化した後、1979年の元のオークションアルゴリズムを最大フロー問題に適用することで導出できます。さらに、線形最小費用フロー問題に対するプリフロープッシュアルゴリズムは、問題を同等の割り当て問題として再定式化した後、元のオークションアルゴリズムを適用することで得られるε緩和法と数学的に等価です。[ 4 ]
最短経路問題を解決するオークション アルゴリズムの後期の変種は、 1991 年に Bertsekas によって導入されました。[ 5 ]これは、有向グラフ で最短経路を見つけるための単純なアルゴリズムです。単一の始点/単一の終点の場合、オークション アルゴリズムは始点から始まる単一の経路を維持し、各反復で単一のノードによって延長または短縮されます。同時に、双対関数の値を改善または維持するために、各反復で最大 1 つの双対変数が調整されます。複数の始点の場合、オークション アルゴリズムは並列計算に適しています。[ 5 ]このアルゴリズムは、他のネットワーク フロー問題に対するオークション アルゴリズムと密接に関連しています。[ 5 ]計算実験によると、オークション アルゴリズムは、すべての終点の最短経路問題に対しては一般的に他の最先端のアルゴリズムよりも劣りますが、終点が少ない問題 (1 点よりかなり多く、ノードの総数よりかなり少ない) に対しては非常に高速です。 Bertsekas、Pallottino、およびScutellaによる論文「最短経路のための多項式オークションアルゴリズム」を参照してください。
最短ハイパーパス問題に対するオークションアルゴリズムは、1998 年に De Leone と Pretolani によって定義されました。これは、2004 年に E. Jason Riedy によって記述された、重み付き二部グラフマッチングのための並列オークションアルゴリズムでもあります。[ 6 ]
最短経路問題に対する（逐次）オークションアルゴリズムは、技術論文で報告されている実験の対象となっている。[ 7 ]実験では、オークションアルゴリズムは、単一出発地から全目的地への問題の最適解を見つけるための最先端の最短経路アルゴリズムよりも劣っていることが明確に示されている。[ 7 ]
オークションアルゴリズムでは、総利益は反復ごとに単調に増加するが、ハンガリーアルゴリズム（Kuhn、1955年；Munkres、1957年）では、総利益は反復ごとに厳密に増加する。
有向グラフ内の最短経路を見つけるためのBertsekasのオークションアルゴリズムは、ランダムグラフや目的地が少ない問題において非常に優れた性能を発揮すると評判である。[ 5 ]