Hokkaido University

Institute for Chemical Reaction Design and Discovery

研究概要

グラフ・ネットワークに代表される離散構造上の最適化問題に対する効率的なアルゴリズムの設計と解析に関する研究をして来ました。特に、最適解が効率的に計算できる多くの組合せ最適化問題に共通の構造として知られるマトロイド・劣モジュラ関数に注目して、理論研究を進めてきました。化学反応は、原子の組み合わせで形成される分子において、結合の組み換えによって生じる現象ですので、その設計や発見には、様々な形で離散最適化手法が活用できるのではないかと期待しています。

連続最適化問題に関して、凸性が保証されない場合には、大域的には最適でない局所最適解が多数存在し、そのために解くことが難しいと言われています。しかし、GRRMの様な化学反応経路の探索手法においては、ポテンシャル・エネルギー面の極小点と鞍点とを列挙して、ネットワーク構造を抽出することが行われています。ここで用いられている手法を、より広く非凸最適化問題全般に利用できないだろうかと考えて、研究に取り組んでいます。　　

代表的な研究成果

• Selecting Molecules with Diverse Structures and Properties by Maximizing Submodular Functions of Descriptors Learned with Graph Neural Networks 
  Tomohiro Nakamura, Shinsaku Sakaue, Kaito Fujii, Yu Harabuchi, Satoshi Maeda, Satoru Iwata. Scientific Reports, 2022, 12: 1124.
  DOI: 10.1038/s41598-022-04967-9
• A Weighted Linear Matroid Parity Algorithm 
  Satoru Iwata, Yusuke Kobayashi. SIAM J. Comput., 2022, 51 (2), 238-280.
  DOI: 10.1137/17M1141709
• Index Reduction for Differential-Algebraic Equations with Mixed Matrices,
  Satoru Iwata, Taihei Oki, Mizuyo Takamatsu, J. ACM, 2019, 66 (5), 1-34.
  DOI: 10.1145/3341499
• Computing the Signed Distance Between Overlapping Ellipsoids 
  Satoru Iwata, Yuji Nakatsukasa, Akiko Takeda. SIAM J. Optim., 2015, 25(4), 2359-2384.
  DOI: 10.1137/140979654
• A Combinatorial Strongly Polynomial Algorithm for Minimizing Submodular Functions 
  Satoru Iwata, Lisa Fleischer, Satoru Fujishige. J. ACM, 2001, 48(4), 761-777. 
  DOI: 10.1145/502090.502096