2次コスト多品種流問題に対する並列型主双対内点法^1

スポンサーリンク

概要

論文の詳細を見る
本論文では、分離可能な2次のコスト関数をもつ多品種流問題に対して主双対内点法を適用し、それを制約条件のブロック構造を利用して並列化することを試みる。ここで提案するアルゴリズムにおいては、主双対内点法の各反復で解くべき連立方程式を、各品種に対応する複数の連立方程式とアークの総流量上限制約に対応する一つの連立方程式に分解し、それらを共役勾配法を用いて並列的に解く。また、共役勾配法の実行において、適切な前処理を行なうことにより探索点が非負領域の境界に近づいたときに生じる数値的悪条件を克服するとともに、連立方程式の係数の処理に工夫を加えて桁落ちによる計算誤差の発生を抑える。提案したアルゴリズムをコントロール並列型の計算モデルによって実現し、さらに並列計算機CM-5を用いて実際に数値実験を行なうことにより大規模な多品種流問題が効率よく解けることを確かめた。

著者

関連論文

もっと見る

スポンサーリンク