報告書番号

R97023

タイトル（和文）

コンピューターネットワークの集線装置配置問題に対する整数計画モデル

タイトル（英文）

INTEGER PROGRAMMING MODEL FOR CONCENTRATOR LOCATION PROBLEM

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

コンピューターネットワークは情報化社会の根幹を成すものである。今後コンピューターネットワークにおいては，情報量の増大と多様化が予想されているため，ネットワークの提供者側には，効率の良い高速の情報伝送能力を持つネットワークを構築する技術が求められている。コンピューターネットワークの最適構成とは，ネットワークに含まれる要素の地理的配置・規模・機能・性能に関する制約条件を満たし，最も経済的なネットワークを選択することである。本報告では，端末の集合を接続する集線装置を最小費用で配置する問題に対して，問題固有の構造を利用して効率的に最適解を求めるアルゴリズムを開発し，数値実験により解法の有効性を示す。

概要 （英文）

TOPOLOGICAL DESIGN OF CENTRALIZED COMPUTER NETWORKS IS AN IMPORTANT PROBLEM THAT HAS BEEN INVESTIGATED BY MANY RESEARCHERS. SUCH NETWORKS TYPICALLY INVOLE A LARGE NUMBER OF TERMINALS CONNECTED TO CONCENTRATORS,THAT ARE THEN CONNECTED TO A CENTRAL COMPUTING SITE. THIS PAPER DEALS ESPECIALLY WITH A CONCENTRATOR LOCATION PROBLEM AMONG GENERAL TOPOLOGICAL NETWORK DESIGN PROBLEMS. THE CONCENTRATOR LOCATION PROBLEM IS DEFINED TO DETERMINE THE FOLLOWING:(I) THE NUMBERS ANDLOCATIONS OF CONCENTRATORS TO BE OPEN AND (II) THE ALLOCATION OF TERMINALS TO CONCENTRATOR SITES WITHOUT VIOLATING THE CAPACITIES OF THE CONCENRATORS. WE PROPOSE A NEW EXACT ALGORITHM (FRACTIONAL CUTTING PLANE ALGORITHM/BRANCH-AND-BOUND) FOR THE CONCENTRATOR LOCATION PROBLEM. IN THIS APPROACH,WE FORMULATE AN INTEGER PROGRAMMING PROBLEM. THEN,WE DERIVE A CLASS OF VALID INEQUALITIES AND SHOW A FAST GREEDY ALGORITHM FOR A SEPARATION PROBLEM. A GOOD LOWER BOUND IS OBTAINED BY A LIFTING PROCEDURE. FINALLY,WE DEMONSTRATE THE COMPUTATIONAL EFFICIENCY OF OUR ALGORITHM.

報告者

キーワード