非線形最適化手法の組合わせ最適化へと応用と関連事項

「非線形最適化手法による組合せ最適化問題の効率的解法の開発」という目的で本年度は研究を進めて来た。組合せ最適化問題の中でも安定集合問題を双向グラフ上に一般化した問題に(一般化安定集合問題と呼ぶ)対しては、本研究の目的を完全に達成した。具体的には、双向グラフのパ-フェクト性を導入し、無向グラフのパ-フェクト性との関係を明らかにし、さらにパ-フェクト双向グラフに対する一般化安定集合問題を半正定値計画問題として定式化する方法を示した。この半正定値計画問題に対する多項式時間解法である楕円体法や内点法を用いることでパ-フェクト双向グラフに対する一般化安定集合問題に対する多項式時間解法を構築した。これらの結果は3編の論文としてまとめ、1編はJ.of the Operations Resarch Society of Japanに掲載予定であり、他の2編はMathematical Programming誌と国際会議の査読付きProceedingsに投稿中である。その他の組合せ的な問題点に対しては、グラフのバンド幅を求める問題について、木グラフのバンド幅の上界値を与える方法を提案した。この上界は既知の結果であるChavatalovaの上界より良く、頂点数が10^9以下の木グラフについてはChunnの上界よりもよいものであった。この結果Discrete Mathematics誌に掲載された。また、グラフのある種の変換についての同型性の研究や符号理論や暗号理論に関する研究を進めた。非線形を専門とする分担者は、人工ニューラルネットワークの逆問題解析への応用についての研究を進め、核融合プラズマの位置決定問題に適用し良好な結果を得た。これをFusion Technology誌に発表した。

「非線形最適化手法による組合せ最適化問題の効率的解法の開発」という目的で本年度は研究を進めて来た。組合せ最適化問題の中でも安定集合問題を双向グラフ上に一般化した問題に(一般化安定集合問題と呼ぶ)対しては、本研究の目的を完全に達成した。具体的には、双向グラフのパ-フェクト性を導入し、無向グラフのパ-フェクト性との関係を明らかにし、さらにパ-フェクト双向グラフに対する一般化安定集合問題を半正定値計画問題として定式化する方法を示した。この半正定値計画問題に対する多項式時間解法である楕円体法や内点法を用いることでパ-フェクト双向グラフに対する一般化安定集合問題に対する多項式時間解法を構築した。これらの結果は3編の論文としてまとめ、1編はJ.of the Operations Resarch Society of Japanに掲載予定であり、他の2編はMathematical Programming誌と国際会議の査読付きProceedingsに投稿中である。その他の組合せ的な問題点に対しては、グラフのバンド幅を求める問題について、木グラフのバンド幅の上界値を与える方法を提案した。この上界は既知の結果であるChavatalovaの上界より良く、頂点数が10^9以下の木グラフについてはChunnの上界よりもよいものであった。この結果Discrete Mathematics誌に掲載された。また、グラフのある種の変換についての同型性の研究や符号理論や暗号理論に関する研究を進めた。非線形を専門とする分担者は、人工ニューラルネットワークの逆問題解析への応用についての研究を進め、核融合プラズマの位置決定問題に適用し良好な結果を得た。これをFusion Technology誌に発表した。