A further challenge to the optimization problems with submodular discrete-convex structures

对子模离散凸结构优化问题的进一步挑战

• 批准号: 22K11922
• 负责人: 藤重 悟
• 金额: $ 1.83万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K11922/
• 关键词: 最適化; 離散構造; 劣モジュラ関数

有効な離散凸構造の本質に迫るべく、精力的に劣モジュラ的離散構造の観点から離散凸構造に関する研究を展開しており、離散最適化諸問題に対する有効な解の導出のために、また、関連分野の研究をさらに飛躍的に進展させるために、劣モジュラ的な離散構造や、より一般的な離散凸構造の理論の更なる精緻化による離散最適化への更なる挑戦を目指して研究を進めてきた。それらの成果は、以下の通りである。1. S. Fujishige and F. Tardella: Discrete 2-convex functions. Mathematical Programming, Ser. A, published online, 26 October 2021.（離散凸関数として、二つの格子点に関して定まる離散2-凸関数の概念を導入し、その有用な数理構造を明らかにした。）2. S. Fujishige and H. Hirai: Compression of M${}^\natural$-convex functions --- Flag matroids and valuated permutohedra. Journal of Combinatorial Theory, Ser. A, Vol. 185 (2022) Article 105525 (published online, 25 August 2021).（離散数理における flag matroid の観点からM凸関数を見直し、その圧縮によってM凸関数から付値置換多面体が生成されることを示した。）令和４年度の成果としては、最適化の基盤をなす線形計画問題に対する新しいアプローチとなる理論的ならびにアルゴリズム的な枠組みを提起し、解析を行ない、その成果をアーカイブに公表した。この成果は、高い評価の国際会議であるIPCO2023に採択されて、発表の予定である。

The study of discrete convex structures with discrete optimization problems has developed rapidly. The study of discrete convex structures with discrete optimization problems has developed rapidly. The theory of general discrete convex structures is refined, the discrete optimization theory is refined, and the research on discrete convex structures is advanced.それらの成果は、以下の通りである。1. S. Fujishige and F. Tardella: Discrete 2-convex functions. Mathematical Programming, Ser. A, published online, 26 October 2021. (The concept of discrete 2-convex number is introduced and useful mathematical construction is clarified.) 2. S. Fujishige and H. Hirai: Compression of M${}^\natural$-convex functions --- Flag matroids and valuated permutohedra. Journal of Combinatorial Theory, Ser. A, Vol. 185 (2022) Article 105525 (published online, 25 August 2021). (Discrete mathematics: flag matroid points, M convex numbers, straight lines, compression lines, M convex numbers, substitution lines, polyhedra, etc.) The results of the fourth year of this year are presented in the form of a new theory for optimizing the linear planning problem. The results of the IPCO2023 were presented in advance.