都市内の災害時の流動に関する総合的研究

―効率性と頑健性を備えた都市実現に向けて―

第2回研究会(2013年度)

開催日時：

2013年7月25日(木) 15:00-17:00

開催場所：

南山大学瀬戸キャンパスG棟G304 (アクセス)

問い合わせ先:

南山大学 情報理工学部 佐々木美裕
〒489-0863
瀬戸市せいれい町27番地
Phone/0561-89-2000
E-mail/mihiro [AT] nanzan-u.ac.jp

プログラム

「大規模な0-1整数計画問題に対する発見的解法」
梅谷俊治(大阪大学 大学院情報科学研究科 情報数理学専攻)

概要：集合被覆問題とは，台集合とその部分集合の族および各部分集合のコストが与えられたとき， 台集合の全ての要素を被覆するコスト最小の部分集合の組み合わせを求める問題であり， 人員スケジューリング問題，配送計画問題，データの論理的解析など多くの応用を持つことが知られている． 一方で，実際の応用事例では，個々の事例に固有の追加制約を伴うため単純な集合被覆問題では定式化できない場合が多い． そのため，大規模な集合被覆問題に対して効率的な発見的解法がいくつか提案されているにも関わらず， 現場では性能の劣る混合整数計画問題に対する汎用ソルバーを利用せざるを得ない場合が少なくない． 本講演では， 集合被覆問題を含むより広いクラスの0-1整数計画問題において大規模な問題例を効率的に解くための手法をいくつか紹介する．