大規模なネットワークフロー問題に対する効率的なアルゴリズムの開発に関する研究

大規模なネットワークフロー問題は線形制約を持つ凸計画問題に定式化される.本研究の目的は,この様な問題に対する効率のよいアルゴリズムを開発し,その有用性を数値実験で確かめることであった.凸計画問題に対する双対解法に乗数法,近傍点法等があるが,本研究では大規模ネットワークフロー問題の重要な例題である多品種流問題に主双対近接点法を適用した.この方法は,従来の主双対近接点法と異なる手順で拡張ラグランジュ関数の鞍点を計算するため,双対最適化に準ニュートン法を直接適用することが可能となっている.また,拡張ラグランジュ関数を構成する際,各品種の流れの総和に関する制約条件のみを緩和しているので,仮にアルゴリズムの反復を途中で打ち切っても,その時点で得られている近似解は,少なくとも各品種ごとの流れ保存条件を満たすことが保証されるが,これは実際の応用上非常に好ましい性質である.また,このアルゴリズムの効率を調べるために,FORTRAN77を用いてコード化し数値実験を行ったが,それによるとかなりのサイズのテスト問題を実用的な時間で解くことができることがわかった.

大規模なネットワークフロー問題は線形制約を持つ凸計画問題に定式化される.本研究の目的は,この様な問題に対する効率のよいアルゴリズムを開発し,その有用性を数値実験で確かめることであった.凸計画問題に対する双対解法に乗数法,近傍点法等があるが,本研究では大規模ネットワークフロー問題の重要な例題である多品種流問題に主双対近接点法を適用した.この方法は,従来の主双対近接点法と異なる手順で拡張ラグランジュ関数の鞍点を計算するため,双対最適化に準ニュートン法を直接適用することが可能となっている.また,拡張ラグランジュ関数を構成する際,各品種の流れの総和に関する制約条件のみを緩和しているので,仮にアルゴリズムの反復を途中で打ち切っても,その時点で得られている近似解は,少なくとも各品種ごとの流れ保存条件を満たすことが保証されるが,これは実際の応用上非常に好ましい性質である.また,このアルゴリズムの効率を調べるために,FORTRAN77を用いてコード化し数値実験を行ったが,それによるとかなりのサイズのテスト問題を実用的な時間で解くことができることがわかった.