第14回研究会
第14回研究会を以下の通り開催いたしました．
- 日時：2017年 11月 4日 (土) 13:30〜
- 会場：東京理科大学 葛飾キャンパス 管理棟5階第1演習室 (マップで3番の建物)
(神楽坂キャンパスではございません．ご注意ください．)
- 講演者１：伊豆永 洋一 氏 (筑波大学 ビジネスサイエンス系)
- 題目：モジュラリティデンシティ最大化問題に対する再定式化とアルゴリズム
- 概要：
最適化問題に対する定式化の方法は，（当然ながら）様々なものが考えられ，その方法によりアルゴリズムの設計も大きく異なる．
本発表では，コミュニティ抽出におけるモジュラリティデンシティの最大化問題を対象とし，いくつかの再定式化とそれに対するアルゴリズムを紹介する．
具体的には，非負対称行列を変数に持つ問題に対する半正定値計画緩和に基づくアルゴリズムと，0-1整数計画問題に対する分枝価格法に基づくアルゴリズムである．
本発表の内容は，松井知己氏（東京工業大学）・山本芳嗣氏（筑波大学），佐藤圭介氏（鉄道総研）との共同研究に基づくものである．
- 講演者２：森 立平 氏 (東京工業大学 情報理工学院 数理・計算科学系)
- 題目：線形計画緩和と半正定値計画緩和の階層の統一的な理解
- 概要：一般的にNP困難である組合せ最適化問題の近似解を得るための最も汎用的な手法は線形/半正定値計画緩和であろう。本講演では局所的な制約を持つ制約充足問題に対する3種類の半正定値計画緩和の階層を紹介し、それらの確率分布に基づく直感的かつ統一的な理解を説明する。この理解に基づき、制約充足問題の充足不可能性について半正定値緩和を適用した際の限界を示す。
戻る
