• Ｉ．特定領域研究(B)「アルゴリズム工学」平成10年 度活動記録

• ＩＩ．シリーズ: 研究班の紹介 -その1-
  A01班「離散最適化アルゴリズム」の紹介

• ＩＩＩ．国際会議参加報告 -ISSAC'98 & SODA'99-

• ＩＶ． 研究集会等のスケジュール

• 研究者名簿

２． 全体の活動

全体的な活動としては, これまでに1回の全体会議を行っており, また, 今年度中に全体会議をもう1度と国際シンポジウムを共催する予定である. 第1回の全体会議では, 全ての研究代表者が, 現在の研究テーマと 本特定領域研究で計画している研究について講演を行った. 参加人数は60名程度であった. 第2回の全体会議では, 各班でこれまでに得られている暫定的な研究成果を 班ごとに総括して発表が行われる予定である. また, 「パラダイムとしてのアルゴリズム工学」と いう概念を明確にし, 今後2年間の研究の方向を定めることを目標に, パネルディスカッションを予定している. 国際シンポジウム「離散数学とその応用に関する日洪シンポジウム」 では, 3件の招待講演と, 39件の一般講演を予定している. これらの日程は以下の通りである.

全体会議

第1回: 平成10年10月19, 20日(京都)

第2回: 平成11年3月5, 6日(福岡)

国際シンポジウム共催

The 1st Japanese-Hungarian Symposium

on Discrete Mathematics and Its Applications

(第1回 離散数学とその応用に関する日洪シンポジウム)

平成11年3月17$\sim$19日(京都)

３． 電子情報通信学会の特集号

新しいパラダイムとしての「アルゴリズム工学」という我々の主張を 広め, また「アルゴリズム工学」の現状を説明するために, 電子情報通信 学会の英文論文誌に特集号を組むため, 以下の要領で企画が進行中である. 当領域研究に参加する研究代表者全員が著者としてそれぞれの専門分野における アルゴリズム工学の最近の知見をサーベイするとともに, 適切な著者がいない重要な分野については 外部からの招待論文を企画することで, すべてのアルゴリズム工学研究者にとって なくてはならない論文集とすることを目指している.

電子情報通信学会英文論文誌　平成12年3月号

ゲストエディタ: 茨木 俊秀, 山下 雅史

アソシエイトエディタ: 室田 一雄 , 渡辺 敏正, 加藤 直樹, 五十嵐 善英

体裁： 大特集 -- 本特集のみからなる号を発行する.

内容：アルゴリズム工学に関する様々な分野の招待サーベイ論文集.

予定：平成11年3月著者／題目決定, 7月脱稿, 9月査読終了, 12月最終稿

４． 平成１０年度Ａ０１班活動／成果報告

平成10年度において，A01班は全体会議の際に各々班会議も同時に開催し，ま た班独自に12月に研究会形式の研究会を開催した．本年度が研究初年度にあた ることに鑑み，班として「アルゴリズム工学」共同研究推進を可能となるよう な運営を行なっている．以下，個別の会についてまとめる．

４．１． 平成１０年度第１回班会議

日時：平成10年10月19日16:00-18:00

場所：京都大学数理解析研究所地下1階009号室

出席者：A01班研究代表者7名

内容：A01班の研究計画について討議した．「アルゴリズム工学」の活 動の1つの主眼であるアルゴリズムデータベース構築について，各班員 からデータベース構築への貢献について検討した．また，アルゴリズム データベースへの貢献に関する議論にそって，班全体で班員の研究分担 者や大学院生など研究協力者の間で共有するテーマで共同研究できる最 も有望なものとして，「TSP, スケジューリングに関するメタヒューリ スティック」，「劣モジュラ・行列など離散システム」の2点を決め， 次回班会議においてこのテーマに関して1テーマ当たり2件の講演を行なっ て，班としての研究を開始して推し進めることとした．

４．２． 平成１０年度第１回研究会

日時：平成10年12月12日(土) 10:00-16:40

