、‥∴Å十≠ト＿毒・一ニチギサ∵・−・・＿二き享．．、■モキ

品野 勇治
Il…＝＝‖＝‖‖‖‖‖＝＝‖‖＝‖＝‖＝‖＝‖‖＝＝‖＝‖‖＝＝‖‖‖＝＝‖‖＝‖‖‖＝‖‖‖‖＝‖‖‖‖＝＝＝‖＝‖＝‖＝＝＝＝‖＝‖＝＝＝‖＝‖＝‖＝＝＝＝‖＝‖‖＝川Illlll…l…‖‖＝＝＝‖＝＝‖‖＝＝＝＝‖＝＝＝‖‖＝＝‖‖＝‖＝‖‖＝＝＝‖＝＝‖‖＝‖＝‖‖‖‖＝‖‖‖‖‖＝＝‖＝＝仙】．、．∵ −、、、

分枝限定法は，組合せ最適化問題に対する列挙解法に基づく古典的なアルゴリズムである。1970年代初頭に，M．He且dと粗車Ka叩が分枝限定法により巡回セールスマン問題を解くことに成功して以来，様々な組合せ最適化閏題に適用されるようになった．その後，解法の一般化も行われ，今では分枝限定法は組合せ最適化問題に対する厳密解法を設計するための基本的な道具として定着している血 しかし，よく知られている事実ではあるが，たとえ分枝限定法を用いても，問題閻魔に博樹のデルゴ毒』滅ムの実装の規模が大きくなると現実的な時間内では解が得ら
図1：汎用ツ山ルPUBBれなくなるElj

1980年代後半になり，並列計算機が実用化されるにつれ，分枝限定法に並列処理を取り入れる試みがなさ望。炉U迅迅の概要れるようになる。当初は，対象とする問題個別に，利PUBBは，以下の特徴をもつ並列分枝限定法の開用する計算機アーキテクチャの特徴を生かして実装された。並列分枝限定法の実装は，並列計算機の知識と対象とする解法に対する知識の両方を持ち合わせる必要があり，困難であった。1990年代になると，特定の問題を特定の並列計算機環境へ実装するのではな
く，分枝限定法の汎用的なフレームワークをツール化

発￠実行環境を構築するための汎用ツールである．並列。分散環境の構築，データ転送には標準メッセージパッシング。ライブラリの1つであるPVM（ParallelVir−
tualMachime）を利用している■ よって，PVMが動作する並列計算機，ワークステーション①クラスタ，PCクラスタ上で動作可能である。

することでタ様々な問題に対する並列分枝限定法の開発を容易にする汎用のシステムがいくつか登場した。

汎用ツール並列分枝限定法のフレームワークを提供

本稿では，それらのツールの1つである分枝限定法並する汎用ツールである。ユーザは問題固有の利用

列化ツールPUBB（Parallelizat主omUtility払町臥anch−

者定義データ型と，それを用いた利用者定義関数

and】BoⅥnda且gor血ms）について，特に利用者を対象をプラグインとして開発することで，各問題に対として紹介する∴椚碓旧を利用した並列分枝限定法のする並列分枝限定法が実現できる（図1）・

開発には，C言語およびC＋＋言語が可能である。しかし，本稿ではC言語による開発を前提として解説する睦 また，説明は最／j、化問題を仮定して行う。

逐次処理として開発可能IJtJHHでは，プラグインするデータ型血関数の開発環境として，同じインターフェースを持っ逐次分枝限定法の実行ファイルを生成する開発キットを提供する。このため，

しなの ゆうじ東京農工大学工学部情報コミュニケー

ユーザは並列処理を意識することなく，並列分枝ション工学科限定法のプログラムが開発できる．ユーザが開発〒184−8588東京都／j、金井市中町2−24−16

したプラグインは，再コンパイル程度の手間で並E−mai恩：yShimamo＠cc．tmat．ac．Jp

列化される（図2）d

周層芝（4）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ3．PUBBが提供するフレ岬ムワーク
PUBBが提供する（並列）分枝限定法のフレームワークの概略を述べる．まず，図4に，分枝限定法の疑似コードをPUBI】のフレームワークにおける利用者定義関数群により示す．アルゴリズムの記述としては，メモリの解放等冗長な部分もあるが，並列を意識しない自然な表現であることを確課されたい．

図2：PUBBによる並列化

algorithmBranch」1nd＿Bound

begin（a）インスタンスを読み込む；（b）初期解を計算する；（c）／レート問題を生成する；￡＝i（ルート問題））；

While∠≠㊥do

