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

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

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

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


平成9年度は，これまでに開発してきた完全分散型並列分枝限定法システムを利用して，インターネットによって配布されている最大クリーク問題の標準問題を解いた．結果としては，これまでに最適解が得られていなかった問題5問に対して最適解を得た．
利用した上界値計算は，これまでに本システムで扱ってきた解法と，評価計算が短時間で終了するという観点で異なっている．そのため，コミュニケーションのコストを低く押さえることが要求された．SP2のＳＰスイッチを利用することで，これまでに利用してきたイーサーネットによるコミュニケーションよりも期待がもてると考えた．
しかし，PVMeの利用，およびLoadLevelerを経由した本システムの実行時に，解決困難な問題が種々生じたためSP2上での実行を9年度は断念した．標準問題の解は，以下2点の改造をシステムへ加えた後，イーサネットにより接続された51台のワークステーション群により得た．
(1)負荷分散のためのコミュニケーション回数をパラメータによって調整
(2)子問題を，あるタスクから別タスクへ転送するときの子問題選択規則の追加．結果は，IPPS'98にて紹介された．

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

[1]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.
[2]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.
[3]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.
[4]Y.Shinano, T.Fujie, Y.Ikebe, R.Hirabayashi,
Solving the Maximum Clique Problem Using PUBB,In Proceedings 12th International Parallel Processing Symposium & 9th Symposium on Parallel and Distributed Processing,IEEE Computer Society Press, 326-332, March 30, 1998.

[1]品野勇治，檜垣正浩，原田賢一，平林隆一，完全分散型分枝限定法並列化ツール，日本OR学会春季研究発表会，1996年5月15日・16日.
[2]Shinano, M.Higaki, R.Hirabayashi,An Interface Design for General Parallel Branch-and-Bound Algorithms,Third International Workshop IRREGULAR'96, August 19-21, 1996.
[3]品野勇治，並列分枝限定法の制御方式について，RAMP(数理計画法特設研究部会）定例研究会，1996年11月30日．
[4]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.
[5]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.
[6]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.
[7]Y.Shinano, T.Fujie, Y.Ikebe, R.Hirabayashi,Solving the Maximum Clique Problem Using PUBB,In Proceedings 12th International Parallel Processing Symposium & 9th Symposium on Parallel and Distributed Processing,IEEE in cooperation with ACM SIGARCH etc., March 30 - April 3, 1998.

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

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

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