場所：京都大学数理解析研究所１階115号講義室

出席者：29名

内容： 以下のプログラムでA班での共同研究を目指した研究会を開催し，有意義な討論 を行なった．

10:00 - 11:10 岩田　覚 (大阪大学 基礎工)

『行列束に対する組合せ論的緩和法』

11:30 - 12:40 野々部 宏司 (京都大学 数理工学)

『資源制約付きスケジューリング問題の定式化と近似解法』

14:00 - 15:10 久保 幹雄 (東京商船大学 流通情報工学)

『巡回セールスマン問題に対する Lin-Kernighan 近傍をを用いた

Guided Local Search --大規模問題に対する実装法を中心として--』

15:30 - 16:40 室田 一雄 (京都大学数理解析研究所)

『離散凸解析のアルゴリズム』

[1]岩田　覚 (大阪大学 基礎工) 『行列束に対する組合せ論的緩和法』

○論旨

代数微分方程式系(DAE)で記述される動的システムの解析において，行 列束(matrix pencil)の指数(index)と呼ばれる量が重要な役割を果たし ている． 本報告では，行列束の指数を計算するための室田による組合 せ緩和アルゴリズムを紹介し，その改良に関する最新の成果を報告する．

○感想

DAEは，F(dx/dt)+Hx=Ψ(t)の形をした微分方程式．また，行列束は， A(s)=sF+Hという多項式形の行列のことをさす． ふつう，微分方程式と いえば，dx/dt=f(x,t)という正規形にして解くのが一般的だが，問題に よってはDAEで解いた方が解きやすい場合も多い．そのさい，微分方程 式の解の形を決定づける要因として，A(s)の指数が重要になってくる． しかし，指数の計算法は組合せ的な要素が高いため，効率的なアルゴリ ズムをつくるのは難しい．
この方法では，行列の次数計算を二部グラフにおとし，さらに，許容ポ テンシャルという量を考え，元の問題の制限を緩めた緩和問題を作り， 行列の指数という代数的な量を，組合せ的な量に変換して解こうという わけである．
行列に関する一部知識で不明なところもあったが，緩和問題を考えてそ の中で最適化を行ない，元の問題の解として適当なら，それが元の問題 の最適解になる，という緩和法のアイデアは，最適化全体でもよく見ら れる方法である．この方法にこのような応用ができることに驚いた．何 より，微分方程式を解くという連続系の分野においても，組合せ論が重 要になってくるという点が興味深かった．

[2]野々部 宏司 (京都大学 数理工学) 『資源制約付きスケジューリン グ問題の定式化と近似解法』

○論旨

資源制約付きスケジューリング問題(RCSP)は，多くのスケジューリング 問題を定式化できるという汎用性の高さから最近改めて注目を集めてい る．しかし現実の応用分野では，スケジュールの評価基準が複雑かつ多 様であるなど，従来のRCSPの枠組では扱うことのできない問題も少なく ない．そこで本研究では，広範なスケジューリング問題に対応できるよ う，RCSPの定式化を拡張するとともに，タブー探索に基づく近似解法を 提案し，計算実験によりその有用性を確かめる．

○感想

RCSPでは，資源の制約を，再生可能資源r（機械，人，仕事など）と， 再生不可能資源s（コスト，原材料など）に分け，また，作業の処理モー ドと，先行制約（ある作業は別な作業より前に完了させる，など）て定 式化するが，この定式化の拡張では，rの供給量・消費量を自由に設定 でき，また，段取り替え作業や，処理モードや処理時間，開始・終了時 刻の制約も考慮可能にすることで，多様・複雑な目的関数に対応できる．
ただ，あまりに制約が大きくなると，局所探索法での効率的な探索が困 難になってくるので，とりあえず資源制約と先行制約のみを満たす解を 探索し，それ以外の制約の違反度の小さいものを選んでいく，という方 法をとっていく．講演では，いくつかの問題例をあげて説明していた． 残念ながら，自分の興味の深い具体的なタブー探索の方法までは詳しく 聞けなかった．
この方法の基本方針になっているのは，「特定の問題に特化した解法を 作るのではなく，定式化の拡張を使えるように問題をうまく定式化して， さまざまな問題に幅広く応用したい」という考え方である．実際の応用 で解きたい問題は，それこそ多様化しているわけだから，このアプロー チはとても興味深かった．個人的には，スケジューリング問題に関して は，もう少しじっくり勉強してみたいと思っている．