begin
子問題P∈￡を選び，￡＝￡＼‡P）とする；（d）子問題の評価計算を行なう；（d−1）if暫定解が更新されたthen

begin

図3：PUBBが提供する制御方式￡から不要な子問題を除去する；（f）古い暫定解のメモリを解放する
多様な探索規則PUI】Bでは，標準として深さ優先，広がり優先，下界値優先，ユーザが定義した子問題の優先順位の昇順・降順の各探索規則をプログラム実行時に指定できる．また，PUBBの開発過

elldニ（d−2）if新たに子問題が生成されたthen￡に新しい子問題を追加する；（f）子問題Pのメモリを解放する
emd；

程において提案・実装された探索規則で，深さ優先探索と下界値優先探索を組み合わせたハイブリッド探索も標準で指定できる．ハイブリッド探索では，まず，深さ優先探索が適用される．実行（e）解を出力する；（f）インスタンスのメモリを解放する
end．
図4：分枝限定法の疑似コード

可能解が見つかるか，暫定解よりも良い実行可能解が見つからないことが保証されることで分枝∠は子問題プールと呼ばれるものであるが，その管が停止すると，生成された子問題群の中から最良理はPUBBによって行われ，ユーザが考慮する必要はの下界値の子問題を選択する．その後，分枝が停ない．実行時のパラメタ指定にしたがって，PUBI∋が止するまで，再度深さ優先探索が適用される．分子問題プールから子問題を取り出し，利用者により定枝が停止すると再び最良の下界値の子問題を選義された評価計算を行う関数へ渡す．つまり，分枝木択する．以上の換作を繰り返す．の標準的な探索順序（探索規則）は，利用者定義関数開発時に意識しなくても実行時に変更できる．並列実多様な制御方式PUBBでは，並列分枝限定法の実装

行療境においては， （d）子間膚の評価計算を行う の上での代表的な制御方式である中央制御型（部分が，複数の計算機上で実行される．また，子問題Master−Slaveモード），分散制御型（Fu11y−

プールの個数もPUBI】の動作モードにより異なる．

Distributedモード），混合制御型（Master−Slave

Master−Slaveモード時は，実行環境全体に1つ子問toFullyDistributedモード）を1つのシステム

題プールが生成される．子問題プーールから子問廣が取で実現している．また，制御方式は実行時に指定り出されると，動作環境上で空きのある計算機へ対しできる（図3）・2000年3月号て送られ，評価後結果として子問題群，あるいは解を© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（5）113受信する。したがって，このモードでは子問題の転送

図4の擬似コードに対応する問題固有の関数群は，次のコストが大きい。しかし，探索順序の制御はプールのように分類される：が1つであるため正確に行え，子問題の評価計算に時（a）イン鼠タン鼠デ血タの読み込み間を要する解法に対しては有効である。
FⅥ11y一皿i如ibutedモード時は，動作環境上の各計算機に手間題プールが生成され，図4の疑似コードにおけるぬ立乱◎ル山プの部分は，それぞれの計算機上で，インスタンスを読み込み，インスタンスデータを生成する。
仲）初期解の計贋

それぞれの子問題プール内の子問題に対して実行さ一番初めの評価計算に先だって，初期暫定解をれるu 子問題プ山ルにおいて子問題の枯渇やあふれ計算する．初期解を求めない場合でも，自明なが起こらない限軋他の計算機との子問題の転送は行botユndのみを持つ解を生成する。

わない。じかし，計算機閣の負荷分散処理のためオーバ山ヘッドは生じる。また，分枝木における探索順序の正確な制御は困難となるため，一般に最適解が得られたときに構成きれる分枝木は大きくなる．評価計算がデータ転送時間と比較して相対的に短時間の場合（c）』♭仙睦問題の作成

ルート問題に関する子問題データを作成する．
（d）草間題の評価

子問題の評価計算をする．このとき，や巨太規模な問題で子間腰プールの大きさが1台の計（d瑚暫定解を更新する解を見つけたら，解デー算機では足りない場合に有効である。

タ型で返す．

Mas七即MSはvetの『ully−Dist『ibutedモ山ド時は，最初はMas七即一別aveモーげとして動作し，パラメタで指定された個数の子間腐が生成されると『ully−Distrib雨ed（d開票）新しい子問題を生成する必要があれば，それらを子問題データ型で返す。

モードへ切り替わるp 切り替え時には，Master−Slaveモードにおける子問題プールから，各子問題を下界債順に選び，各計算機ヘラウンド叫コピン方式で分配する。このため，『Ⅶ且1y−Di由五butedモードへ切り替わった時点では，子問題の個数，および，各計算機が保持している子問題の下界値の合計という観点でもほぼ（e）解の出力

