要約援護援護学生論文賞受賞論文

枝被覆問題を用いたスタイナー問題の下界値
矢部憲一

東京工業大学大学院総合理工学研究科システム科学専攻;現所属:東京ガス紛(指導教官小島政和教授)

1.

blem ，以下 TSP と略)に対しては緩和問題として割当はじめに問題を用いるとかなり強力な下界値が得られることがわ

スタイナー問題 (Steiner Problemin Graphs ，以下

かっている[ 1J.

しかし，SPG に対しては巡回セール

SPG と略)は校に非負費用が与えられたグラフ上で与スマン問題に対する割当問題ほど効率よく下界値を求めえられた点集合 (Z 一点集合)がすべて連結であるようなる緩和問題はこれまでに発見されていない.また，割当部分グラフのうち，費用が最小となるものを求めること問題を用いて求めた TSP の下界値はグラブ縮約やラグを目的とする問題で，ランジュ緩和問題を利用して値をさらに強化できること

NP 完全族に属する非常に難しい問題である. NP 完全族に属する問題の正確な解を求めがこれまでに研究されている [I ， 3J.

るためにしばしば用いられる手段として分校限定法があ

本論文では TSP に対するこれらの手法を SPG の下る.分校限定法を効率よく適用するためには最適解のよ界値に対して応用し，下界値を強化する手法について研L 、下界値を L 、かに効率よく求めるかが重要である.

究している.

本論文では SPG の下界値を求めるための新しい手段

3. 枝被覆問題を利用した下界値として枝被覆問題を利用する方法を提案する.さらに，
枝被覆問題を解くさいに求められる各校の被約費用を利

枝被覆問題はグラフ上の校部分集合のうち，各点に対用してグラブの縮約を行なうことによって，得られた下して少なくとも l 本はその部分集合内の枝が接続してい界値をさらに強化する下界値強化法を提案した.そしてるものの中で費用の総和が最小となるものを求める問題

これらを組み合わせた下界値強化アルゴリズムを開発である.

し，下界値を求める既存の方法と計算機実験によって比較し，本論文で提案した方法の有効性を確認した.

2.

スタイナー問題について

枝被覆問題に対しては Murty 他 [4J が蓄アルゴリズムを応用した効率のよい解法を発表している.
SPG を解くために与えられたグラフ G において，Zｭ点集合以外のすべての点と特殊な人工点とを費用が 0 の

SPG はネットワーク通信計画や輸送問題，施設配置

枝で結ぶことによって変形されたグラフを G' とすると，問題などを取り扱うさいに非常に重要な役割を果たす問

G'上で枝被覆問題を解くことによって得られた最適解は題である.

G 上での SPG の最適値の下界値となっている.

SPG は特殊な場合として，よく知られた全張木問題や最短路問題を含んでいる.これらの問題に対4. 下界値の強化しては入カサイズの多項式オーダーの計算量で解けるよ
うな非常に効率のよい解法が数多く発表されているが，本論文では，分校限定法を効率よく適用するために，一般の SPG は NP 完全族に属する非常に難しい問題で枝被覆問題を利用して得られた下界値をさらに改良するあり，正確な解を効率よく求めるアルゴリズムは発見さ下界値強化アルゴリズムの開発も行なった.このアルコれていない.

リズムは TSP に対する割当問題によって得られた下界SPG に対して分枝限定法を適用する解法はこれまで値に対して Christofides が行なった，ラグランジュ緩

Beasley [3 J らによって研究が進め和法を利用した下界値強化法 [I ， 3J と類似のものであに Shore 他 [5J ，られてきた.

る.

巡回セールスマン問題 (Traveling S
alesman Proー46

枝被覆問題を利用して下界値を求めたさいに，枝被覆© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リ+ーチ

問題を解くMurty のアルゴリズムでは最適の他に各校枝被覆問題を利用する方法を提案した.また，得られたに対する被約費用 (Reduced Cost) が得られる.この下界値をグラフ縮約を利用して強化する下界値強化法と時，人工問題を解くために変形したグラフから人工校を組み合せ，取り除くと，被約費用が 0 であるような枝によってグラを提案した.そして計算実験の結果，本論文で提案した

フはいくつかの連結成分に分かれる.このように分けらアルコリズムが SPG に対するかなりよい下界値を求めれた各連結成分を新しく 1 点とみなし，グラフの縮約をることができることがわかった.

SPG の下界値を求める新しいアルゴリズム

行なかそのさい，新しく l 点となる元の点の集合の中

参考文献にひとつでも Z 一点集合に含まれる点があれば新しくまとめられた点は新しい Z 一点集合に含まれる点とする.

[1J E.Balasand N.Christofides. A restricted

また，各校の費用は枝被覆問題を解いた後のそれぞれのLagrangean approacht
o thetravelingsalesｭ

被約費用に置き換え，各連結成分間土を結ぶ校の費用はman problem. M athematical Programming ,もとのグラフでそれぞれの連結成分内の点同士を結ぶ枝の被約費用のうち，最小のものの費用とする.
そして，縮約されたグラフ上において再び人工問題を作り，枝被覆問題を解く.そのさいに得られた最適値を初めに得られた下界値に加えてももとのグラフに対するSPG の最適値の下界値となっている.

Vo 1. 21 , pp.19-46 , 1981.
[2J J.E. Beasley , An algorithm for Steiner
problemi
ngraphs. Networks , Vol.14, pp.147
984.
-159 , 1[3J N.Christofides. Bounds forthetravellingｭ.
salesman problem. OperationsResearch , Vol

この縮約一枝被覆問題と L 、う手続きを Z 一点、が I 点と20 , pp.1044-1055 , 1
972.

なるまで繰り返し行ない，そのつど枝被覆問題の最適値[4J K. G. Murtyand C. Perin , A I‑matching

として得られた値を下界値に加えてゆく.論文中ではこblossom‑type algorithm for edge coveringのようにして得られた値も SPG に対する下界値となることを示した.

5.

982.
problems. Networks , Vo l. l2 , pp.379-391 , 1[5J M. L. Shore , L. R. Foulds , and P.B. Giｭbbons , Analgorithm forthe Steiner problem

計算実験.12 , pp.323-3~3 ， 1
982.
ingraphs , Networks , Vol

本論文で提案した枝被覆緩和法に下界値強化法を加えたアルゴリズムの有効性を調べるために，SPG 下界値を求める既存の 2 つの方法，すなわち， Shore 他 [5J の間[6J H. Takahashi and A. Matsuyama. AnapproximatesolutionfortheSteinerproblem.
Math. Japonica , Vo1.6. pp.573-577 , 1
980.

Beasley[2J のラグランジュ緩和法との比較[7J P. Winter. Steiner problem in networks:

実験を行なった.実験の点、の数に対する枝の数の比率を

A survey. Networks , Vo l. l7 , pp.129-167 , 1987.

接列挙法，変え，乱数によってグラフを作成してそれぞれのアルゴリズムによって下界値を求めた.その結果，計算時間の面では Shore 他の方法にかなわないものの，値の面では本論文のアルゴリズムは他のアルゴリズムに比べてよい結果が得られた.この傾向は特に点の数に比べて枝の数が少ないようなグラフ，すなわち疎なグラフにおいて顕著であった.たとえば点の数が 100 ，枝の数が 495 のグ

会員言ト報

ラフに対して発見的解法 [6J による近似解の値に対する下界値の比率を比較すると，

10 問解いた平均値が Shore

他の間接列挙法では 53.6% であるのに対し本論文のアルゴリズムでは 73.3% というよい値を得ることができた.

6.

川野幸三郎氏(元学会庶務理事，監事
現 OR 誌編集委員，評議員)
平成 2 年 12 月 9 日心不全のため逝去されました.

まとめ

1j1'年 61 才，議んでご冥福をお祈りします.

本論文では SPG の下界値を求める新しい方法として1991 年 1 月号

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

47