[3]久保 幹雄 (東京商船大学 流通情報工学) 『巡回セールスマン問題 に対するLin-Kernighan 近傍を用いた Guided Local Search --大規模 問題に対する実装法を中心として--』

○論旨

(主にユークリッド型の)巡回セールスマン問題に対する最も強力な近傍 のひとつに，1973年に Lin と Kernighanによって提案されたもの (Lin-Kernighan 近傍)がある．Lin-Kernighan 近傍は強力ではあるが， Tabu Search， Simulated Annealingなどのメタ解法をベースにして大 規模問題に対して実装を行おうとすると，幾つかの問題が発生する．こ こでは，Guided Local Searchをベースにしたメタ解法が， Lin-Kernighan 近傍のような複雑な近傍と比較的相性が良く，大規模問 題に対する強力なメタ解法になる可能性があることを紹介する．

○感想

今回参加を決めた動機の講演で，期待に違わず興味深い話だった．ノー トPCでPowerPointを走らせて講演していたのだが，途中で自作のTSPソ ルバーを立ちあげて，実際に問題の解法を実演していて，プレゼンテー ションとして素晴らしいできだと思った．
話の中で，点データの構造としてK-d木が出てくるのだが，実は，K-d木 に関しては，学部演習で実際にプログラムした経験があるため，話が理 解しやすかった．あっと言う間に2-optが終了するのを見て，K-d木が効 率的な探索にきわめて有効であることがよくわかった．
また，LK法を「3-opt」+「深さ優先のTabu Searchを，2-opt近傍で行なっ たもの」と解釈すると良い，との話には，目から鱗が落ちた思いだった． 確かに，そう考えると，LK法がすでにメタ解法的性格を帯びているとい うことになるわけであり，その他のメタ解法との組合せがうまくいかな いのも納得できる．
今回の話の主題であるGuided Local Searchは，LK法のような複雑な近 傍に対しても相性がよい解法である．基本的な考え方は，「局所最適解 に陥ったら，目的関数の形を変形させて再探索させる」という方法であ る．この方法を用いると，局所探索法として2-opt近傍を用いた場合で も，0.5%増し程度の解が得られる．しかし，ふつうに実装すると，n^2 のメモリが必要になるので，近傍制限が必要になる．
また，Guided Local Searchでは，各枝に対してペナルティ関数という ものを考えるのだが，この実現のためにはCandidate Graphを用いて， どの枝のペナルティ関数を増加させるか決める．
なお，今回の講演で使ったPowerPointのデータと，最新版のTSPソルバーはhttp://www.logopt.comにある．

[4]室田 一雄 (京都大学数理解析研究所) 『離散凸解析のアルゴリズム』

○論旨

マトロイド，劣モジュラ関数に関するアルゴリズムを概観した後，Ｍ凸関 数，Ｌ凸関数に関するアルゴリズムの最近の成果を紹介する．マトロイド の抽象論を知らない人にも分かるように，行列やネットワークの言葉に翻 訳して説明をする．

○感想

残念ながらマトロイドの基礎部分の学習がまだなので，正直言ってよく分 からなかったところが多かった．ただ，Ｍ凸関数は，局所的最適解がかな らず大域的最適解になるという特性があり，しかもそれが多項式時間で判 定できるという点は便利かなと思った．このような幅広い分野の理解も含 めて，これからの研究を進めたいと思う．

A01班平成10年度最終の班会議を全体会議の際に合わせて下記日程で予定している．

日時：平成11年3月5日(金) 12:00-13:30

場所：福岡ソフトリサーチパーク

参加人数：15名(予定)

