劣モジュラ構造とその一般化で切り開く最適化の数理とアルゴリズム

使用子模结构及其概括开发的优化数学和算法

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

離散凸構造の中でも特に劣モジュラ的な離散構造は、大規模な組合せ的な最適化問題を効率よく解決するための手がかりを与える重要な離散構造であり、有効な離散凸構造の本質に迫るべく、劣モジュラ的離散構造の観点から研究を展開し、それらの成果は、以下の通りである。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 optimization problem of discrete convex structures is solved efficiently by solving the optimization problem of large-scale combinations of discrete convex structures. 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 numbers on integer lattice points is introduced and useful mathematical structures are made clear.) 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 is deeply understood. The flag matroid is pointed out. The M convex number is straight. The M convex number is reduced. The M convex number is replaced by the polyhedron.) In 2004, the company conducted research on the wiring board, and optimized the research on the wiring board. The basic framework of optimization theory is proposed by IPCO2023, which is an international conference on optimization theory.

项目成果

Signed ring families and signed posets

带符号环族和带符号偏序集

• DOI: 10.1080/10556788.2020.1740219
• 发表时间: 2020
• 期刊: Optimization Methods and Software
• 影响因子: 2.2
• 作者: Fujishige Satoru;Takazawa Kenjiro;Yokoi Yu;Kazutoshi Ando an Satoru Fujishige
• 通讯作者: Kazutoshi Ando an Satoru Fujishige

Compression of M#-convex functions --- Flag matroids and valuated permutohedra

M 的压缩

• DOI: 10.1016/j.jcta.2021.105525
• 发表时间: 2022
• 期刊: Journal of Combinatorial Theory, Series A
• 作者: Fujishige Satoru;Hirai Hiroshi
• 通讯作者: Hirai Hiroshi

Barter markets, indivisibilities, and Markovian core

• DOI: 10.1111/boer.12279
• 发表时间: 2021-03
• 期刊: Bulletin of Economic Research
• 影响因子: 0.8
• 作者: S. Fujishige;Zaifu Yang

A NOTE ON A NEARLY UNIFORM PARTITION INTO COMMON INDEPENDENT SETS OF TWO MATROIDS

关于两个矩阵的公共独立集的几乎一致划分的注记

• DOI: 10.15807/jorsj.63.71
• 发表时间: 2020
• 期刊: Journal of the Operations Research Society of Japan
• 作者: Fujishige Satoru;Takazawa Kenjiro;Yokoi Yu
• 通讯作者: Yokoi Yu

Minimizing submodular functions on diamonds via generalized fractional matroid matchings

通过广义分数拟阵匹配最小化钻石的子模函数

• DOI: 10.1016/j.jctb.2022.07.005
• 发表时间: 2022
• 期刊: Journal of Combinatorial Theory, Series B
• 作者: Fujishige Satoru;Kiraly Tamas;Makino Kazuhisa;Takazawa Kenjiro;Tanigawa Shin-ichi
• 通讯作者: Tanigawa Shin-ichi