初期解とPU儲眉終了後の解（一般に最適解）を出力する．
（厨）メ驚召』の解放

デ山夕型のメモリを解放する。

均一になる。この状態からの負荷分散は，過去の数値実験結果では♪比較的少なく済み，特に大規模な問題を解く場合に有効であった。

．．ニ ー ●●・． ．・J轟蕪・−（g）DⅦmp関数
デバッグのために，データ型の情報を出力する．
逐次分枝限定法の実装は以上で充分である．そしPU蟄BによるC言語での分枝限定法の実装概略を述べる。ユーザが実装する必要があるのは，データ型て，並列化のみに必要な関数は次の1つである：（払）デ脚タの野鼠ck／U叩aC駄と問題固有の関数群である、データ型は次の3種類でPVMの提供する基本pack／unpack関数を用いて，ある：デ山夕型をpack／unpackする・−インスタンスデ州タ5。並列化の効果につむ鴨竃

これはタ 解くべき問題のデータである。
並列分枝限定法と呼ばれる解法の中には，各子問題一子問題データの評価計算にも並列処理を適用している場合がある。

各子問題はインスタンスデータと付加的な情報によって記述できるb 子問題データは付加的な情報に関するものである。
一解データ

これは，実行可能解のデータである．
椚瀾（6）しかし，ここではPUBBのみによって実現できる，複数の子問題を同時に処理するような並列化に限定する。複数の子問題を同時に評価する並列動作を行った
場合仁異常加速（speed−uPanOmaly）仁異常損失（detri−memtalanon−aly）という現象が生じることが良く知ら© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチように，並列実行時に，逐次処理では生成されなかっ並列処理（子問題2個を同時に処理）

逐次処理

p＝1，t＝1 ＼＼＼感1 t＝

p＝1，t＝2

p＝り＝1 ＼＼＼ k2窟

た子問題が生成され，余分な子問題の処理を行うことで生じる．図6では，ま＝3の時点で，プロセッサへ分枝木の右側に位置する子問題が割当られている．逐次処理と比較して子問題の処理順が変わっているように思われるかもしれないが，f＝2で行った評価計算

p＝1，p＝1， p＝1，p＝1，t＝4 t＝5 t＝7 t＝8

後，同時に4つの子問題が生成される場合，生成されp＝計井に使用するプロセッサ♯号，t＝計算開始からの蛭過時間（u・t・川鵬Itime）た4つの子問題中での処理順は非決定的である．現実

頂点の中の数価は下界価的にも，わずかに右側に位置する子問題が先に生成さ①暫定解を更新した頂点一合評価計算を行わすに限定された頂点れた場合，このような現象が生じる．

PUBBにより並列分枝限定法を実現して行った数

図5：異常加速の例

値実験結果においても，これらの現象は観測されてい並列処理（子間規2個を同時に処理）る．実験結果から，探索規則を比較的制御できる中央制御型を用いて，ハイブリッド探索を行った場合，少ない台数（5台程度まで）による並列処理では異常加速を生じやすい．このような現象が生じるのは，分枝限定法を実行した場合に，解が更新されることが前提

p＝1，p＝2，p＝1p＝2，である．初期暫定解の精度が高い場合には，生じ難い

t＝4 t＝4 t＝5 t＝5のは当然であり，特に初期暫定解が最適解であった場

p＝計井に使用するプロセッサ書号， t＝計算朋始からの経過時憫（u．t．：uI山time）
頂点の中の数値は下界価◎暫定解を更新した頂点
・⇔・評価計算を行わすに限定された頂点合には上記の観点からの異常加速は起こり得ない．また，経験上，利用する台数が100台程度になると，特殊なデータを用意することがなければ，極端な異常

図6：異常損失の例

加速は生じ難い．一方，異常損失についても，全体としての探索順序が正確に制御できる場合には，特殊なれている［2】．まず，この現象について具体的に説明しデータを用いない限り，生じることは少ない．比較的，よう．

異常損失を生じやすいのは深さ優先探索を行った場合

ちをp個のプロセッサによる計算時間とする・p個であった．ただし，用意されていたプロセッサの台数のプロセッサを使用して計算を行ったとき，加速率ちが，本来解くべき問題に対して多すぎた場合や，子問は，ち＝れ／ちと定義される・通常，並列処理を適用

題プールを複数持つような実装に対して，負荷分散をした場合，並列化に伴うオーバーヘッドにより，ち＜誤ると生じやすくなる．

pとなる．しかし，分枝限定法に対して並列処理を適

