Hokkaido University

Institute for Chemical Reaction Design and Discovery

Research Outline

I have investigated the design and analysis of efficient algorithms for optimization problems on discrete structures such as graphs and networks. In particular, I have conducted theoretical research focusing on matroids and submodular functions, which are known as structures that commonly appear in various efficiently solvable combinatorial optimization problems. Since chemical reactions are phenomena described by changes of chemical bonds between atoms in molecules, I expect that there are many places in which discrete optimization techniques can contribute to the design and discovery of chemical reactions.

Continuous optimization problems which do not enjoy convexity are hard to solve in general as they admit locally optimal solutions which are not globally optimal. Search methods for chemical reaction routes such as GRRM actually enumerate the locally optimal and saddle points of the potential energy surface. I have been trying to extend the methods there to more general setting of nonconvex optimization.

Representative Research Achievements

• 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