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

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

基本信息

批准号：
13740079
负责人：
塩浦昭義
金额：
$ 1.15万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

项目摘要

本年度は,組合せ凸関数の理論を構築するとともに,様々な組合せ最適化問題に対して非線形計画アプローチを用いた効率的なアルゴリズムを提案することを目指した.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

今年，我们的目标是构建组合凸函数理论，并针对各种组合优化问题提出使用非线性规划方法的有效算法。1．虽然是一个概念，但作为基于组合凸函数理论的高效解的基础，构建一种最小化M凸函数的高速算法是必不可少的。今年，我们将提出一种最小化M凸函数的高速算法M-凸函数及其特殊情况。：M 凸函数最小化的快速缩放算法及其在资源分配问题中的应用，S.Moriguchi，A.Shioura：关于一般资源分配的 Hochbaum 缩放算法问题2. 到目前为止，组合凸函数的概念主要针对整数格点上定义的函数，但存在许多涉及实数变量的组合优化问题，我们将凸函数的概念扩展到实数空间上的函数，并导出了各种。这些函数的性质。结果总结在以下论文中：K. Murota, A. Shioura: M-凸和 L-凸函数在实空间上：组合凸函数的两个共轭类3.为了利用组合凸函数理论解决一般组合优化问题，需要从问题的局部结构中找到M-凸和L-凸等良好的结构。今年，我们发现 M 凸性和 L 凸性源自组合优化中的一个基本问题，称为最小成本流问题，我们在下面的论文中对此进行了总结，A. Shioura：网络流中的替代和补充被视为离散凸性