とのコラムは， OR にかかわる概念，知織(手法，原理)，それらの図解，よい教材や問題，実学

C ~I.，...~~

OR の実施経験，そとから得られた知恵やアドパイス，失敗談と教訓，新しい視点，視座，フレー
ムワーク，未だ解けていない問題，面白い研究テーマなどを，“新鮮に~しかも“コ γ パクトjC"表現し，提示していただくものです.ユニークなアイディア，フレッジュな見方，発想，だれかとメモランダム

意見をたたかわせたい問題提起など，ふるってど投稿ください. (原稿は，刷り上がり，半ページから 3 ページ IC納まるようにお書きください.簡単 IC/

加筆訂正をお願いする場合があります〉

最大クリーク問題の近似解法に関するコメント
久保幹雄
近似解すら，A/' ，9-完全である難し

設費電j停閉 jtMt

い問題において，本稿のような大きな対象についても，多項式時間で驚くべき高い近似精度の達成を確認することができた.

猪瀬，山田，富田，高橋 [IJ1.

はじめに

平成 5 年 9 月 6 日の読売新聞の 1 面トップで「コンピュータの難問解明，集団内の最大派閥，超高速で選別 jとし、う記事が載っていた.ここで言う最大派閥問題とは，組合せ最適化およびグラフ理論における標準的な問題の1 つである最大クリーク問題Problem) のことである.

(Maximum Clique

筆者は，この記事および，その発端になった研究発表論文 [IJ を読んだ後，最適化問題に関与している研究者の 1 人として少なくとも OR

記事のもとになった研究発表 [IJ に「近似解すら J・ダ・学会員の方々には，正しい情報を流す義務があると感じ完全である難しい問題J としづ記述がある.この言葉のた.以下では，最大クリーク問題の現状と，この記事で真意を説明しよう.

紹介されている内容の問題点を示す.

最大 3 充足問題 (MAX3・ SAT)2.

定義と計算量ないことを証明した.この結果を用いることによって，は，すべての点の聞に枝があるグラフである.無向グラ(V , E) (V は点集合の e. 近似解を求める多項式時間のアルゴリズムは，ダ守と Jタの下では存在しまず，用語と問題の定義を説明しよう.完全グラフとフ G=1992年に Arora etal
. [2 ， 3J は，E は校集合を表わす)が与えられたとき，点の部分集合 C(çV) は，C によって導かれたグラフが完全なときクリークと呼ばれる.最大クリーク問題とは，クリークサイズ ICI で最大になるクリークを求める問題である.もちろん，この問題は，A/'タ・困難である [6J.

任意の ε(>0)

に対して，最大クリーク問題の最適値のI
Vle 分の 1 以上の近似値を算出する多項式時間のアルゴリズムがタキ，A/' ，9の仮定のでは存在しないことが示される.

3.

現状

最大クリーク問題に対する現状を知るための最もよい情報源は DIMACS である.

DIMACS とは DIscrete

MAthematicsandt
heoretical ComputerScience
くぼみきお東京商船大学流通情報工学の略称であり干 135 江東区越中島 2-1-6

University , A T& T Bel
1Laboratories , Bel1coree‑mail: kubo@ship2. ipc.tosho・ u.ac.jp

を母体とした研究センターである.毎年テーマを決めて，650 (38)

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

University , Princeton

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

そのテーマに対して世界中の研究者たちが協力して集中的に研究を行なっている.

表 1

1993年度のテーマは，最大クリーク問題，グラフ彩色問題，充足可能性問題の 3 つであり，ベンチマーク問題の収集，アルゴリズム開発および性能テスト，サーベイ論文の整備，理論的な結果の発表など，テーマ別に精力的に研究が行なわれている.最大クリーク問題に関する成果は無記名 ftp サイト

dima­cs. rutgers.edu の pub/challenge/graph に集められており，誰でも自由に得ることができる(以下では，directory 名のみを記すことにする).

文献 [IJ の実験で得られた値と確率推定値

pI0.250.50

0.750.90

Clique Size I 71325527132655

確率的推定値

不完全であるというのが，研究者の聞のコンセンサスである.

DIMACS では，最大クリーク問題の応用から生まれた，いろいろなタイプの構造をもったグラフを/
benchmarks で配布している.

例としては，符号理論から生まれた Hamming グラフや Johnson グラフ，幾最大クリーク問題に対する最適解法をいくつか紹介し何学の未解決問題を解くために生まれた Keller グラフ，よう.簡単な陰的列挙法が Carraghan と Pardalos に信頼性への応用から生まれた C.Fat Ring グラフなどがよって作られている[幻.彼らの解法はグラブが疎なときある.開発したアルゴリズムの頑強性を確認するためにn=3000 までの実際問題を解くことには，これらのグラフに対する数値実験も必要不可欠であFORTRANる.また，実験用として大きなクリークを隠したランダは効率的であり ，成功している.

彼らの論文の付録には，で書かれたプログラムがついている.このプログラムは/contributed/pardalos から得られる.

ここには，Pardalos のグループによる凹関数の最適化による下界ムグラフの作成法もいくつか提案されている.

4. 実験結果の分析を組み込んだ分校限定法 [7J のプログラムと最新のサー

読売新聞に掲載されていたアルゴリズムは近似解法でベイもある.また， Applegate と Johnson による C 明ある.実験ではすべてランダムグラフに対して行なわれ言語で記述された効率的な最適化手法と近似解法のプロているが，従来の近似解法との比較ではなく，最適化手グラムも /solvers から得ることができる.

法と計算時間の比較を行なっている.当然のことである

最大クリーク問題に対する数値実験は，通常ランダムグラフを用いて行われる.ここで，ランダムグラフ Gn ， pが，近似解法の評価をするときに，最適解法に比べて速いことだけで満足してはいけない.とは，点の数 n(= jV l). 定数 o~p ζ1 を与えたとき，近似解の性能は最適値からどの程度離れているかによ

すべての 2 点聞に独立に確率 p で枝を引くことによってって評価できる.しかし，問題の規模が大きくなると最構成されるグラフである.ランダムグラフ Gn ， p に含ま適解を求めるのが困難になるので，最適値の代わりとしれる+イズ k(=ICI) のクリークの数の期待値はて上述の確率的推定値を用いるのが普通である.しかし，

k点[IJ の実験では，

h 点のランダムグラフがクリークになる確率が p/C(/C-1l /2

ゴリズムを異なる乱数系列で 100 回試行し，状況的な証拠であることからから求めた推定値をもととして j 最適値を推測する方法

E-­唱)
(

部分集合の数が n 個から h 個を選ぶ組合せの数であり，旬 C/c pk( /C-1l /2r厳密解が求まっていないので，本アルを用いている.このような方法によって最適解の保証をGn ， p に対する最大得ることは難しいことが予想される.おそらく [IJ の実験のクリークサイズの推定値(確率的推定値)は (1)が l 以で、最適値と推定した債は，本来の最適値とは異なるもの上になる最大の h の値となる [4J. たとえば，後で比較にであることが推測される.以下に詳しい理由をあげよう.

用いる n =4000 ， ρ=0.75 のランダムグラフでは ， k=24 ,まず，上述した確率的推定値との差を見てみる.文献となることがわかる.

したがって ，25 ， 26 ， 27 のときのクリークの数の期待値を式 (1) によって[IJ に記載されていた n =400 のランダムグラフに対する計算すると，それぞれ7377.9 ， 11 1. 3 ，1. 21 ， 0.01 個である.

実験結果を表 1 にあげる .

p=0.25 , 0.50 のときは確率

したがって，サイズが 24や 25 のクリークは簡単に見つか的推定値と同じ値を算出してはいるが ，るが，サイズが 26になると探すのは容易ではなくなり，は推定値より 1 だけ，サイズが 27 になると非常に高い確率で存在しなくなる.

か算出していない

p=0.75 の場合

ρ=0.90の場合は 3 も小さい値しn が小さく p が 0.5 から離れた場合

最近では，最大クリーク問題に対するアルゴリズムのには，ランダムグラフ内のクリーグ+イズの推定値は正評価を行なうには，ランダムグラフによる実験だけでは確ではないが，彼らの言うところの「実験を 100 回行な

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

(39)851表 2Applegate と Johnson の近似解法を 1000 回試行したときの近似値とその頻度

n =400 ，ρ=0.8 ，確率的推定値は 31

表 4

比較実験:
単位は秒，n=400, p=0.75 のランダムグラフ，()内の数値は得られたクリークのサイズTabuSearch

文献 [IJCliqueSize

I24 25 26 27 28 29 30

頻度

I3 76 338 399 168 14 280 (25)0.28 (25) ,46.3 (26)が，計算時間と得られた解の値の向者が記述されている
表 3Applegate と Johnson の近似解法を 1000 回試行
n =8000,P=0.5,Fコ〆

16

1718O

718

246

10

したときの近似値とその頻度
確率的推定値は 20のは ，n=400,p=0.75 の場合だけである.したがって，この問題に対してのみ比較を行なう.結果を表 4 に'AQUeZ‑‑ー内4E度
山頻q;

Cあげる.

明らかに

Tabu Search の方が高速に解を算出していることがわかる.

クリークサイズ 25 を探索する

までの計算時間は 200 分 l の以下であり，さらに， Tabu

Search は確率的推定値であるクリーグサイズ26 を出すったときの状況的な証拠」よりは，根拠のある数値であると考えられる.
文献 [IJ のアルゴリズムは手元にないので，どの程度の証拠が実験から生まれてくるかは筆者にはわからない.
以下では， Applegate と Johnson の行なった類似の実験結果を利用して「状況的証拠 J の妥当性について考えてみよう.

TabuSearch のインプリメンテーションは容易でありデータ入力の部分を除けば，わずか 100 行程度のコードで記述できる.
他のランダムグラフに対する結果を表 5 に，構造をもった問題に対する結果を表 B にあげる.表 6 の問題は，Applegate と Johnson は，彼らが作成したランダム化を用いた近似解法 (dmclique) を 1000 回試行したときの度数分布を n =100 から 8000 のランダムグラフに対して調べている(結果のすべては /solvers/results. dmcにある).一例として [IJ で解かれた最大規模の問題の近い n=100 ，ことにも成功している.アルゴリズム実現の容易さも比較の対象になるので簡単に触れる.上の実験で用いたp=0.8 の度数分布表をあげる(表 2).

1000回の実験による状況証拠から判断すると，最大のクリーグサイズは 30 であることが予想されるが，残念ながら確率的推定値は別である.このような現象は，問題のサイズが大きくなると顕著になる.たとえば ，n=8000, p=0.5 の問題の場合(表 3 )では，確率的推定値が 20 であるにもかかわらず，1000回の試行で得られた最良値は 18すべて /benchmar ks から得ることができる.もし今後，最大クリーク問題に対する近似解法を作成して比較を行なうときには，この値を目安にして評価することが望ましい.計算に用いたアルゴリズムおよび実験の詳しい内容(パラメータ設定，他のグラフに対する実験結果等)に関する論文は，筆者に連絡をとることによって得ることができる.また，実験に用いたプログラムも研究用としてなら喜んで提供する.

5.

おわりに上で・述べたことから考えると，読売新聞に掲載されていた近似解法は，現在までtこ開発されてきた解法と比べである.このように，近似解法を 1000 回実行したときのて優れているとはし、えず，また数値実験も不完全である

最良値より最適債(または確率的推定値)が大きくなると考えられる.組合せ最適化に限らず，OR に関連する現象が，かなりの頻度で発生することが Applegate とことがマスコミに掲載されることは，喜ばしいことではJohnson の結果を観察することによっていえる.すなわ

あるが，正しい情報を流すように注意を与えることが，ち，近似解法を何度も試行したときの「状況証拠j は，学会としての義務であると考えられる.

アルゴリズムのよさの証拠にはならないのである.

以下では，筆者が作成した Tabu Search を用いた近参芳文献

似解法と比較を行なう.この近似解法は，現在世界中で[1J 猪瀬，山田，富田，高橋，近似最大クリークを抽最良のものというわけではないが，よい解を短時間で算出する確率アルゴリズムの実験的評価.電子情報通信

出するアルゴリズムの 1 つである.実験は [IJ と同じ

SPARCstation2 で行ない言語は C である.

[IJ では，実験はすべてランダムグラフに対して行なわれている

652 (40)

学会秋季大会予稿集，6-3 , 1993.

[2J S.AroraandS.Safra , P
robabilisticcheckｭ
ingo
fp
roofs;anewc
haracterizationofNP.

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

オベレーションズ・リサーチ

表 5

ランダムグラフ G伽 p に対する実験(の一部):計算
時間 (CPUの欄)は SP ARCstation2 の CPUc・.fat200-1

5.25
0.28
47.01

c-f:叫 200・2c・.fat200-5c‑
fat
500‑
1c‑
fat
500‑
10c-f:酷 500- 2c-f:酷 500-5

3.6
4.43

johnson16‑
2‑
4johnson
32‑
2‑
42.97

johnson8- 2・4
johnson8-4・4

62.5
3.13

a阻400.o .9.1 .clq

exact algorithm for the maximum

Ancliqueproblem ，。声erations R
esearchLetters , 9: 375‑

382 , 1990.
[6] M. R. Garey and D.S.Johnson , Com uters

andIntractability: A Guide tothe Theory ofp.hat500・3.c1q
pム酷 700- 1.c1q

Com uters and Operations

p.hat1 00ι1.cIq
p.h at1000.・ 2.cIq

pム酷 1000-3.cIq

p.h叫 1500-1.cIq
p.h回 150仏 2.clq

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

836
50唱

p.h at1500ド 3. cIq

82136

咽
Oq4nυn'oonuaaza。oau'Aq4au'An40

p.
hat
700‑
3.
clq
A

branch and bound algorithmforthemaximum

Research , 19: 363-375, 1992.

p.h a七 300- 1. clq

p.
hat
300‑
2.c1qp.
hat
300‑
3.
clqp.
hat
500‑1.clqp.
hat
500‑2.c1qpムat700・2.c1q

NP-Completeness , Freeman , 1979.
[7] P. M. Pardalos and G. P. Rodgers ,e 田 r400.0.7.cI q

・[5] R. Carraghan and P. M. Pardalos ,

噌司 A9

sanr
200.
0.
9.
clq
S回r400.0.5.cIq

100'Aas回r200.o.'1.clq。。 qaqdw'aRandom Graphs , AcademicPress , 1985.

1993 年 12 月号

8an
400.
0.
7.
.
2.
clq
同n400.o. 7.
3.
clq

値Z'onυnu
舟4wdauA 幽z'Aa
せ qd 内，eBollobas ,S 回400.0.7.1. clq

且Computer Society , Los Angeles , CA , 1992.

B 回 200.o .9 .3 .clq

san400.
o.5.1.clq

Aqo'tion
sofComputerScience , pages 14-23, IEEE

S町1200 .o .7..2 .clq

8an
200.
0.
9.
1.
clq.
o.
9.
.
2.
clq
8an200噌

tractability of approximation problems. In

Proceedings33rdIEEESymposiumonFoundaｭ

h田沼田ing8-4

san
l
000.
clq
S町1200.0 .7J..
clq

4

1
28'Aand M. Szegedy. Proof verification and inｭ

h田nming6-4

h回1ming8-2

au 定。 nueonunua[3] S. Arora , C.Lund , R. Motwani , M.Sudan ,clique problem ,Bench‑

は最適値まCliqueSize
122
4
58
1
4
12
626
64
8
164
14
1
12743

1992.

h町nming6-2

500
500
500
120496
2
8
70
1
71776
3361
1024
1024
64
64
256
256
1000
200
200
200
200
200
400
400400400
400200200400
400
300
300
300
500500500700700
70010001000
1000
1500
1500
1500

15343235
8473
4459
46627
9139231915460
107880210185594
35225990
4619898
518656434176
1824
704
31616
20864
250500
13930
13930
17910
17910
179
1039900
55860
5586055860
71820
1
3868
178
6339984558
69
1093321928
33390
31569
62946
93800
60999121728
1830
10122253
24479937174628492356896084724402

13 , IEEE Computer Society , Los Angeles , CA ,h町nming10-4

5日oIEI‑

ほProceedings 33rd IEEE Symposium onFoundations of Com uter Science , pages 2 ‑[4] B ,Size

引h副刃 ming1 0- 2

InClique

95162.08keller4keller
5keller6

内4nd0.72

圏内4FileName

4.1

a--

0.1

-一0.5

ζU1500

戸
hノ0.5

f1000

t

whJRJ

0.75

コヲ

Fフ0.50.75《rフ0.25(DIMACS

たは Best Known Value に一致している.

m山開.
一∞ ma
せ0.75

得られたすべての解の"0.75，

必句必句必句0.5

tnJhFIq3RJro'sqJfhu7・戸、ノ〆 hvdTA
ワ -qL
C'sqLn4'i'A

ヨJ

0.25

tq4719Jror033q

何4AUAUAUnununUAUnununu
nunvnunununvnunvnunu

0.5
0.5

0.01

dta'l

0.5

CPU

《100Clique Size、，・

確率的推定値，1、ァ111122412211今ρ

応用から生まれたグラフmarks) に対する実験(の一部)，計算時間 (CPU の欄)は SP ARCstation2 の CPU time ，単位秒，time ，単位は秒n

表 B

CPU0.
010.
050.
150.
050.
520.
030.
230.
0
20.
0
30.
0
1
0.
0
1
0.
0
7
17.
2
7
2
1
13.
2
7.
3
70.
5
60.
0
3
0.
0
10.
4
3
0.
0
1
8
1
9.
1
85.
4
5
4.
7
2
0.
2
8
2.
4
7
1.5
3
50.
6
2
5
7.
1
50.
6
2
6.
5
2
17.
7
8
0.
1
2
1.5
8.
4
2
7.
5
0
3.
1
3
0.
1
2
0.
9
20.
4
3
1.0
3
8.
1
8
7.
0
70.
3
70.
8
2
12.
620.
6
2
1
7.
1
5
70.
0
2
6.
6
0
5.73

(41)653