FIT2018 第17回情報科学技術フォーラム

イベント企画

最適モデリング

9月19日(水) 13:00-15:00
第3イベント会場（D棟D25講義室）

【セッション概要】モデル化は、数理的手法による現実の問題解決や現象の解明に不可欠な第一歩ですが、生命現象や社会現象の様に支配法則の不明確な対象を扱う際には、同じ現象に対しても多数のモデルが考えられます。JST CREST「大規模複雑システムの最適モデリング手法の構築」では、生命現象におけるネットワークや電力システム、交通システムを題材に、離散数学・最適化分野における最新の知見を駆使して、多数のモデルの中から最も適切なものを効率的に選択する体系的な手法の創出を目指しています。本シンポジウムでは、その中でも特に離散最適化技術に関連した話題を中心に紹介します。

13:00-13:40 講演(1) 微分代数方程式モデルの最適化
岩田　覚（東京大学情報理工学系研究科教授）
【概要】微分代数方程式は、微分演算を含む連立方程式系であり、電気回路、機械力学系、化学反応系等、多くの動的システムの記述に自然に使われる道具である。正規形の常微分方程式と異なり、任意に与えられた初期解を通る軌道が存在するとは限らないため、矛盾のない初期値条件を与えることも自明ではない。そのために、計算誤差が不可避な数値計算によって解を得ることは、常微分方程式よりも本質的に難しくなる。微分代数方程式に対して、常微分方程式との近さを表す各種の指数が定義されている。常微分方程式の指数は0、代数方程式の指数は1となる。一般に、指数が高くなるほど、数値的に解くことが難しくなる。同じ物理現象を記述する際にも、注目する自由変数の選び方や式の立て方によって、異なる指数の微分代数方程式が得られる。そのため、できるだけ指数が小さな微分代数方程式を自動的に導出する効率的な手法の構築が望まれる。本講演では、この目標に向かって、離散最適化技法を援用した一連の研究成果を解説する。
	【略歴】 1993年東京大学大学院工学系研究科計数工学専攻修士課程修了、1994年京都大学数理解析研究所助手、1997年大阪大学大学院基礎工学研究科講師、2000年東京大学大学院工学系研究科助教授、2001年東京大学大学院情報理工学系研究科助教授、2006年京都大学数理解析研究所助教授、2008年京都大学数理解析研究所教授、2013年東京大学大学院情報理工学系研究科教授、数理工学、離散最適化の研究に従事。日本IBM科学賞、Fulkerson Prize、文部科学大臣表彰若手科学者賞、STOC Best Paper Award等受賞。
13:40-14:20 講演(2) 配電損失最小化 ―実グラフに潜む性質の活用―
山口　勇太郎（大阪大学大学院情報科学研究科情報数理学専攻助教）
【概要】現代社会における生活は、インターネット、ソーシャルネットワーク、交通網、電力網など、様々なグラフ（ネットワーク）構造と密接に関わっており、それらのネットワークを利用・運用していくことで成り立っている。多種多様な状況における意思決定は、数理最適化問題としてモデル化できることが多く、その解法の提案や評価の研究が盛んに行われている。これらの実用を考える際に、元の状況で実際に要求される速度・精度で問題が解けるかどうかは、対象となるグラフの規模だけではなく、その背後に潜む性質にも強く依存する。本講演では、電力システムにおける重要な意思決定の一つである、配電網での電力損失の最小化をメインの題材とし、グラフに潜む性質に着目した最適化問題の解法・評価に関して紹介する。特に、グラフの木分解と、木分解を利用した動的計画法に関して、その有用性・優位性を実験的に示す。
	【略歴】 2013年京都大学大学院理学研究科数学・数理解析専攻修士課程修了、2016年東京大学大学院情報理工学系研究科数理情報学専攻博士後期課程修了。博士（情報理工学）。2016年より大阪大学大学院情報科学研究科情報数理学専攻助教。2017年より理化学研究所革新知能統合研究センター客員研究員（兼任）。離散最適化の理論と応用に関する研究に従事。
14:20-15:00 講演(3) 安定マッチング理論と展開型マッチングゲーム
横井　優（国立情報学研究所情報学プリンシプル研究系助教）
【概要】労働者と雇用者のマッチングや、婚活市場における男女のマッチングなど、各々希望をもつ人々の間でのマッチングを考える場面は、世の中に数多く見受けられる。このような状況を扱う安定マッチングモデルは、Gale-Shapley(1962)に提案されて以来、活発に研究されてきた。このモデルでは、各主体が申告する選好を元に、オーガナイザーが結果を決定する、中央集権型のマッチングが前提とされている。しかし、社会にはそのような統制がされていない市場も多く、そこでは各主体が周囲の戦略を観測しながら、逐次的な意思決定をしている。本研究では、そのような状況を表すモデルとして、展開型マッチングゲームを提案する。具体的には、逐次的にジョブオファーを受ける求職者が、競合相手の戦略を考慮しながら自身の戦略を決定する状況を扱う。最適戦略の計算複雑度についての特徴付けを与え、また、各求職者が均衡戦略に従った際に結果として得られるマッチングの性質を解析する。
	【略歴】 2012年大阪大学基礎工学部システム科学科卒業。2014年東京大学大学院情報理工学系研究科数理情報学専攻修士課程修了、2017年同博士課程修了、博士（情報理工学）。2017年4月より国立情報学研究所情報学プリンシプル研究系助教。日本オペレーションズ・リサーチ学会会員。組合せ最適化やマッチング理論の研究に従事。