研究内容
信頼性の高い情報システムでは、理論に基づく数理手法が活躍しています。 私たちの研究室では、情報システムの設計・評価に有用な数理モデルやアルゴリズム手法、またそれらの解析について研究を行っています。 そして、理論研究の強みを生かして、産学連携研究にも取り組んでいます。 情報システムの多様化に伴い、本研究室が対象とする研究テーマも多岐に渡っていますが、ここでは「組合せ遷移」と「配電運用 (産学連携研究)」について概要を説明します。
組合せ遷移
組合せ遷移とは「状態空間上での遷り変り」を数理モデル化し、解析するアルゴリズム理論です。 その概念は様々な分野で古くから研究されてきましたが、アルゴリズムと計算量の理論研究としては、2008年にその理論フレームワークが確立されました。 今では世界的な研究潮流となり、特に日本では精力的に研究が進められています。
組合せ遷移の最も身近な例はパズルでしょう。 有名な「15パズル」は、1～15の数字が書かれた駒をスライドさせることで、初期盤面から目標盤面へと到達させるパズルです。 では、このスライドの手順を計算することは簡単でしょうか？ また、目標盤面に到達できるときに、その「最短」のスライド手順を求めることはできるでしょうか？ 実は、スライド手順の有無を判定するだけであれば計算は容易なのですが、その最短手順を求めることは計算困難であることが知られています。
私たちの研究室では、グラフ上に定義される組合せ遷移問題を中心に研究を行っています。 例えば、下図はグラフの「独立集合」と呼ばれるものの遷移の一例です。 先の15パズルのように、どのような問題であれば (どのような入力であれば)、容易に計算できるのか？また反対に計算困難となってしまうのか？を理論的に解析しています。 このように計算できる・できないの両面からアプローチすることで、理論を鮮明化させ、究極には「計算」の本質に迫るべく研究を進めています。
組合せ遷移に関する研究動向については、伊藤教授が代表を務めたプロジェクトのWebサイトもご覧ください。
配電運用に現れる課題の数理モデル化とアルゴリズム開発（産学連携研究）
本研究室では、アルゴリズム理論の研究手法を活用して、実社会の課題解決にも取り組んでいます。 特に、産学連携研究を通して、配電運用に現れる種々の課題に取り組んできました。 配電網もネットワークですので、そこに現れる様々な課題（例えば、停電の最小化や早期復旧手順の算出等）は、グラフに関する組合せ最適化問題として数理モデル化できます。 /p>
しかし、適切な数理モデルを構築できても、実際に最適解を見つけることは容易ではありません。 例えば、配電系統の日本標準モデル（ベンチマークデータ）には、10の58乗通りもの配電経路の選択肢が存在します。 このような膨大な選択肢の中から最適な配電経路を見つけるためには、しらみつぶしに候補を探索していては不可能であり、高速なアルゴリズムの開発・活用が必須となります。 特に、配電運用のような社会的説明責任が求められるシステムにおいては、理論解析に基づく数理エビデンスを与えられるようにすることも重要なポイントです。
これまでの研究成果のいくつかは、下記プレスリリースでも発表していますので、そちらもぜひご覧ください。
先輩たちの活躍
先輩たちの中には、研究成果を国内外の研究集会で発表したり、学術論文として出版したりしている方もいます。 また、研究テーマに依っては、他大学や企業の方々とも連携しながら共同研究を行うこともあります。
2025年
【国内研究集会，査読なし】頂点重み関数付きシュタイナー歩道問題に関する研究（鈴木 龍太朗）
鈴木 龍太朗, 斉藤 凜, 伊藤 健洋 (東北大学) 「頂点重み関数付きシュタイナー歩道問題の計算複雑性」
2024年度冬のLAシンポジウム, 京都大学, 2025年1月27日(月)－29日(水)．
2024年
【学術雑誌，査読あり】配電系統構成の最適化に関する研究（野崎 哲平）
杉村 修平, 金子 曜久, 林 泰弘 (早稲田大学), 野崎 哲平, 鈴木 顕, 伊藤 健洋 (東北大学), 田邊 隆之 (明電舎)「停電残量最小化を目的とした配電系統構成の多角的評価」電気学会論文誌B, 144巻, 12号, pp. 640-649, 2024. (DOI: 10.1541/ieejpes.144.640)
【学術雑誌，査読あり】点素最短パスの遷移に関する研究（斉藤 凜）
Rin Saito (東北大学), Hiroshi Eto (九州工業大学), Takehiro Ito (東北大学), Ryuhei Uehara (北陸先端科学技術大学院大学), "Reconfiguration of vertex-disjoint shortest paths on graphs," Journal of Graph Algorithms and Applications, 28(3), 87–101, 2024. (DOI: 10.7155/jgaa.v28i3.2973)
【国際会議，査読あり】マトロイドの基の組の遷移問題に関する研究（斉藤 凜）
Tesshu Hanaka (九州大学), Yuni Iwamasa (京都大学), Yasuaki Kobayashi (北海道大学), Yuto Okada (名古屋大学), Rin Saito (東北大学), "Basis Sequence Reconfiguration in the Union of Matroids," Proceedings of the 35th International Symposium on Algorithms and Computation (ISAAC 2024), Leibniz International Proceedings in Informatics, Vol. 322, 38:1-38:16, 2024. (DOI: 10.4230/LIPIcs.ISAAC.2024.38)
ISAAC 2024, オーストラリア・シドニー, 2024年12月8日(日)－11日(水)．
【国際ワークショップ，査読なし】独立集合最適化遷移に関する研究（川名 陸翔）
Rikuto Kawana, Rin Saito, Takehiro Ito, "A new optimization variant of independent set reconfiguration," The 5th International Workshop on Combinatorial Reconfiguration (CoRe 2024), 日本・福岡, 2024年10月7日(月)－11日(金)．
【国内研究集会，査読なし】グラフ上の詰め込みと組合せ遷移に関する研究（斉藤 凜）
斉藤 凜 (東北大学)「グラフ上の詰め込みと組合せ遷移」離散数学とその応用研究集会2024 , 山形大学, 2024年8月19日(月)－21日(水)．
【国内研究集会，査読なし】マトロイドの基の組の遷移問題に関する研究（斉藤 凜）
土中 哲秀 (九州大学), 岩政 勇仁 (京都大学), 小林 靖明 (北海道大学), 岡田 優斗 (名古屋大学), 斉藤 凜 (東北大学)「マトロイドの基の組の遷移問題」
電子情報通信学会 コンピュテーション研究会 , 東北大学, 2024年10月24日(木)．
最適化の理論とアルゴリズム：未来を担う若手研究者の集い 2024 , 筑波大学, 2024年5月18日(土)－19日(日)．（優秀発表賞受賞）
【国際会議，査読あり】独立集合遷移問題のデータセットに関する研究（渡邉 拓武）
Takehide Soh (神戸大学), Takumu Watanabe (東北大学), Jun Kawahara (京都大学), Akira Suzuki, Takehiro Ito (東北大学), "Scalable hard instances for independent set reconfiguration," Proceedings of the 22nd International Symposium on Experimental Algorithms (SEA 2024), Leibniz International Proceedings in Informatics, Vol. 301, 26:1-26:15, 2024. (DOI: 10.4230/LIPIcs.SEA.2024.26)
SEA 2024, オーストリア・ウィーン, 2024年7月24日(水)－26日(金)．
【国内研究集会，査読なし】SAT充足解の多様性に関する研究（斉藤 凜）
儀間 達也 (名古屋大学), 岩政 勇仁 (京都大学), 小林 靖明 (北海道大学), 栗田 和宏, 大舘 陽太 (名古屋大学), 斉藤 凜 (東北大学)「Computing diverse pair of solutions for SAT」
2024年電子情報通信学会 総合大会, [DS-2] COMP-AFSA学生シンポジウム, 広島大学, 2024年3月4日(月)－8日(金)．
2023年度冬のLAシンポジウム, 京都大学, 2024年2月19日(月)－21日(水)．
2023年
【国内研究集会，査読なし】配電系統構成の最適化に関する研究（野崎 哲平）
杉村 修平, 金子 曜久, 林 泰弘 (早稲田大学), 野崎 哲平, 鈴木 顕, 伊藤 健洋 (東北大学), 田邊 隆之 (明電舎)「事故復旧を考慮した配電系統構成の最適化に関する検討」電気学会 2023年電力技術・電力系統技術合同研究会, 熊本大学, 2023年9月25日(月)－26日(火)．
【国際会議，査読あり】点素最短パスの遷移に関する研究（斉藤 凜）
Rin Saito (東北大学), Hiroshi Eto (九州工業大学), Takehiro Ito (東北大学), Ryuhei Uehara (北陸先端科学技術大学院大学), "Reconfiguration of vertex-disjoint shortest paths on graphs," Proceedings of the 17th International Conference and Workshops on Algorithms and Computation (WALCOM 2023), Lecture Notes in Computer Science, Vol. 13973, pp. 191-201, 2023. (DOI: 10.1007/978-3-031-27051-2_17)
WALCOM 2023, 台湾・新竹, 2023年3月22日(水)－24日(金)．
【国内研究集会，査読なし】点素最短パスの遷移に関する研究（斉藤 凜）
斉藤 凜 (東北大学), 江藤 宏 (九州工業大学), 伊藤 健洋 (東北大学), 上原 隆平 (北陸先端科学技術大学院大学)「点素最短パス遷移問題に対するアルゴリズム」科研費・学術変革領域研究(B)「組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合」2022年度「組合せ遷移」学生シンポジウム, 東北大学, 2023年2月20日(月)．
2022年
【国内研究集会，査読なし】点素最短パスの遷移に関する研究（斉藤 凜）
Rin Saito (東北大学), Hiroshi Eto (九州工業大学), Takehiro Ito (東北大学), Ryuhei Uehara (北陸先端科学技術大学院大学), "Complexity of reconfiguring vertex-disjoint shortest paths," 電子情報通信学会 コンピュテーション研究会, 愛媛大学, 2022年12月6日(火)．
【国際ワークショップ，査読なし】点素最短パスの遷移に関する研究（斉藤 凜）
Rin Saito, Hiroshi Eto, Takehiro Ito, "Reconfiguration of vertex-disjoint shortest paths on split graphs," The 4th International Workshop on Combinatorial Reconfiguration (CoRe 2022), カナダ・バンフ, 2022年5月9日(月)－13日(金)．
【国際会議，査読あり】機械学習の説明手法に関する研究（浅野 孝平）
Kohei Asano, Jinhee Chun, "Post-hoc global explanation using hypersphere sets," Proceedings of the 14th International Conference on Agents and Artificial Intelligence (ICAART 2022), Vol. 2, pp. 236-243, 2022. (DOI: 10.5220/0010819100003116)
ICAART 2022, オンライン, 2022年2月3日(木)－5日(土)．
2021年
【国際会議，査読あり】機械学習の説明手法に関する研究（浅野 孝平）
Kohei Asano, Jinhee Chun, "Post-hoc explanation using a mimic rule for numerical data," Proceedings of the 13th International Conference on Agents and Artificial Intelligence (ICAART 2021), Vol. 2, pp. 768-774, 2021. (DOI: 10.5220/0010238907680774)
ICAART 2021, オンライン, 2021年2月4日(木)－6日(土)．
2020年
【国内研究集会，査読なし】機械学習の説明手法に関する研究（浅野 孝平）
浅野 孝平, 全 眞嬉「模倣ルールを用いた機械学習の説明手法」2020年度 (第34回) 人工知能学会全国大会, オンライン, 2020年6月9日(火)－12日(金)．