一個兩段式以拉氏鬆弛法為基礎的網路設計演算法

Abstract

終端機的的配置問題是集中式網路設計的一個重要問題。此問題是假設在一組終端機 和一個唯一的集結器的位置均已知的情況下，連接終端機和集結器使其連接圖形為一 樹狀結構，并且使此樹狀結構中連接至集結器的子樹大小須滿足集結器之輸入端子的 容量限制。其最終目的乃是希望使網路的連接費用降至最低。這個問題相當於一個「 有容量限制的最小展開樹」問題。論文中，一個可解「有容量限制的最小展開樹」問 題的兩段式演算法被提出。在第一個階段中，首先藉著逐漸放松附屬條件產生一個原 來問題的「遞增式拉氏松弛問題」，解此問題并因而得到原有問題之下限；接著利用 一個啟發式之方法修改前面求得之解，得到一個原本問題的可行解和上限。在第二個 階段中，首先藉著一個「啟發式列舉法」求得比第一階段較佳的可行解；接著利用「 分枝定界法」找尋比第一階段更好的上、下限和可行解。實驗的測試終端數多至一百 臺；所有實驗結果顯示，求得解和最佳差距之平均值在3.65% 以下。