TOKUTEI: algorithm A01han kaigi 98/12/12
A01班 班会議
===============================================================
科研費特定領域研究「新しいパラダイムとしてのアルゴリズム工学」
A01班(離散最適化アルゴリズム) 班会議のお知らせ
===============================================================
この班会議の目的は, 共同研究への発展を目指して, 相互の研究活動を理解する
ことにあります.
講演者一人の持ち時間は70分とし, 40分間講演, 30分間質疑応答討論という
形式で,実質的な研究交流を狙います.A01班以外の方の参加も歓迎します.
日時:平成10年12月12日(土) 10:00-16:40
場所:京都大学数理解析研究所1階115号講義室
(京都大学,北部キャンパス(農学部)の東端;市バス 北白川 下車)
◎数理解析研究所のホームページ: http://www.kurims.kyoto-u.ac.jp/
の日本語のところに 地図があります.
◎当日は土曜のため,正面玄関は締まっています.北側の通用口
(正面玄関に向かって左の方へ)をご利用下さい.
講演者と講演タイトル:
10:00 - 11:10 岩田 覚 (大阪大学 基礎工)
『行列束に対する組合せ論的緩和法』
代数微分方程式系(DAE)で記述される動的システムの解析において,
行列束(matrix pencil)の指数(index)と呼ばれる量が重要な役割を
果たしている.本報告では,行列束の指数を計算するための室田
による組合せ緩和アルゴリズムを紹介し,その改良に関する最新の
成果を報告する.
11:30 - 12:40 野々部 宏司 (京都大学 数理工学)
『資源制約付きスケジューリング問題の定式化と近似解法』
資源制約付きスケジューリング問題(RCSP)は,多くのスケジューリング問題を
定式化できるという汎用性の高さから最近改めて注目を集めている.
しかし現実の応用分野では, スケジュールの評価基準が複雑かつ多様であるなど,
従来のRCSPの枠組では扱うことのできない問題も少なくない.
そこで本研究では, 広範なスケジューリング問題に対応できるよう,
RCSPの定式化を拡張するとともに, タブー探索に基づく近似解法を提案し,
計算実験によりその有用性を確かめる.
14:00 - 15:10 久保 幹雄 (東京商船大学 流通情報工学)
『巡回セールスマン問題に対する Lin-Kernighan 近傍をを用いた
Guided Local Search --大規模問題に対する実装法を中心として--』
(主にユークリッド型の)巡回セールスマン問題に対する最も強力な近傍のひとつに
1973年に Lin と Kernighanによって提案されたもの(Lin-Kernighan 近傍)がある.
Lin-Kernighan 近傍は強力ではあるが,Tabu Search, Simulated Annealingなどの
メタ解法をベースにして大規模問題に対して実装を行おうとすると,幾つかの問題
が発生する.ここでは,Guided Local Searchをベースにしたメタ解法が,
Lin-Kernighan 近傍のような複雑な近傍と比較的相性が良く,大規模問題に対する
強力なメタ解法になる可能性があることを紹介する.
15:30 - 16:40 室田 一雄 (京都大学数理解析研究所)
『離散凸解析のアルゴリズム』
マトロイド,劣モジュラ関数に関するアルゴリズムを概観した後,
M凸関数,L凸関数に関するアルゴリズムの最近の成果を紹介する.
マトロイドの抽象論を知らない人にも分かるように,行列やネットワークの
言葉に翻訳して説明をする.
◎「新しいパラダイムとしてのアルゴリズム工学」のホームページ:
http://www.kuamp.kyoto-u.ac.jp/labs/or/tokutei98/
連絡先: 〒606-XXXX
京都市左京区XXXXXX
京都大学XXXX解析研究所
室田 一雄
EMAIL: murota@hoge.kyoto-u.ac.jp
TEL: 075-753-XXXX
柳浦 睦憲
<最終更新作成日時 1998年11月2日 >