図7は，PUBBを利用して並列分枝限定法を実行用した場合，図5のように，最終的に生成される分枝した場合に，計算時間が短縮する様子を示す典型的な木の大きさが，逐次処理と比較して小さくなることが例である．ワークステーションとして，柑MRS／6000ある．計算開始後のある同じ経過時点において逐次処

Mode125T（CPU：PowerPC601（66MHz），メモリ：

理と並列処理を比べたとき，逐次処理では見つからな64M）を用い，各ワークステーションが10M bpsのかった実行可能解が，並列処理では見つかることがあイーサネットにより接続されてた環境を用いた．利用る．すると，このみつかった実行可能解により，いくしたワークステーションの台数は，最高101台（全体のつかの子問題が限定され‥分枝木が小さくなる．この管理用にワークステーションを1台用いるので，評価場合，ち＞pという極めて有効な並列処理の効果が計算を行う部分であるSolverは最大100）である・古期待できる．このような現象が異常加速である．

典的なHeldLKarpの解法を用いて，TSPLIBのデータ一方，多くのプロセッサを利用して実行したにもから都市数が70（st70）の巡回セールスマン問題を解関わらず，逆に遅くなるという現象がある．つまり，いた・探索規則として，下界値優先探索（Best），ハイpl＜p2の場合に，ち1＜ち2が生じる・このような現ブリッド探索（Hybrid）を適用し，PUBBが提供する3象は，異常損失と呼ばれる．具体的には，図6に示す
2000年3月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（7）‖50 0 0爪︶

0

的には探さ優先探索でないと実行不可能となる。このようなパラメタ設定において，最大クリーク問題に対するDIMACSのベンチマーク問題，および，二次割爪U

OO

クラスタ環境で解いた結果について紹介する（衷1フ2C︵U￠S﹀む∈仁ぎ竜d∈OU

当問題に対するベンチマーク問題（QAP軋IB）を，PC参照）。PCには，エプソンダイレクト社のEm舶avoでA甘−700C（CPU脛emtiumI亙400M二Hzタ メモリ：256M）を利用した鶴 このPC21台を3Com社製SuperStackI‡迅ase且ine川／100Swi七ch24portで接続してPCタラスタを構成した
12 3

5 7 1020
Numbero†Solvers

40

衷1：のIMACSの問題に対する結果

701の0Time（sec）
p＿hat1500−2

図7：計算時閤の短縮効果を示す例

子問題数34810 623538050 無

p＿ぬatlOOO−3 1256613 23901006812 無種類の制御方式フ中央制御型（MS），分散制御型（『叫，表2：QÅPL耳Bの問題に対する結果混合制御型（MSto『わ）により実行した中図7中の各プ
ロットはタ 並列実行にともなう非決定的な振る舞いをmⅦg21排除するため，5回の実行の平均値を用いている。

13287 593656913 無mⅦg22 1∠基7378 6712276783 無

まず，ここに示した結果は，中央制御型で動作する

nmg24 1269218 44317904109 無ことから，問題の規模という観点からは比較的小規模であることに注意されたい．この場合，中央制御型（MS）がもっとも効果的な並列分枝限定法を実現しているけ これは，解法が評価計算に時間を要したので，子問題の転送コス恥よりも探索順の制御が有効に機能しているためである。ハイブリッド探索は下界値優先探索よりも，さらに計算時間の短縮効果が大きい場合がある．特に，Sの且ve訂数が70では超線形で計算時間を短縮している轟分散制御型（『D）においては

表172中の 更新 は，分枝限定法実行における，解の更新の有無を示す∴つま畑 表1：2中のいずれの結果においても，初期暫定解を求める近似解法により，最適解が得られていたことになり，全ての計算は最適性を保証するために費やされている．この場合，異常加速や異常損失は生じない。おおよそではあるが，この環境での加速率β20は，16程度であった。

Sの且ve訂数が増加しても計算時間が短縮しない場合が生じる。これは，PUBBが，レスポンスタイムで定義

臥 炉U迅蟄開発卑ッ睦

される距離の近い部分に位置する計算機とのローカ

PUBBのアプリケーションを開発するための開発キルなやり取りにより負荷分散を行うため，全体としてット，および，マニュアルを以下のU嗣皿にて配布しての負荷分散には失敗していると考えられる。このよういる．

な状懐が，混合制御型（MStoF叫を適用することで大臨も℃p：／／a且。℡立。もua七■aC・jp／￣ys払inamo／pubb

幅に改善されることがわかる．

最後に夕子問題の評価計算が短時間である解法を用

