組合せ最適化における多面体手法の高度化

本研究計画は組合せ最適化における多面体的アルゴリズムの高度化を目的とするものであり，特に，「拡張定式化の利用」，「複数の多面体の利用」の2点に注目している．2022年度の主要な成果として，ある種の制約付き重み付き2マッチング問題に対する初の多項式時間アルゴリズムの設計が挙げられる．重み付き2マッチング問題は，多面体的アプローチを用いてアルゴリズムを設計することのできる組合せ最適化における古典的かつ重要な問題である．しかし，付加的な制約を課すと問題は急激に難しくなり，多項式時間アルゴリズムが知られていない問題が数多く存在している．本研究では，ある種の制約付き重み付き2マッチング問題に対して，指数本の制約式を持つ拡張定式化を用いて実行可能解全体を表現するという，今までにないアプローチを用いて多項式時間アルゴリズムを設計している．これはまさに当初目指していた通りの「拡張定式化を利用して多面体的アルゴリズムを高度化する成果」であると言える．この研究は前年度以前から継続して取り組んでいたものであり，2022年度に数理最適化の主要誌である Mathematical Programming誌に採録された．その他の重要な成果として，最短点素パス問題に対する多項式時間アルゴリズムの設計が挙げられる．最短路問題は多面体的に解釈でき，多項式時間で解ける組合せ最適化問題であるが，その拡張である最短点素パス問題は多項式時間アルゴリズムの存在が未解決である．本研究では，ある種の条件をみたす最短点素パス問題に対して，初の乱択多項式時間アルゴリズムを与えている．この成果は，アルゴリズム理論の主要国際会議である International Symposium on Algorithms and Computation (ISAAC) に採択された．

本研究計画は組合せ最適化における多面体的アルゴリズムの高度化を目的とするものであり，特に，「拡張定式化の利用」，「複数の多面体の利用」の2点に注目している．2022年度の主要な成果として，ある種の制約付き重み付き2マッチング問題に対する初の多項式時間アルゴリズムの設計が挙げられる．重み付き2マッチング問題は，多面体的アプローチを用いてアルゴリズムを設計することのできる組合せ最適化における古典的かつ重要な問題である．しかし，付加的な制約を課すと問題は急激に難しくなり，多項式時間アルゴリズムが知られていない問題が数多く存在している．本研究では，ある種の制約付き重み付き2マッチング問題に対して，指数本の制約式を持つ拡張定式化を用いて実行可能解全体を表現するという，今までにないアプローチを用いて多項式時間アルゴリズムを設計している．これはまさに当初目指していた通りの「拡張定式化を利用して多面体的アルゴリズムを高度化する成果」であると言える．この研究は前年度以前から継続して取り組んでいたものであり，2022年度に数理最適化の主要誌である Mathematical Programming誌に採録された．その他の重要な成果として，最短点素パス問題に対する多項式時間アルゴリズムの設計が挙げられる．最短路問題は多面体的に解釈でき，多項式時間で解ける組合せ最適化問題であるが，その拡張である最短点素パス問題は多項式時間アルゴリズムの存在が未解決である．本研究では，ある種の条件をみたす最短点素パス問題に対して，初の乱択多項式時間アルゴリズムを与えている．この成果は，アルゴリズム理論の主要国際会議である International Symposium on Algorithms and Computation (ISAAC) に採択された．