組合せ凸関数理論の構築と組合せ最適化問題に対する非線形計画アプローチの研究

组合凸函数理论的构建及组合优化问题的非线性规划方法研究

• 批准号: 13740079
• 负责人: 塩浦 昭義
• 金额: $ 1.15万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13740079/
• 关键词: 凸集合; 凸関数; 凸性; マトロイド; 劣モジュラ関数; 離散最適化; 非線形計画; 組合せ最適化

本年度は,組合せ凸関数の理論を構築するとともに,様々な組合せ最適化問題に対して非線形計画アプローチを用いた効率的なアルゴリズムを提案することを目指した.1.組合せ凸関数の理論において中心的な役割を果たすのがM凸関数という概念であるが,組合せ凸関数理論に基づく効率的な解法の基礎として,M凸関数最小化に対する高速算法の構築が必須となる.本年度はM凸関数最小化およびその特殊ケースに対する高速算法を提案し,下記の論文にまとめた.A.Shioura : Fast Scaling Algorithms for M-convex Function Minimization with Application to the Resource Allocation Problem, S.Moriguchi, A.Shioura : On Hochbaum's Scaling Algorithm for the General Resource Allocation Problem2.これまで組合せ凸関数の概念は主に整数格子点上で定義された関数を対象としていたが,組合せ最適化問題の中には実変数に関する問題が少なくない.この事実を踏まえて,組合せ凸関数の概念を実数空間上の関数へと拡張し,その関数に関する様々な性質を導いた.この結果は下記の論文にまとめられている.K.Murota, A.Shioura : M-convex and L-convex Functions over the Real Space : Two Conjugate Classes of Combinatorial Convex Functions3.組合せ凸関数の理論を利用して一般の組合せ最適化問題を解くためには,その問題の部分的な構造からM凸性,L凸性のような良い構造を見出すことが必要である.本年度は,最小費用流問題という,組合せ最適化においては基本的な問題からM凸性,L凸性が生じることがわかり,下記の論文にまとめた.K.Murota, A.Shioura : Substitutes and Complements in Network Flows Viewed as Discrete Convexity

This year, we have combined the theory of convexity data and the optimization of the problem of optimization. This year, we have proposed that the rate of non-linear planning should be improved. 1. In the center of the theory of convex number, the concept of convex number is very important, the solution of the rate of convexity in mathematics and physics is very difficult, and the algorithm of high-speed algorithm of minimizing convexity number is necessary. This year, to minimize the number of convexities, we need to minimize the number of high-speed algorithms. A.Shioura: Fast Scaling Algorithms for M-convex Function Minimization with Application to the Resource Allocation Problem, S.Moriguchi, A.Shioura: On Hochbaum's Scaling Algorithm for the General Resource Allocation Problem2. In the concept of convex number, the concept of convex number is defined on the integer grid point, and the number of numbers in the optimization problem is less than that in the optimization problem. This is a combination of the concept of convex data, the number of data in space, the number of data, and the number of data in the space. K.Murota, A.Shioura: M-convex and L-convex Functions over the Real Space: Two Conjugate Classes of Combinatorial Convex Functions3. The theory of convexity number theory makes use of the general optimization problem to solve the problem of convexity, the convexity of the part of the problem, and the convexity of L-convexity to produce the necessary convexity. This year, the minimum usage flow problem is divided into two basic problems: convexity, convexity, convexity and convexity. K.Murota, A.Shioura: Substitutes and Complements in Network Flows Viewed as Discrete Convexity

项目成果

S.Moriguchi, K.Murota, A.Shioura: "Scaling Algorithms for M-convex Function Minimization"IEICE Transactions on Fundamentals. E85-A. 922-929 (2002)

S.Moriguchi、K.Murota、A.Shioura：“M 凸函数最小化的缩放算法”IEICE Transactions on Fundamentals。