PUBB開発キットでは，プラグインとなる関数群かい，生成される子問題数が極端に多かった場合についら1つの実行モジュールが生成されるため，並列処理ても言及する（詳細は，【3】参照）・この場合，複数の子は全く意識せずに開発が行える．また，PUBBのフ間腰プレルを保持する，分散制御型，あるいは，混合レームワークが提供する機能が利用できることによ制御型での動作が前提となる。通常，動作環境に存在り，分枝限定法の開発環境としても有効である．例えする全ての計算機に夕子問題を3個程度割り当てられば，探索規則はパラメタを変更することで実行時に切るだけの子問題が生成された後，分散制御型に切り替り替えられる。複数の探索法を適用し，得られた解のえているっ また，大規模な問題を扱う場合には，現実目的関数値が一致することを確認することは，デバッ

耶鳩（8）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズロリサーチ

で，興味のある方はそちらを参照されたい．
また，本稿では，C言語による開発を紹介したが，C＋＋言語による開発も可能である．PUI柑は，C＋＋言語によって記述されている．PUBBのように，利用者定義関数をプラグインとして開発するシステムにおいて，C言語で開発されたシステムに対して，プラグインがC＋十言語で記述された場合，問題を生じることがある（開発当時は，リンクそのものが困難であった）．現在，STLやLEDAなど強力なクラスライブラリが利用できるようになっているので，C＋＋言語によるアプリケーション開発のメリットは大きい．C＋＋
言語によるインターフェースについては，参考文献［4】を参照されたい．
図8：VABBによる分枝木の表示例

グに有効である・また，桧垣正浩氏（現SarionSystemsResearch）によるVABB（Visualizer and Analyzer fbr
Branch−andrBoundalgorithms）を動作させることで，分枝限定法実行時に生成される分枝木を可視化できる（図8参照）・アプリケーション開発時には，可視化のためのコードは1行も書く必要はない．こちらは，デバッグに有効なのはもちろんのこと，分枝限定法の動作説明にも有効である．

PUBBそのものも，STL等を利用したコードへと書き換えたいと考えている．PUBBは，他の汎用の並列分枝限定法に対するツールと比較して，利用者定義関数の定義は，もっとも単純であり，その数も少ない．
単純なユーザインターフェースにより，十分な汎用性が維持できるのであれば，インターフェースとしては好ましい．書き換えに際しても，C言語によるユーザインターフェースは，現状を継承するように心がけるつもりである．しかし，ユーザインターフェースに不自然に感じる部分等あれば，PUBBと並列分枝限定法の汎用ツールの向上のため，幅広いご意見を頂ければ幸いである．

7．おわりに参考文献

べンチマーク問題に対する数値実験結果は，近似解法で得られた結果がたとえ最適解であっても，その最適性を保証することが如何に困難であるかを示している．近似解法の研究と比較して，厳密解法を実装し［1］茨木俊秀，組合せ最適化一分枝限定法を中心として‥産業図寄1983．
［2］T・H・Laiand S・Sahni， Anomaliesin parallel

た研究が少ないのは，実装の困難さにも関わらず，近branch−and−bound algorithms． ComrT nications

似解法が扱う問題規模と比較して，厳密解法の扱う問

げ班eAα峰27（1984）594−602．

題規模が極端に小さいことにも起因すると考えられ［3】Y・Shinano，rr・Fujie‥Y．IkebeandR．Hirabayashi，る．しかし，厳密解が必要な局面や，少なくとも精度㍑SoIving the Maximum Clique Problem uslngがある程度保証された解が必要な場合には，分枝限定PUBB， proc．げ兢e躇抗力両脚而血Ⅷ＝毎而は法が唯一の解法となることさえある．そのような場面

Pmceβざ盲円g5ympoβ壱um（1998）326−332．

で，実装の手間を省くことにPUBBが貢献できれば幸いである．

【4］Y・Shinano∫M・HigakiandR．Hirabayashi， AnIn−

terface DesignIbr GeneralParallelBranch−and−

本稿では，PUBBの内部構造についての解説は割愛

Bound Algorithms．

A．Ferreira．J．Rolim．Y．Saad

し，利用する場合に必要となる手間と，実際にPUBB

and T・Yang（eds・），PartzllelAlgorithms hrIr−

により並列分枝限定法を実現した場合に期待できる

regularly Structured Problems，LNCS，Springer−

効果を示すため，過去の数値実験結果を紹介した．

Verla臥1117（1996）277−2錮．

PUBBのタスク構成等の詳細については，上記URL

よりPUBBに関連する論文がダウンロードできるの2000年3月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（9）117