離散最適化における準凸性の理論の構築と社会工学への応用

离散优化半凸理论构建及其在社会工程中的应用

• 批准号: 13874016
• 负责人: 室田 一雄
• 金额: $ 1.34万
• 依托单位: The University of Tokyo (2002-2003)Kyoto University (2001)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Exploratory Research
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-13874016/
• 关键词: 凸解析(convex analysis); 整数計画(integer program); 主算法(primal algorithm); 離散最適化(discrete optimization); 非線形計画(nonlinear program); 数理計画(mathematical program); ネットワークフロー(network flow); マトロイド(matroid); 離散最適化; 凸性; 準凸性; 非線形計画; 組合せ最適化; 凖凸関数; マトロイド

まず,数理経済学における離散凸関数の応用について研究を進めた.不可分な財を含む経済均衡モデルにおいて,供給者の費用関数がM凸関数かつ消費者の効用関数がM凹関数の場合に競争均衡が存在することが,研究代表者らの昨年度までの研究において証明されていた.本年度はさらにこの研究を進めて,競争均衡を実際に求める方法について検討し,多項式時間で競争均衡が求められることを示した.具体的には,競争均衡を求める問題を元にしてM凸劣モジュラ流問題をつくり,これを既存の多項式時間アルゴリズムで解いて得られた出力を適切に変換することで競争均衡が得られる,という手法である.これはM凸劣モジュラ流問題の応用としても興味深い結果である.次に,最適配分問題に対する効率的な解法の研究を行った.生産ラインでのバッファ配分や労働力・資源の配分など,生産システム設計の際に頻繁に現れる最適配分問題は,離散準凸性の理論を適用しやすい問題の一つである.離散準凸関数の理論を踏まえて,現実に現れる最適配分問題を定式化し,その離散構造を明らかにすると共に効率的な解法を提案した,具体的には,劣モジュラ制約の元での最適配分問題に対するHochbaumの高速解法がなぜうまく働くのかを離散凸性の視点から検討し,その結果を元にM凸関数に対する高速な最小化アルゴリズムを提案した.また,dial-a-ride transit system, isotone regressionなどに応用をもつ,双対最小費用流問題について研究を進めた.この問題が準L凸関数最小化問題の特殊ケースである,という事実を踏まえ,既存の解法を見直し,準L凸関数に対する解法へと拡張した.

In mathematics and mathematics, discrete convex numbers are studied in detail. In this paper, the authors prove that competitive equilibrium exists when the supplier's cost relation is M convex relation and the consumer's cost relation is M concave relation. This year, the research on competitive equilibrium has been advanced, and the method of competitive equilibrium in polynomial time has been shown. Specifically, the competitive equilibrium problem is solved by solving the convex flow problem in polynomial time. This paper discusses the application of the convex flow problem and its results. Second, the study of efficient solutions to optimal subproblems. The most suitable component problem frequently occurs in the design of production systems, and the theory of discrete quasi-convexity is applied to one of the problems. The theory of discrete quasi-convex relations is developed, and the optimal fitting problem is formulated. The discrete structure is proposed to solve the optimal fitting problem with common efficiency. Specifically, the optimal fitting problem with inferior constraint elements is solved with high speed by Hochbaum.また,dial-a-ride transit system, isotone regressionなどに応用をもつ,双対最小费用流问题について研究を进めた. This problem is a special case of minimizing quasi-L-convex relations. The existing solution is straightforward. The solution of quasi-L-convex relations is extended.

项目成果

A.Shioura: "Fast Scaling Algorithms for M-convex Function Minimization with Application to the Resource Allocation Problem"Discrete Applied Mathematics. 134. 303-316 (2003)

A.Shioura：“M 凸函数最小化的快速缩放算法及其在资源分配问题中的应用”离散应用数学。

K.Murota, A.Tamura: "Application of M-convex submodular flow problem to mathematical economics"Japan Journal of Industrial and Applied Mathematics. 20. 257-277 (2003)

K.Murota、A.Tamura：“M-凸子模流问题在数理经济学中的应用”日本工业与应用数学杂志。

K.Murota, A.Shioura: "Quasi M-convex and L-convex Functions : Quasiconvexity in Discrete Optimization"Discrete Applied Mathematics. (掲載予定). (2003)

K.Murota、A.Shioura：“拟 M 凸函数和 L 凸函数：离散优化中的拟凸性”离散应用数学（即将出版）。

K.Murota, A.Tamura: "New Characterizations of M-convex Functions and Their Applications to Economic Equilibrium Models"Discrete Applied Mathematics. (掲載予定). (2003)

K.Murota、A.Tamura：“M 凸函数的新特征及其在经济均衡模型中的应用”离散应用数学（即将出版）。

V.Danilov, G.Koshevoy, K.Murota: "Discrete convexity and equilibria in economies with indivisible goods and money"Mathematical Social Sciences. 41. 251-273 (2001)

V.Danilov、G.Koshevoy、K.Murota：“具有不可分割的商品和货币的经济体中的离散凸性和均衡”数学社会科学。