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

基于离散凸分析的资源分配问题研究

基本信息

批准号：
20K11697
负责人：
室田一雄
金额：
$ 1.91万
依托单位：
The Institute of Statistical Mathematics (2021-2022)Tokyo Metropolitan University (2020)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

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

本研究的目的是围绕离散凸分析的对偶理论，构建离散资源公平分配问题的理论和算法。根据这一目标，我们获得了以下结果。 M 凸集上的词典优化问题可以定位为对变量施加整数约束的基本多面体上的词典优化问题。对于后者，包括结构定理和算法在内的综合理论在1980年左右被构建。我们对此主题进行了详细的文献调查，比较了连续变量和离散变量的结构定理和算法，阐明了离散变量理论和连续变量理论的结构对应关系，完成了论文．至此，基多面体上的资源公平分配问题的理论和算法的全貌已经清晰起来。作为离散资源公平分配问题的更一般的问题设置，我们用子模约束来处理网络流。我们成功地描述了公平分布形成的集合，并以与解决以线性函数为目标函数的子模约束流问题的传统方法一致的方式设计了有效的算法，并将其作为论文发表。为了连接离散凸分析和多面体组合理论，有必要阐明离散凸集的不等式表达式。在离散凸分析中，M凸系统集合的不等式表示已经得到很好的阐明，但不等式对L2凸集的描述还没有明确。在本研究中，我们重点关注 L 凸集是由与有向图最短路径相关的不等式系统描述的事实，并导出了 L2 凸集的不等式表示。这里得到的定理是作为离散凸分析基本定理的一个重要结果，与离散资源的公平分配问题无关。