５．平成１０年度Ａ０２班活動／成果報告

平成１０年度A02班の活動報告をお知らせいたします． A02班は６名の研究代表者（浅野孝夫（中央大学理工学部），戸田誠之助（日本大文学 理学部），周暁（東北大学情報科学研究科），永持仁（京都大学工学研究科），平田 富夫（名古屋大学工学研究科），渡辺敏正（広島大学工学部）） およびその研究分担者より構成されています．
主な研究対象は離散最適化問題の中でも特殊な構造をもち かつ基礎的であるグラフ・ネットワーク問題とSAT（充足可能性問題）であります. 平成１０年度はアルゴリズム工学の立場から以下のように研究集会を開催し, グルー プ内の研究者および他のグループとの情報交換を行ない，共通の目的意識を形成しま した.

第１回研究集会

日時：平成10年10月19日(月)，16:00 -- 17:45

場所：京都大学8号館413会議室

出席者：５名（浅野孝夫，周暁，永持仁，平田富夫，渡辺敏正）

内容：

１.同日，午前10時から12時に開かれた総括班会議の報告，特に，アル ゴリズム工学の研究目標，期待される研究成果について共通理解の必要 とされていることが強調された．

２.アルゴリズム工学の立場から実用に供するためのアルゴリズムのデー タベースに関して議論がなされた．

(i) 最大フロー問題等の基礎的なアルゴリズムも用意するか，
(ii) 既存のシステム，たとえば，LEDAなどを利用するか，
(iii) 教育用のプログラム（デモ）を用意するか，
(iv) 開発のプログラム言語はC++にするか

などのワーキンググループで検討すべき課題が出された．

３. 今後のA02班の会議計画をたて，次回以降には分担者も参加してもらうことにした．

第２回研究集会

日時：1999年1月26日（火）13：30-18:00

場所：名古屋大学豊田講堂第２会議室

出席者：１４名（浅野孝夫，永持仁，渡辺敏正，周暁，谷聖一，戸田誠 之助，藤戸敏弘，草苅良至，上原隆平，元木光男，西田剛，平田富夫， 小野孝男，磯直行）

内容：

今後の班活動の方向を確認し, 共同研究を推進するために研究参加者に よるチュートリアルを以下のプログラムに従って行なった. 内容は近似 アルゴリズムとグラフアルゴリズムに関する発表が主となった. 充実し たディスカッションを目指して発表中も随時質問を受ける形式とし, 会 議終了後のlamp sessionも行った.

1. Efficient Parallel Algorithms on Generalized Chordal Graphs 上原隆平（駒澤大）
2. 半定値計画法による近似アルゴリズム（基本形） 平田富夫（名 大）
3. 半定値計画法による近似アルゴリズム（応用） 浅野孝夫（中央 大）
4. 単一解を持つ3SAT例題の生成 元木光雄（東工大）
5. Not-All-Equal SAT におけるローカルサーチの効率化について 西田剛（東工大）
6. 劣モジュラ被覆問題の近似アルゴリズムとその応用 藤戸敏宏 （広島大）

第３回研究集会

３月５日（金）11時30分から13時，10人（上原，谷，陳，戸田，周，草 刈，平田，小野，永持，浅野）の出席のもとで福岡で開催の予定です．

５．平成１０年度Ａ０３班活動／成果報告

第１回会合

平成１０年１０月１９日（月曜日）午後４時〜６時

場所：京都大学工学部

参加者：浅野（哲夫），杉原厚吉，徳山豪，加藤直樹，今井桂子，玉木久 夫，中野眞一，藤澤克樹

最初のミーティングということで，主として今後の研究の進め方に ついて話し合った．事務的には浅野がまとめ役をすることになった． 最終的な結果が世間にアピールするものであるためには，実際的な 問題に対してデモができるような形での実際的な解（アルゴリズム） の開発が肝要であるという考えで一致した．また，アルゴリズムデータ ベース作成という観点からも，アルゴリズム開発環境を班全体で統一 する必要があるということで共通の認識を得ることができた． とにかく研究を各グループで開始し，成果が得られ次第電子メールなどを 通じて班全体で共有して行こうということになった．

