離散凸解析による資源配分問題の研究

本研究の目的は，離散凸解析の双対理論を軸に据えて，離散資源の公平配分問題に関する理論とアルゴリズムを構築することである．この目的に沿って，以下の成果を得た．Ｍ凸集合上の辞書式最適化問題は，基多面体上の辞書式最適化問題において，変数に整数制約を課した問題と位置付けることができる．後者については，1980年頃に構造定理やアルゴリズムを含む包括的な理論が構築されている．これに関して詳細な文献調査を行い，連続変数の場合と離散変数の場合の構造定理とアルゴリズムの比較を行い，離散変数理論と連続変数理論の構造的な対応関係を解明して論文を完成させた．これにより，基多面体上の資源公平配分問題に関する理論とアルゴリズムの全体像が明確となった．離散資源の公平配分問題のより一般的問題設定として，劣モジュラ制約をもつネットワークフローを扱った．従来知られていた線形関数を目的関数とする劣モジュラ制約フロー問題の解法と整合する形で，公平配分の成す集合の記述と効率的なアルゴリズムの設計に成功し，論文として公表した．離散凸解析の理論と多面体的組合せ論を繋ぐためには，離散凸集合の不等式表現を明らかにする必要がある．離散凸解析において，今まで，Ｍ凸系統の集合の不等式表現は十分解明されてきたが，Ｌ２凸集合の不等式による記述は明らかにされていなかった．本研究においては，Ｌ凸集合が有向グラフの最短路に関係した不等式系で記述されることに着目し，Ｌ２凸集合の不等式表現を導出した．ここで得られた定理は，離散資源の公平配分問題とは独立に，離散凸解析の基本定理として重要な成果である．

本研究の目的は，離散凸解析の双対理論を軸に据えて，離散資源の公平配分問題に関する理論とアルゴリズムを構築することである．この目的に沿って，以下の成果を得た．Ｍ凸集合上の辞書式最適化問題は，基多面体上の辞書式最適化問題において，変数に整数制約を課した問題と位置付けることができる．後者については，1980年頃に構造定理やアルゴリズムを含む包括的な理論が構築されている．これに関して詳細な文献調査を行い，連続変数の場合と離散変数の場合の構造定理とアルゴリズムの比較を行い，離散変数理論と連続変数理論の構造的な対応関係を解明して論文を完成させた．これにより，基多面体上の資源公平配分問題に関する理論とアルゴリズムの全体像が明確となった．離散資源の公平配分問題のより一般的問題設定として，劣モジュラ制約をもつネットワークフローを扱った．従来知られていた線形関数を目的関数とする劣モジュラ制約フロー問題の解法と整合する形で，公平配分の成す集合の記述と効率的なアルゴリズムの設計に成功し，論文として公表した．離散凸解析の理論と多面体的組合せ論を繋ぐためには，離散凸集合の不等式表現を明らかにする必要がある．離散凸解析において，今まで，Ｍ凸系統の集合の不等式表現は十分解明されてきたが，Ｌ２凸集合の不等式による記述は明らかにされていなかった．本研究においては，Ｌ凸集合が有向グラフの最短路に関係した不等式系で記述されることに着目し，Ｌ２凸集合の不等式表現を導出した．ここで得られた定理は，離散資源の公平配分問題とは独立に，離散凸解析の基本定理として重要な成果である．