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

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

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

分枝カット法は、線形計画緩和に基づいた分枝限定法に切除平面法を加えた解法であり、近年組合せ最適化問題の厳密解法として成功を収めている。一方、分枝限定法の並列化に対して汎用実装ツールの開発も盛んであるるが、それを分枝カット法にまで拡張したものは少ないので、本研究ではその拡張を試みる。


平成10年度は，これまでに行ってきた結果を統計数理[1]にまとめた．並列分枝カット法に対する汎用実装ツールの部品を開発した．

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

品野勇治，藤江哲也： 汎用並列分枝限定法ツールPUBBによる組合せ最適化問題の厳密解法，数理統計，Vol.46,No2, pp.411-431, 1998.

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

本研究により開発するツールは、並列分枝カット法のスケルトンを提供する。スケルトンに即して、問題固有のカット（切除平面）生成方法およびそのマネージメント方法を記述することにより、様々な問題に対して適用可能となるようなスケルトンを設計する。これまでに、並列分枝限定法を実現する汎用ツールを開発している。開発されているツールはPVMを利用しており、完全分散型のアーキテクチャを持つ。また、実行中に動作環境を変更することも可能である。これらの特徴は、特に大規模な問題を解くためには必要不可欠であるが、実現されているシステムはあまりない。本研究で開発するツールは、これまでに開発してきたツールを拡張するものである。組合せ最適化問題に対する厳密解法は、本質的に多大な計算を必要とするために、並列計算機上で動作することが望まれる。そのために、PVM上で動作する本ツールの開発に対しても、並列計算機環境が必要不可欠である。

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