分枝限定法における新たな探索法の提案
A New Search Strategy in Branch-and-Bound Algorithms
山口 一章
1∗斎藤 寿樹
1増田 澄男
1Kazuaki Yamaguchi
1Toshiki Saitoh
1Sumio Masuda
11
神戸大学大学院 工学研究科
1
Graduate School of Engineering, Kobe University
Abstract: The branch-and-bound method is used in many exact algorithms for optimization problems. In most case, those algorithms are implemented with the depth first search. Other search strategies are rarely used because they require large storage areas. In this paper, we propose a new search strategy, the widening search. The widening search greedily finds a solution at first, and then gradually widens the search space. The storage size required by the widening search is almost same as the depth first search. We implemented the branch-and-bound algorithm for the maximum weight clique problem with the depth first search and the widening search and compared their performances. Experimental results show that the solutions by the widening search are much better than the solutions by the depth first search.
1
はじめに
分枝限定法は分枝操作と限定操作からなり，最適化問 題の（大域的）最適解を求めるのに用いられる．最適化 問題には最大化問題と最小化問題があるが，以下では説 明の都合上，最大化問題として話を進める．分枝限定法 には様々な実装方法があるが，その一例を Algorithm 1 に示す．アルゴリズム中，f (x) は解 x の評価値を計 算する関数であり，U B(P ) は問題 P の解の評価値の 上界を計算する関数である．変数 x∗ は暫定解（それ までに求まった最良の実行可能解）である．x∗ には Algorithm 1 を実行する前に初期値として自明な可能 解を入れておく． Algorithm 1 は問題 P が解を持たない場合は何もせ ず抜ける（2 行目）．P の最適解が容易に求められる場 合は P の最適解を求め（4 行目），より良い解が求ま れば暫定解の更新を行う（5 行目）．容易に解けない場 合は上界テストを行い，P が良い解を持たない場合は 枝刈りを行う（8 行目）．枝刈りが行われない場合は P からいくつかの部分問題を作成し（10 行目），部分問 題の質が最も良い（と思われる）ものを P0とし，以降， 質の良さの降順に P1, P2, . . . と順序付けをする．その 後，P0から順に再帰的に解を調べる（11∼ 13 行目）． 与えられた問題を根とし，各々の問題に対しその部 分問題を子とする根付き木で表現したものを探索木と 呼ぶ．Algorithm 1 は探索木を深さ優先探索する．深さ ∗連絡先：神戸大学大学院工学研究科 〒 657-8501 神戸市灘区六甲台町 1-1 E-mail: [email protected] Algorithm 1 分枝限定法 INPUT: Problem POUTPUT: Optimum solution x∗
1: procedure Branch and Bound(P ) 2: if P has no feasible solution then return
3: else if P is easily solvable then
4: Find the optimum solution x of P 5: if f (x∗) < f (x) then x∗← x 6: end if
7: return
8: else if U B(P )≤ f(x∗) then return 9: end if
10: Create subproblems P0, P1, . . . , Pk from P 11: for i from 0 to k do
12: Branch and Bound(Pi) 13: end for
優先探索の分枝限定法は Algorithm 1 のように再帰呼 び出しを使って簡潔に記述することができ，また，計 算過程において必要な記憶領域が少ないという長所が ある．深さ優先探索以外の探索順についても研究が行 われているが [1]，他の探索法では展開中の部分問題が 深さ優先探索に比べ多くなり，より多くの記憶領域が 必要となる． 本稿では分枝限定法における新たな探索法として幅 制限探索と拡幅探索を提案する．幅制限探索は深さ優 先探索において有望な部分問題のみ探索するものであ り，最適性の保証はないが効率的に高い確率で良い解 を求める．拡幅探索は最適性を保証しかつ少ない記憶 領域を用いてできるだけ早い段階で良い暫定解を求め る．拡幅探索は一般的なメタ戦略 [2][3] とは仕組みが異 なるが，最適化問題に対する汎用の枠組みとしてメタ 戦略と同様に用いることができる． 以降の構成は以下の通りである．まず幅制限探索と 拡幅探索について順に述べる．次に拡幅探索の性能を 計算機実験により性能する．最後にまとめと今後の課 題を示す．
2
幅制限探索
幅制限探索を Algorithm 2 に示す．幅制限探索は分 枝限定法とほぼ同じ構造だが，入力は問題 P と探索 幅に対する制限値 w の二つとなっている．探索では作 成した部分問題のうち高々w + 1 個のみ探索し（11 行 目），再帰呼び出しで部分問題 Pi を探索する際は探索 幅を i だけ狭める（12 行目）．このため，分枝が進む につれ探索する幅はより制限されていく． 幅制限探索は多くの問題に用いることができる．分 枝限定法による厳密解法が提案されている場合はそれ を幅制限探索に書き換えることは容易である．厳密解 法が提案されていないような問題でも，何らかの貪欲算 法をもとに分枝処理を作れば幅制限探索を実装できる． 図 1 の探索木を用いて探索の様子を説明する．各節 点は部分問題を表している．根は与えられた問題に対 応し，葉は分枝せずに解ける部分問題に対応する．各節 点の子は，左から順に P0, P1, P2 と並んでいるものと する．各節点内には数字が書かれているが，w がその 節点内の数以上のときだけその節点は訪問される．例 えば，w = 0 の場合は左下の 0 と書かれた葉を訪問し， 解をただ一つだけ生成し終了する．つまり，実質的に 貪欲算法と同じ動作をする．w = 2 の場合は根の左の 部分木の全ての子を訪問し，真ん中の部分木の左の子 と真ん中の子の計二つを訪問し，右の部分木の左の 2 と書かれた子一つを訪問する．また，w が十分大きな 値の場合，探索幅の制限がないのと同じになり，深さ 優先の分枝限定法と全く同じ動作をする． Algorithm 2 幅制限探索INPUT: Problem P , search width w OUTPUT: Optimum solution x∗
1: procedure Width Restricted Search(P, w) 2: if P has no feasible solution then return
3: else if P is easily solvable then
4: Find the optimum solution x of P 5: if f (x∗) < f (x) then x∗← x 6: end if
7: return
8: else if U B(P )≤ f(x∗) then return 9: end if
10: Create subproblems P0, P1, . . . , Pk from P 11: for i from 0 to min(k, w) do
12: Width Restricted Search(Pi, w− i) 13: end for 14: end procedure A A A A A A A A A A A A A A A A A A H H H H H H H H H 0 0 1 2 0 1 2 1 2 3 2 3 4 図 1: 探索木
幅制限探索は部分問題の作成法が適切であれば比較 的高い確率で最適解を求めることを以下で説明する．解 析を容易にするため，探索木は高さ h の完全二分木で あり，探索木中には最適解はただ一つ存在するものと する．また，上界テストによる枝刈りは一切行わない ものとする． 幅制限探索では葉のうち根から右側の枝を高々 w 回 だけ通って到達できるもののみを訪問する．部分問題を 作成する際に左の部分木にその部分問題の最適解が含 まれる確率がある一定の値 p であるとき，根から最適 解に対応する葉までの道上に右側の枝が含まれる本数 は二項分布 B(h, 1− p) に従う．よって，w = h(1 − p) のとき最適解が求まる確率（以降，成功確率と呼ぶ）は ほぼ 50%となり，w を大きくすれば成功確率は高くな る．例えば，h = 1000，p = 0.9 のとき w = 110 とし て幅制限探索を実行すれば，二項分布表などから成功 確率は約 0.865 であることが分かる． 上記の探索木において葉のうち根からの道中に右側 の枝をちょうど i 個含むものの数はhCi個である．つ まり，幅制限探索において訪問する葉の数は w ∑ i=0 hCi (1) である．式 (1) より，例えば h = 1000，w = 110 のと き訪問される葉の数は約 1.419× 10149 と計算できる． ここで，深さ優先探索において同程度の数の葉を訪問 した時点の成功確率を調べる．深さ 504 の節点を根と する部分木の葉の数は 21000−504≈ 2.046 × 10149 であ るが，その最も左の部分木に対応する部分問題に最適 解が含まれる確率は p504≈ 8.67 × 10−24 である．幅制 限探索の成功確率 0.865 はこの値と比べ極めて大きい ことが分かる． 上記の例では p を 0.9 という大きな値にして解析を 行ったが，p の値は 0.5 に近づくにつれ深さ優先探索 に対する幅制限探索の有利さは小さくなる．分枝処理 において最適解ができるだけ最初に訪れる部分問題に 含まれるようにすることは分枝限定法の設計における 基本であるが，幅制限探索では特に重要である． 実行可能解のうち評価値が上位 a 個までを上位 a 解 と呼ぶことにする．また，上位 a 解に対する成功確率を paと記す．paを計算するのは容易ではないが，上位 a 解が左の部分木に含まれる事象が他の上位 a 解の存在と 独立であるという仮定をおけば pa= 1−(1−p1)aとし て容易に求まる．例えば，h = 1000，p = 0.9，w = 80 のときは p1≈ 0.0176 なので，a = 100 のときは上記 の式より p100≈ 0.831 となる．なお，深さ優先探索の 分枝限定法において w = 80 での幅制限探索とほぼ同 数の葉を訪問した時点で上位 a 解を一つ以上訪問する 確率は 10−21 以下である．
3
拡幅探索
幅制限探索を用いる場合は制限幅 w の値を定める必 要があるが，事前に適切な値を求めるのは困難である． その問題点に対する解決法として拡幅探索を提案する． 拡幅探索はまず w = 0 で幅制限探索を実行し，次に w = 1 で幅制限探索を実行し，以降，w = 2, 3, . . . と少 しずつ制限幅を大きくしながら実行していくことで良 い解を早い見つけようというものである．拡幅探索を Algorithm 3 に示す．拡幅探索では w の上限値 wmax を定める必要があるが，ある程度大きな値に定めれば 解の最適性が保証される．例えば，探索木の高さを h， 分枝操作において作成する部分問題の最大数を d とし たとき，wmax= h(d− 1) とすれば必ず最適解が得ら れる．ただし，wmax が大きいと停止するまでに時間 がかかるので，最適解を逃さない範囲で wmax をでき るだけ小さな値に定めた方が良い． Algorithm 3 拡幅探索INPUT: Problem P , maximum width wmax
OUTPUT: Optimum solution x∗
1: procedure Widening Search(P, wmax) 2: x∗← (a feasible solution)
3: for w from 0 to wmaxdo
4: Width Restricted Search(P , w) 5: end for 6: end procedure 拡幅探索では w の値を変えながら幅制限探索を何度 も実行するので，多くの無駄な処理を行っているように 見える．実際は，幅制限探索において訪問される探索木 の葉の数は w が 1 増える度に急激に増加するので，同 じ節点を何度も訪問することによる手間の増加は全体の 手間に比べさほど大きくない．例えば h = 1000 のとき， w = 110 の幅制限探索と wmax= 110 の拡幅探索が訪 問する葉の数はそれぞれ 1.419× 10149，1.618× 10149 であり，1.14 倍程度で済む． 上記の解析においては上界テストによる枝刈りを全 く考慮していないが，枝刈りが行われる場合は拡幅探 索の無駄はより少なくなる．なぜなら，ある部分木を 2 回訪問する場合，2 回目の探索のときは初めての探索 のときよりも良い暫定解を持っており，2 回目の方が枝 刈りが早い段階で行われるからである．
4
計算機実験
拡幅探索の評価のため計算機実験を行った．実験で は以下に示す最大重みクリーク問題を用いた．• 入力：無向グラフ G = (V, E)，各頂点の重み（自 然数） • 出力：グラフ G のクリーク（任意の 2 頂点間に辺 が存在するような頂点誘導部分グラフ）の中で， 頂点の重みの和（＝評価値）が最大のもの． 著者らは上記の問題に対する深さ優先の分枝限定法 のアルゴリズムを文献 [5] にて提案している．このア ルゴリズムを従来法と呼ぶ．それを拡幅探索に書き換 えたものを提案法とし，二つの手法を比較する．なお， 提案法において，wmax はグラフの頂点数とし，部分 問題の順序付けは文献 [5] の方法に従った． 入力のグラフの頂点数と辺数をそれぞれ n, m と記 す．実験では頂点数は 1000, 2000, 5000, 10000 の 4 通 り，辺密度（d = 2m n(n−1)）は 0.3，0.5，0.7 の 3 通りの 計 12 通りの組合せについて乱数を用いてグラフを 10 個ずつ作成した．各頂点の重みは 1 から 10 までの整 数値を等確率で割り当てた．計算時間を 180 秒とし， 分枝数に対する暫定解の頂点の重みの和の平均値の変 化をグラフに示す．実験に使用した計算機の CPU は Intel Core i7-2600 (3.4GHz)，メモリは 4GB，プログ ラミング言語は Java (JDK 1.7) である． 以下に現れる図中，横軸は計算時間 [秒]，縦軸は評価 値，WS は提案法，DFS は従来法を表す．頂点数 1000 の場合については，辺密度 0.3 と 0.5 に対し従来法，提 案法とも最適解を出力した．辺密度 0.3 の場合は 1 秒 以内に最適解が求まっており手法による差異はほとん ど見られなかったが，辺密度 0.5 の場合，提案法は従 来法に比べ短時間に解の改善が行われた（図 2）．辺密 度 0.7 の場合は最適解が得られたか確認できなかった が，提案法の暫定解の評価値は従来法を常に上回って おり，180 秒の実験時間内には提案法と従来法の差は ほとんど縮まらなかった（図 3）． 90 95 100 105 110 115 120 0 20 40 60 80 100 120 140 160 180 WS DFS 図 2: 実験結果（n = 1000, d = 0.5） 頂点数 2000 の場合については，最適解が出力され たのは辺密度 0.3 のときのみであり，辺密度 0.5 の場 145 150 155 160 165 170 175 180 185 190 195 0 20 40 60 80 100 120 140 160 180 WS DFS 図 3: 実験結果（n = 1000, d = 0.7） 合については提案法の平均値が従来法を常に上回った （図 4）．辺密度が 0.7 の場合，頂点数 5000 の場合もほ ぼ同様であった． 50 60 70 80 90 100 110 120 130 140 0 20 40 60 80 100 120 140 160 180 WS DFS 図 4: 実験結果（n = 2000, d = 0.5） 頂点数 10000 の場合は，従来法は短時間の間に暫定 解の更新が進んだが，それ以降は解の改善はほとんど 行われなかった．提案法は，最初，解の改善が従来法 より若干遅れたが，その後も解の改良が行われ，従来 法よりも良い解を得た後は従来法と提案法の差が少し ずつ広がっていった．その傾向が顕著に表れた頂点数 10000，辺密度 0.7 の結果を図 5 に示す． 以上の実験結果より，小さな問題に対しては提案法 が従来法よりも早く良い解に達し，大きな問題に対し ては提案法では従来法よりも良い解を得られることを 確認した．
5
むすび
本稿では分枝限定法における新たな探索手法である 幅制限探索を提案し，さらにパラメータ設定が容易な120 140 160 180 200 220 240 260 280 0 20 40 60 80 100 120 140 160 180 WS DFS 図 5: 実験結果（n = 10000, d = 0.7） 拡幅探索を提案した．拡幅探索は深さ優先探索の分枝 限定法に軽微な変更により実現できるので，実装は容 易である．幅制限探索と拡幅探索について，いくつか の仮定の下で計算の性能を評価した．また，計算機実 験により，従来法よりも短時間で暫定解の評価値が良 くなることを確認した． 本稿では最大重みクリーク問題対し拡幅探索を用い 有効性を検証したが，拡幅探索は様々な問題に対して 適用可能な，近似解を求めるための一般的な枠組みで あると考えられる．よって，様々な問題に対して拡幅 探索と通常のメタ戦略による解法を実装し比較するこ とが今後の課題として挙げられる．分枝限定法の中に は分枝順序を固定することで効率化を図っているもの があるが（例えば [4]），このような手法に対する提案 法の適用も今後の課題として考えられる．また，幅制 限探索では部分木の探索時に制限する幅を部分問題の 順位によって定めたが，より詳細な制限量を定めれば より高速に良い解に到達する可能性がある．この点に ついても検討の余地がある．
参考文献
[1] Toshihide Ibaraki: Theoretical comparisons of search strategies in branch-and-bound algorithms, International Journal of Computer & Information Sciences, Vol. 5, No. 4, pp. 315–344 (1976) [2] 今堀慎治，柳浦睦憲: 概説メタ戦略，オペレーション
ズリサーチ：経営の科学，Vol. 58, No. 12, pp. 695– 702 (2013)
[3] 久保幹雄，J. P. ペドロソ: メタヒューリスティク スの数理，共立出版 (2009)
[4] Satoshi Shimizu, Kazuaki Yamaguchi, Toshiki Saitoh and Sumio Masuda: Optimal table method
for finding the maximum weight clique, Pro-ceedings of the 13th International Conference on Applied Computer Science (ACS’13), pp. 84–90 (2013)
[5] Kazuaki Yamaguchi and Sumio Masuda: A new exact algorithm for the maximum weight clique problem, Proc. of 23rd International Conference on Circuits/Systems, Computers and Communic-tions (ITC-CSCC 2008), pp. 317–320 (2008)
