報告書番号

R98003

タイトル（和文）

コンピューターネットワーク設計に対する不確実性を考慮した数理モデル

タイトル（英文）

Stochastic Programming Model for the Design of Computer Network

概要 （図表や脚注は「報告書全文」に掲載しております）

現実の数理計画問題には、目的関数および制約条件に不確実要素を伴う場合が多い。例えば、与えられたパラメータ、特に各端末で発生する需要値などは確定値として取り扱うことが困難であることがある。本論文では、確率計画法(Stochastic Programming)を応用したコンピューターネットワーク設計問題を取り扱う。確率計画法とは、このような不確実要素、すなわち確率的要素を考慮した数理計画法である。特に、離散的な確率計画問題（償還請求を有する問題）に対し、L-Shaped法と分枝限定法を加えた解法の枠組を示し、数値実験によってその解法の有効性を示す。

概要 （英文）

In this paper a stochastic version of a concentrator location problem is dealt with in which traffic demand at each terminal location is uncertain. The concentrator location problem is defined as to determine the following; (i)the numbers and locations of concentrators that are to be open and (ii)the allocation of terminals to concentrator sites. The problem is formulated as a stochastic integer linear program, with first stage binary variables concerning network design and second stage continuous variables concerning expansion of capacity. Given a first stage decision, the realization of traffic demand may possibly imply a violation of the capacity constraint of the concentrator. Therefore the second stage decision is taken to correct the violation. The objective function minimizes the cost of connecting terminals and the cost of opening concentrators and the expected recourse cost of capacity expansion. We propose a new algorithm which combines an L-shaped method and a branch and bound method. Finally we demonstrate computational efficiency of our algorithm.

報告者

キーワード