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

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

• 批准号: 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/
• 关键词: 離散システム; 通信網; グラフ; ネットワーク; 劣モジュラ関数; 数理計画法; オペレーションズ・リサーチ; 組合せ最適化

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

This paper aims at solving the practical problems of management of large-scale communication networks, and developing methods for solving the problems of optimization, approximation, lower bound, useful information, and basic partition. In particular, changes in equipment such as switches are related to investment planning, and the relationship between switches and users is related to the development of basic segmentation and utilization methods. This method is implemented on the computer, and the actual data is verified. The relationship between basic structure and basic partition is related to the decomposition method of discrete system. In addition, the algorithm related to the high-intensity series of poor quality problems has been successfully accelerated.

项目成果

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)

岩田南

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

M·重野

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

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

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

岩田南