平成１０年度第３回Ａ０１班会議 議事録

日時：1999年3月5日11:30--13:00
場所：福岡ソフトウェアリサーチパーク2階視聴覚室
出席者： 室田，茨木，石井，伊藤，岩田，久保，齋藤，塩浦，塩出，降旗，
         増山，柳浦，今井


1. 次回班研究会について

次の予定で次回班研究会を開催することとした．

日時：6月24日(木曜)
場所：東京大学本郷キャンパス近辺
(参考: この翌日には東京で，離散構造とアルゴリズムの研究会が開催される予定.)

日程決定の後，発表形式，発表者について議論した．次回は第1回研究会で発
表していないグループの発表を主体に，特定領域全体のアルゴリズムデータベー
スに関する発表も入れることとした．具体的には，以下の4つの発表を土台の
案とすることにした．

石井先生グループ
増山先生グループ（伊藤先生が発表予定）
今井グループ
アルゴリズムDBについて
* 浅野孝夫先生(他班との協調で，マトロイドとネットワークのアルゴリズム間
  の関係から)
* 藤澤先生(アルゴリズムデータベース実現に関連してSDP計算サーバなど)

10時から17時の予定で，詳細については班長と会場担当の方で検討し，班全体
に通知することとした．


2. アルゴリズムデータベースについて

特定領域研究全体のアルゴリズムデータベースについて，班としての方針を議
論した．これは，上の次回班研究会で検討している発表にも関連する．

班としてはデータベース構築のためのコーディネータが必要であるということ
になり，久保先生にコーディネートを依頼することとした．コーディネータは
実際の開発とかを行うのものではなく，各グループで用意するべきもの・締切
り・方法などコーディネートすることを行う．

アルゴリズムデータベースについて，各グループから現状・方針の報告を行っ
た．

* 室田グループ：
  マトロイドでの最適化を主テーマに，線形関数を目的関数とするようなマトロ
  イド上での最適化について，グラフ・行列(2値，有理数)で表現できる場合の
  システム開発を検討．マトロイド交差．ネットワークフローと関係するので，
  A02班との連携についても検討する．

  離散凸解析のアルゴリズムについて，塩浦らの理論的によいものと，実際的
  なものとの準備的な比較も行っている．岩田らのアルゴリズムの実装に基づい
  たものの開発．行列分解システムは，既にホームぺージで公開している．

* 石井グループ
  ネットワーク信頼度に関する研究に関して，システムが開発されている．
  近似解法での新しい汎用性のある枠組みを分枝限定法の拡張で検討しており，
  スケジューリング問題に適用することを計画している．配置問題に関する検討．

* 茨木グループ：メタヒューリスティック
  野之部の開発したスケジューリングのアルゴリズムについては，かなり使える
  ものになりつつある．また，制約充足問題というより広い枠組みでのアルゴ
  リズムについても研究・システム開発が進んでいる．GAP (Generalized
  Assignment Problem)に関する研究，MAXSATへの適用・拡張も行っており，汎
  用性が高く色々なものに使えるものになっている．

* 今井グループ：
  不変量計算について，特に絡み目のJones多項式，ネットワーク信頼度を軸に，
  システムを開発中である．グラフの基本アルゴリズムなどはLEDAなどを使うこ
  とも検討する．
  また，基本アルゴリズムの問題として，文字列の接尾辞配列(suffix array)と
  関連したデータ構造を求める一連のパッケージも開発中である．

* 久保グループ：
  ジョブショップやスケジューリング，巡回セールスマン問題，２次割り当て問
  題のこれまで作ったもので未公開のものなど公開することを検討する．
  Vehicle Routingでのシステムで，ただし道路ネットワークなどデータベース
  の部分と組み合わせているため，そのデータベース自身の著作権に触れる部分
  公開できないので，アルゴリズムエンジンの部分だけを公開することを検討す
  る．
  LEDAについては，久保先生は最初の版から経験があり，LEDAに関する他研究班
  の検討動向にも注意しながら進める．

* 藤重グループ(岩田先生代理)：
  従来の離散システムに関する理論の上に，アルゴリズム工学としての観点の付
  加して，データベースとして貢献できる部分を検討する．特に，マトロイド・
  劣モジュラ関数に関する離散構造の表現法に関して離散凸解析の研究班と共同
  で検討したい。双対定理に関して既に発表した多項式時間アルゴリズムは，楕
  円体法や塩浦氏のＭ凸関数最小化アルゴリズムを用いるため，実装には適なさ
  ない。より効率的なアルゴリズムの開発を現在進めている。
  組合せ緩和法など，組合せ最適化技法の行列計算への応用に関する理論的な
  成果を実現につなげることを目指す．

* 増山グループ：
  既にできているものとして，AGVシステムで開発したものがある．ただ，企業
  で使って事故が起こるなどというところまでの責任はとれない(これについて
  は，アルゴリズムデータベース全体でのバグの扱いに通じる)．
  市川先生のところのアーキテクチャ関係のbranch-and-bound, branch-and-cut
  のシステムがあり，これについては市川先生に聞くこととした．
  自然言語関係のものもあるが，マッチングを使っているという点でアルゴリズ
  ム工学に通じるものであるが，研究用に公開された新聞データと一体となって
  おりそれも含めた公開は著作権の問題が生じ，また，ソフトウェア工学とアル
  ゴリズム工学との差別化という点の問題点も指摘された．
  分担者の伊藤先生より，理論的に出しているところの需要がある部分について
  学生さんとの共同研究を検討することも報告された．

以上の各グループからの報告の後，アルゴリズムデータベース全体に関しての
議論を行った．既に出た点もあることで，バグの存在などデータベースの質に
ついてどう考える必要性が指摘された．このデータベースの中には
・多くの人が研究していてたくさんの人が使えるという種類のものから，
・新しい分野でここでしかない種類のものまで
色々なものがあり，それにもバグの問題は関係する．また，以前の班会議から
の継続の問題点であるが，デモの重要性について指摘された．関連して，デー
タベースはソースコードなのか，計算サーバなのかという問題起もされ，その
点からも異なるレベルでの公開を行うこととした．茨木先生より，全体で同一
レベルまで実現するというより，各グループで実現レベルが色々でよいのでは
とのコメントがあった．

久保先生より，京大藤沢先生のSDP(半定値計画各システム)の公開で計算をサー
バ側でするという計算サーバ方式での公開を行うと，デモが実現される面が指
摘された．こういう計算サーバという形態によるデータベース公開も班として
検討するため，次回班研究会でこのテーマについて藤沢先生に発表を依頼する
こととした．

また，次回班研究会で本班のマトロイド最適化に深く関わるテーマのネットワー
クアルゴリズムが他班で研究されていることに鑑み，A02班の浅野孝夫先生に
このテーマの発表を依頼することとした．


参考資料：
6月24日A01班会議プログラム(案)

10:00-11:00 浅野孝夫
11:00-12:00 今井浩

13:30-14:30 石井博昭
14:30-15:30 伊藤大雄

16:00-17:00 藤沢克樹

近日中にタイトル+数行のアブストラクトをもらう
(1998-12-12のアナウンスメントを参照)

翌6月25日に離散構造とアルゴリズム研究会が東京で開催されます．
会場など詳細については，同研究会主査の藤重悟先生に連絡ください．