離散システムの分解手法の通信網管理への応用

离散系统分解方法在通信网络管理中的应用

• 批准号: 07750084
• 负责人: 岩田 覚
• 金额: $ 0.58万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07750084/
• 关键词: 離散システム; 通信網; グラフ; ネットワーク; 劣モジュラ関数; 数理計画法; オペレーションズ・リサーチ; 組合せ最適化

本研究は,大規模な通信網の管理のために実際問題として解くことが要求されるが,効率的な解法は望めないような最適化問題に対して,近似解や下界値といった有用な情報を得るために,劣モジュラ関数や基本分割に関する理論的な成果を活用する手法の開発を目的としていた.特に,交換機等の設備の更改に関する投資計画に関連して,交換機とその利用者との関係についての膨大なデータの構造を的確に把握するために,基本分割を利用した手法を開発した.この手法を計算機上で実現し,実際的なデータによってその有用性を実験的に確認した.また,離散システムの分解手法そのものに関しては,基本構造と基本分割との間の関係に,マトロイドにおける強射の劣モジュラシステムへの拡張が重要な役割を果たしていることが明らかになった.さらに,劣モジュラシステムの強射系列に関する算法の高速化に成功した.

本研究旨在为大规模通信网络管理的实际问题需要解决的优化问题提供有用的信息，例如近似解和下界，但无法期望获得有效的解决方案。准确理解海量数据的关系结构为此，我们开发了一种使用基本分解的方法。我们在计算机上实现了该方法，并使用实际数据通过实验证实了其有用性。此外，关于离散系统的分解方法本身，我们开发了一种使用已经清楚，拟阵中态射向子模系统的推广在结构与基本分解之间的关系中起着重要作用。此外，已经表明，拟阵中态射向子模系统的推广也发挥着重要作用。成功了。

项目成果

S. Iwata & K. Murota: "A Theorem on the Principal Stercture for Independent Matchings" Discrete Appl. Math.61. 229-244 (1995)

岩田南

S. Iwata & K. Murota: "A Mimimax Thorem and a Dulmage-Mendelsohn Type Decomposition for a Class of G Pthatrices" SIAM J. Matrix Anal. Appl.16. 719-734 (1995)

岩田南

S. Iwata: "Principal Structure of Submodular Systems and Hithcock-type Independent Flou" Combinatorica. 15. 515-532 (1995)

S. Iwata：“子模系统的主要结构和 Hithcock 型独立 Flou”Combinatorica。

M. Shigeno & S. Iwata: "A Dual Approximation Approach to Weighted Matroid Intersection" Oper. Res. Lett.18. 153-156 (1995)

M·重野