大規模データに対する最大フロー求解アルゴリズムの実装技術の構築

短期共同研究
研究計画題目 大規模データに対する最大フロー求解アルゴリズムの実装技術の構築

研究代表者 瀧澤重志（大阪市立大学・工学研究科・准教授）

研究実施期間 平成27年6月8日（月）～ 平成27年6月12日（金）

研究分野のキーワード グラフ解析，離散最適化，高性能計算，最大フロー，アプリケーション開発，防災

目的と期待される成果 　
グラフ解析は物流解析，工学など広範な応用をもち，理論・応用の両面から数多くの研究がなされている．その一方で，大規模データを扱う計算機プログラムの開発は現在においてもなお発展途上の段階である．計算機プログラムの計算効率は，多階層メモリ内でのデータの配置方法や，加減乗除の順序に依存する．しかし，その効率化を実現するための一般的な枠組みはいまだ確立されておらず，状況に応じたアドホックな検討が必要なのが現状である．そのため，産業分野の利用者にとってはハードルが高く，一般的な枠組みが望まれている．
本研究では，グラフ解析における基本的な問題として特に最大フロー計算を取り上げ，大規模データに対する効率的な計算機プログラムの実装方法を整備する．最大フロー計算の応用対象として，特に避難計画策定を取り上げる．避難計画策定は，津波や地震などの災害発生時，被害が予想される地域にいる人々が安全な場所に迅速に避難できる計画を立てることを指す．これは，最大フロー問題としてモデル化することができ，それにより避難者が全体として最も効率よく避難する計画が得られる．避難計画策定を最大フロー問題として定式化するには，時間経過を表現することかできる「動的ネットワーク」を用いるが，実際の地理的情報を用いた計算では計算時間が非常に長くなる傾向にある．そこで，データ構造・データ配置・計算順序などを定量的に評価し，それらを計算機プログラムに反映することで，高速に動作するように効率化する．最大フロー計算で用いるデータ構造および計算手順は，グラフ解析において基本的なものであり，この効率化の過程で蓄積された知見は，他の問題にも幅広く展開可能となることが見込まれる．参加者は，アルゴリズム，ハードウェア，産業利用など多様な観点からの検討を可能にするため，民間企業，大学，公的研究所のメンバで構成する．

組織委員(研究集会)
参加者(短期共同利用) 瀧澤重志（大阪市立大学・准教授）
清水正明（日立製作所 中央研究所 PS部・部長代行）
斉藤努（構造計画研究所・テクニカルマネージャー）
藤澤克樹（九州大学マス・フォア・インダストリ研究所・教授）
神山直之（九州大学マス・フォア・インダストリ研究所・准教授）
佐藤憲一郎（独立行政法人海洋研究開発機構・特任研究員）