平成8（1996）年度　共同研究Ａ実施報告書

課題番号	8−共研−20			専門分類		2
研究課題名	汎用完全分散型並列分枝限定法実装ツールの開発／評価
フリガナ 代表者氏名	ヒラバヤシ　リュウイチ 平林　隆一			ローマ字
所属機関	東京理科大学
所属部局	工学部第二部
職　　名	教授
所在地
TEL				FAX
E-mail
URL
配分経費	研究費	0千円	旅　費		0千円		研究参加者数	8　人

研究目的と成果（経過）の概要

並列分枝限定法の実装には，対象とする問題固有の下界値計算法を主とするアルゴリズムの開発と分枝限定法の実行時に生成される子問題群をプロセッサ群へ割り当てる負荷分散を実現するアルゴリズムの開発が必要となる．各アルゴリズムは，比較的独立したものである．本研究の目的は，後者の負荷分散のアルゴリズムを実装した汎用の並列分枝限定法動作環境の開発／評価である．開発されたシステムにより，比較的容易に完全分散型の並列分枝限定法の実現が可能となる．


平成8年度は、これまでに開発してきた完全分散型並列分枝限定法システムを評価し、その結果を考慮して負荷分散方式の調整を行った。評価は、まずマスター・スレーブ型へ実装していた解法と同じTSPの解法を、開発したシステム上にも実装し、数値実験を実施することで行った。統計数理研究所のSP2上では、下界値を利用した負荷分散方式の効果を調べた。
これまでは、個々のプロセッサの保持する子問題数により負荷分散を行っていたが、下界値の情報を加味した負荷分散を開発中のシステムに加えた。しかし、並列分枝限定法実行時に生じる、負荷の不均衡は改善されなかった。原因は、不均衡の改善処理の開始の判断に使用する情報が、実行時の負荷分散の状態を正確反映できないためである。この結果は、修士論文としてまとめられた。
また、CARP(Capacitated Arc Routing Problem)を、開発したシステムへ実装し、SP2上で動作させて解いた。これまで、頂点数8・枝数15程度までのインスタンスしか解けていなかったが、今回のシステムでは、頂点数31・枝数50のインスタンスに対して厳密解を得た。
この結果は、ISORA'96の口頭発表時に紹介された。最後に、混合制御型の並列分枝限定法の開発も行った。混合制御型は、マスター・スレーブ型から完全分散型へ並列分枝限定法の実行時に切り替わる制御方式である。こちらは、主にワークステーション群を使用した数値実験を実施した。100台のワークステーション群上で数値実験の結果は、IPPS'97にて紹介された。

当該研究に関する情報源（論文発表、学会発表、プレプリント、ホームページ等）

Y.Shinano, M.Higaki, R.Hirabayashi,An Interface Design for General Parallel Branch-and-Bound Algorithms,Lecture Notes in Computer Science, 1117, Springer, 277-284, August 19, 1996.
M.Kiuchi, Y.Shinano, R.Hirabayashi, Y.Saruwatari,An Exact Algorithm for the Capacitated Arc Routing Problem Using the Parallel Branch and Bound Method,Lecture Notes in Operations Research, 2, World Publishing Corporation,December 11, 1996.
Y.Shinano, K.Harada, R.Hirabayashi,Control Schemes in a Generalized Utility for Parallel Processing,In Proceedings 11th International Parallel Processing Symposium,IEEE Computer Society Press, 621-627, April 1, 1997.

品野勇治、檜垣正浩、原田賢一、平林隆一、完全分散型分枝限定法並列化ツール、日本OR学会春季研究発表会、1996年5月15日・16日.
Shinano, M.Higaki, R.Hirabayashi,An Interface Design for General Parallel Branch-and-Bound Algorithms,Third International Workshop IRREGULAR'96, August 19-21, 1996.
品野勇治、並列分枝限定法の制御方式について　RAMP(数理計画法特設研究部会）定例研究会、1996年11月30日。
M.Kiuchi, Y.Shinano, R.Hirabayashi, Y.Saruwatari, An Exact Algorithm for the Capacitated Arc Routing Problem Using the Parallel Branch and Bound Method, Second International Symposium, ISORA'96, December 11-14, 1996.
Y.Shinano, K.Harada, R.Hirabayashi, Control Schemes in a Generalized Utility for Parallel Processing,11th International Parallel Processing Symposium, IEEE in cooperation with ACM SIGARCH etc., April 1-5, 1997.
A.Ferreira, Y.Shinano, M.Higaki, Making a Standard Branch-and-Bound Interface for Parallelizations of the Algorithms, SCOOP(Solving COmbinatorial Optimization Problem in Parallel)Workshop, April 5, 1997.

研究会を開催した場合は、テーマ・日時・場所・参加者数を記入してください。

本システムは，分枝限定法のスケルトンを提供する．スケルトンに即して各問題固有の下界値計算や分枝変数選択のルーチンを記述することにより，本システムは，様々な問題に対して適用可能である．また，以前の研究で実現したマスター・スレーブ型のシステムを使用して行った数値実験の結果から得られた知見をもとに完全分散型のシステムとして再構築した本システムは，1000個以上のプロセッサを使用した環境で，動作可能であることを目標に開発されている．さらに，分枝限定法の特徴である，計算に必要な資源が予測できないという特徴に対応するために，実行中に動作環境の変更を可能とするシステムとなっている．例として，３個のプロセッサで数日間実行していたが解けない場合，もう５個のプロセッサを追加するということが可能である．組合せ最適化問題は本質的に多大な計算を必要とするために，並列計算機上で動作することが望まれる．そのために，ＰＶＭ上で動作する本システムの開発／評価に対しても，並列計算機環境が必要不可欠である．

研究参加者一覧
氏名	所属機関
池辺　淑子	東京理科大学
井本　税	東京理科大学大学院
木内　正明	東京理科大学大学院
佐藤　良	東京理科大学大学院
品野　勇治	東京理科大学大学院
原田　賢一	東京理科大学大学院
水野　眞治	統計数理研究所