第２回会合

平成１１年１月２６日（火曜日）午後１時〜６時

場所：ホテルアソシア豊橋（愛知県豊橋市）

参加者：浅野（哲夫），杉原厚吉，徳山豪，加藤直樹，今井桂子，中野眞 一，小保方幸二

具体的にアルゴリズム記述方法を統一するという立場から，とりあえず ドイツのマックスプランク研究所で開発されたアルゴリズム記述言語で あるLEDAを班全体で勉強するために，デモプログラムを用いた説明会を 開いた．この言語の特徴は，計算幾何学でよく使われるボロノイ図や 三角形分割などを求める基本的な手続きが多数既に実装されているので， 単にそれらを組み合わせるだけで高度なアルゴリズムを実現できる所に ある．LEDAについての概略的な知識を得た後，各グループでの研究テーマ の紹介を行い．グループ間で協力できることがないかどうかを検討した. LEDAについては, 出席者の間でのアルゴリズムの交流, 交換に非常に 便利だということで意見が一致し, 各研究機関でLEDAのインストールを 始めることになった.

さらに, 班全体での研究交流のために, 共通の研究テーマを設定する ことで意見が一致した. 共通のトピックスとしてな, 計算幾何学の 最も基本的な技報である三角形分割である. CGへの応用, 建築への 応用, 有限要素法への応用, 高次元での三角形分割などが当面の 目標として設定された.

６．平成１０年度Ａ０４班活動／成果報告

特定領域研究(B)「新しいパラダイムとしてのアルゴリズム工学」 A04班 ( 並列／分散アルゴリズム ) の主な活動は, 班会議を開催したことである.
第 1 回 A04班 班会議は, 次の日時および場所で行った.

日時 平成 10 年 10 月 31 日 (土) 9:00 〜 13:10

場所 東北大学工学部電気情報系453会議室

1. 分散アルゴリズムの故障耐性：自己安定性と無待機性

   増澤 利光，井上 美智子 (奈良先端大)

   概要：本稿では, 故障耐性を有する分散アルゴリズムのパラ ダイムとして, 自己安定アルゴリズム, 無待機アルゴリズムを紹介し, 最近のいくつかの研究動向を述べる.

2. 格子基底問題に基づく公開鍵暗号の現状と課題

   櫻井 幸一 (九大)

   概要：格子を利用した公開鍵暗号の構成とその安全性に関 する最近の結果を報告する.

3. PVMについて

   藤原 暁宏 (九工大)

   概要：本稿では, 計算機クラスタを用いて並列処理, 分散 処理を手軽に実現する方法の１つである PVM(Parallel Virtual Machine)を紹介する.

昼食後, 「A04班の今後の活動について」話し合いが持たれた. 各チュートリアルの詳細および第 1 回 A04班 班会議の審議事項は, 成果報告書の「チュートリアル」「第 1 回 A04班 班会議議事録」を参照され たい.
第2回 A04班 班会議は, 平成10年度第2回全体会議に合わせて, 次の日程および 場所で開催する予定である.

日時 平成 11 年 3 月 5 日(金) 11:30 〜 13:15
場所 福岡ソフトリサーチパーク(SRP)
2F 視聴覚研修室

4. 量子計算の可能性と限界

   岩間 一雄 (京大)

   概要：本論文では1.5方向量子有限オートマトンを導入し, 最 も基本的な決定問題である空集合問題が, このモデルに対し非可解で あることを示す.

5. 実並列 / 分散システムへのアルゴリズムの適用

   藤田 聡 (広島大), 山下 雅史 (九大)

   概要：We talk about on-going works for designing algorithms for real parallel/distributed systems; a multiprocessor scheduling algorithm for parallelizing compiler and distributed algorithm for two robots carrying a ladder.

1. 論文および国際会議 54 編
2. 研究会等 28 編
3. 学会等 3 編