報告書番号

R99002

タイトル（和文）

多期間にわたる通信量の不確実性を考慮したコンピューターネットワーク設計手法

タイトル（英文）

Multi-Stage Stochastic Programming Model for the Design of Computer Network

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

現実の数理計画問題には、目的関数および制約条件に不確実要素を伴う場合が多い。例えば、コンピューターネットワークの設計においては、各端末で発生する需要値などを確定値として取り扱うことが困難である。本報告では、確率計画法を応用したコンピューターネットワーク設計問題を取り扱う。本報告では、集線装置配置問題に対する逐次線形近似法と整数計画法を加えた解法の枠組を示す。。多期間にわたる投資決定では、各期の決定がその期までに生じたシナリオの履歴に依存するため、複雑な問題となる。T期間の各期においてn個のシナリオが起こりうる場合、通常では全体としてn^T個のシナリオを考慮しなければならない。開発した方法では、ネットワークにおける通信需要と、集線装置への容量増設費用に対するある単調性の仮定の下でこの問題をn個のシナリオを持つT個の部分問題へと分解し、計算実験によりこの計算効率を示す。

概要 （英文）

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 multi-stage integer linear program, with first stage binary variables concerning network design and continuous recourse variables concerning expansion of capacity. Given a first stage decision, the series of realization of traffic demand may possibly imply a violation of the capacity constraint of the concentrator. Therefore from the second stage to the last stage, recourse action 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. Under some assumptions it decomposes the problem into a set of problems as many as the number of stages in parallel. Finally we demonstrate the computational efficiency of our algorithm for the multi-stage model.

報告者

キーワード