一類帶約束的支撐樹形圖容量擴張問題

楊子蘭 李 睿 楊惠娟

（1.麗江文化旅游學院信息學院，麗江 674199；2.昭通學院數(shù)學與統(tǒng)計學院，昭通 657000）

引言

隨著互聯(lián)網(wǎng)的不斷發(fā)展，我們的生活越來越網(wǎng)絡(luò)化、信息化、數(shù)據(jù)化?！拔磥砭W(wǎng)絡(luò)作為戰(zhàn)略新興產(chǎn)業(yè)的重要發(fā)展方向，預計在2030 年將支撐萬億級、人機物、全時空、安全、智能的連接與服務(wù)，將重點聚焦在加速業(yè)務(wù)創(chuàng)新、促進運營商轉(zhuǎn)型、滿足工業(yè)互聯(lián)網(wǎng)需求等方面的發(fā)展”[1]。通信網(wǎng)絡(luò)作為現(xiàn)代社會重要的基礎(chǔ)設(shè)施，其通信流量傳輸能力也面臨著嚴峻挑戰(zhàn)。為應(yīng)對龐大的需求壓力和發(fā)展壓力，對現(xiàn)有的網(wǎng)絡(luò)進行升級變成學者們一直關(guān)注的一個熱點問題[2-10]。通信網(wǎng)絡(luò)分為有線通信網(wǎng)絡(luò)和無線通信網(wǎng)絡(luò)。有線通信網(wǎng)絡(luò)往往是大型通信網(wǎng)絡(luò)的主干道和基礎(chǔ)設(shè)施[11]。有線通信網(wǎng)絡(luò)受到外界隱私的干擾程度小，不管在保密層面還是可靠性層面都展現(xiàn)出獨具的優(yōu)勢[12]，所以有線通信網(wǎng)絡(luò)具有不可替代的作用[13]。有線通信通常借助于金屬導線、光纖等有形媒介來對信息進行傳輸[13]。

為解決有線通信網(wǎng)絡(luò)擁塞問題，我們考慮對現(xiàn)有的網(wǎng)絡(luò)拓撲結(jié)構(gòu)進行升級，然而，對現(xiàn)有的網(wǎng)絡(luò)拓撲結(jié)構(gòu)進行升級，需要消耗資源，這就涉及各種費用問題。

為應(yīng)對高峰期客戶的流量需求值，為確?？煽康赝ㄐ牛覀儼延脩舫橄蟪蓤D論中的頂點，把傳輸信息的連通載體抽象成圖論中的邊，提出帶約束的支撐樹形圖容量擴張問題（The Capacity Expansion Problem of Spanning Arborescence with Constraints，CEPAC）[10]。CEPAC 問題的數(shù)學模型如下：

其中Γ為有向圖G中所有支撐樹形圖構(gòu)成的集合。有向圖G=(V,A:w,c,p)，V表示圖G的頂點集，A表示圖G的邊集合，且 |V|=n，|A|=m。對任意的弧e∈A，正數(shù)w(e)、c(e)、p(e)分別表示弧e的長度權(quán)重、容量、單位擴張費用。正數(shù)W表示長度權(quán)重限制指標值，正數(shù)D表示預期的流量需求值。當c(e) ＜D時，d*(e) =D-c(e)，當c(e) ≥D時，d*(e) = 0。

在文獻[10]中，作者通過0-1 背包問題歸約出CEPAC 問題的實例，從而證明CEPAC 問題是NP-困難的。其次提出一個（2，1）-近似的擬陣交算法求解了CEPAC問題。

大量文獻[14-18]表明拉格朗日松弛算法是解決NP-困難問題的有效算法。陳文[14]對冷鏈商品物流配送路徑問題展開研究，通過將啟發(fā)式搜索算法與拉格朗日松弛算法相結(jié)合,對冷鏈配送的網(wǎng)絡(luò)模型進行動態(tài)優(yōu)化調(diào)整,獲取最優(yōu)路徑解。席磊，劉治洪等[15]重復更新Q 學習拉格朗日松弛算法，來獲取多區(qū)域協(xié)同。程琳，寧翊森等[16]為研究一類時空網(wǎng)絡(luò)下的弧路徑問題，設(shè)計一個拉格朗日松弛啟發(fā)式算法，可以有效地處理模型中的耦合約束。晉美珠，韓曉霞等[17]提出一種改進的拉格朗日算法以求解一類大規(guī)模的機組組合問題。Requejo C[18]針對權(quán)重受限的最小支撐樹問題（WMST），作者構(gòu)造出WMST 問題的一種有效的上、下界，并且提出兩種基于拉格朗日的WMST算法。仿真實驗表明算法是有效的。

受Requejo C 的啟發(fā)，我們對CEPAC 問題進行進一步研究，獲得CEPAC 問題的有效的上、下界，并設(shè)計改進的拉格朗日松弛算法求解CEPAC問題。

本文的創(chuàng)新點有兩個方面。

第一個方面，理論的創(chuàng)新。通過研究CEPAC問題，得出C(Ts)是CEPAC問題的一個更佳的上界或下界的結(jié)論。其次證明了拉格朗日乘子λk滿足。這些結(jié)論同樣適用于其他的限制性雙權(quán)重支撐樹形圖問題。

第二個方面是算法的創(chuàng)新。在本文設(shè)計的拉格朗日算法中，對任意的弧e∈A，構(gòu)造特殊的系數(shù)sλk(e) =λkw(e) +C(e)，并求出關(guān)于系數(shù)sλk最小的支撐樹形圖Tsλk，通過判斷w(Tsλk)的值是否大于W來有效更新上界UB或更新下界LB，效果較好。

1 CEPAC問題的上下界的分析

Requejo C 對CEPAC 問題的數(shù)學模型進行分析。為方便敘述，對任意的弧e∈A，記C(e) =d*(e)c(e)。當c(e) ＜D時，C(e) =d*(e)c(e)，當c(e) ≥D時，C(e) = 0，于是CEPAC問題的目標函數(shù)變?yōu)?minT∈Γ∑e∈TC(e)。設(shè)T是一棵支撐樹形圖，則記w(T) =∑e∈Tw(e)，C(T) =∑e∈TC(e)。

在不考慮長度權(quán)重限制的條件下，設(shè)TC表示圖G中關(guān)于擴容費用C最小的支撐樹形圖，即TC=(V,ATC)且，設(shè)Tw表示圖G中關(guān)于長度權(quán)重w最小的支撐樹形圖，即Tw=(V,ATw)且。設(shè)ν(CEPAC)表示CEPAC 問題的最優(yōu)值，則有C(TC)≤ν(CEPAC) ≤C(Tw)成立。若CEPAC 問題有解，則Tw是可行解；當w(TC)＞W(wǎng)時，TC是不可行解。因此，我們得出以下性質(zhì)：

性質(zhì)1 若w(TC)≤W，則TC是CEPAC問題的最優(yōu)解。

性質(zhì)2 若w(TC)＞W(wǎng)，則CEPAC問題有最優(yōu)解的充分必要條件是w(Tw)≤W。

假如w(Tw)＞W(wǎng)，則CEPAC 問題無解。假如w(Tw)≤W且C(Tw)=C(TC)，則Tw是CEPAC 問題的一個最優(yōu)解。

假如w(Tw)≤W≤w(TC)，則支撐樹形圖Tw、TC都不是CEPAC 問題的最優(yōu)解。為了找到另外的支撐樹形圖，對任意的弧e∈A，我們構(gòu)造新的系數(shù)s(e) =aw(e) +bC(e)，其中a，b為非負的常數(shù)。不考慮長度權(quán)重限制的條件，在圖G中找出關(guān)于系數(shù)s最小的支撐樹形圖Ts，即Ts=(V,ATs)且。假如a= 0，b= 1，則Ts≡TC；假如a= 1，b= 0，則Ts≡Tw。顯然C(Ts)≥C(TC)。Ts可能是CEPAC 問題的可行解，也有可能是不可行解，因此，得出以下結(jié)論：

性質(zhì)3 樹形圖Ts滿足C(TC)≤C(Ts)≤C(Tw)。假如Ts是CEPAC 問題的一個可行解，即w(Ts)≤W，則C(Ts)是ν(CEPAC)的一個上界。假如Ts是CEPAC 問題的一個不可行解，即w(Ts)＞W(wǎng)，則C(Ts)是ν(CEPAC)的一個下界。

因此，通過構(gòu)造支撐樹形圖Ts，獲得ν(CEPAC)的一個更好的上界或下界。

2 CEPAC問題的拉格朗日松弛有效上下界

引入拉格朗日乘子λ≥0，將CEPAC 問題數(shù)學模型中的長度權(quán)重限制條件吸收到目標函數(shù)中，得到CEPAC問題的拉格朗日松弛問題如下：

記此拉格朗日松弛問題的最優(yōu)值為ν(CEPACλ)。則拉格朗日松弛問題的最優(yōu)值ν(CEPACλ)是原問題最優(yōu)值的一個下界，即有ν(CEPACλ) ≤ν(CEPAC)成立。

對于任意給定的一個非負實數(shù)λ，拉格朗日松弛問題CEPACλ都可以用Chu-Liu/Edmonds算法[19，20]求解。對應(yīng)每一個拉格朗日乘子λ，對任意的弧e∈A，取a=λ，b= 1，構(gòu)造系數(shù)sλ(e) =λw(e) +C(e)。設(shè)Tsλ是拉格朗日松弛問題CEPACλ的一個最優(yōu)解，則則有ν(CEPACλ) = -λW+s(Tsλ)成立。

不同的拉格朗日乘子λ，可以獲得不同的支撐樹形圖Tsλ。為獲得最接近原問題CEPAC 最優(yōu)解的下界，考慮拉格朗日松弛問題CEPACλ的對偶問題：

其中λ*= arg maxλ≥0ν(CEPACλ)。

傳統(tǒng)的拉格朗日松弛問題求解，使用次梯度優(yōu)化算法。次梯度優(yōu)化算法從λ取初始值λ0開始。在每次迭代中，根據(jù)λk求解對應(yīng)的CEPACλk問題。通過設(shè)置步長sk、梯度方向dk的值來更新λk的值，即λk+1= max{0,λk+skdk}。

設(shè)Tsλk是第k次迭代中拉格朗日松弛CEPACλk問題的最優(yōu)解，則有。

當w(Tsλk)＞W(wǎng)時，Tsλk是不可行解，此時根據(jù)性質(zhì)3 可得出v(CEPAC) ≥C(Tsλk)，即C(Tsλk)是v(CEPAC)的一個下界；當w(Tsλk)≤W時，Tsλk是可行解，此時根據(jù)性質(zhì)3 得出v(CEPAC) ≤C(Tsλk)，則C(Tsλk)是v(CEPAC)的一個上界。

性質(zhì)4 拉格朗日乘子λk滿足。

證明：首先設(shè)λk是非負的數(shù)，即λk≥0。設(shè)T是CEPAC 問題的任意一個可行解，則C(TC)≤C(T) ≤C(Tw)，w(Tw)≤w(T) ≤W。把x軸看作權(quán)重長度，把y軸看作擴容費用，建立過兩點(w(Tw),C(Tw))、(w(TC),C(TC)) 的直線方程y=C(Tw)+m(x-w(Tw))，則過兩點(w(Tw),C(Tw))、(w(TC),C(TC))的直線斜率。CEPAC問題的任意一個可行解T的權(quán)重x=w(T) ≤W，則擴容費用y=C(Tw)-λk(x-w(Tw)) ≥C(Tw)-λk(W-w(Tw))。因此CEPAC 問題的任意一個可行解T的擴容費用C(T) ≥C(Tw)-λk(W-w(Tw))。同理當w(TC)＞W(wǎng)時，TC的擴容費用y=C(TC)=C(Tw)-λk(w(TC) -w(Tw)) ≤C(Tw)-λk(W-w(Tw))，所以。

3 CEPAC問題的拉格朗日松弛算法

為得到最接近原問題最優(yōu)解的下界，拉格朗日乘子λk取值越大越好。根據(jù)性質(zhì)4，拉格朗日乘子λk滿足，故本算法中拉格朗日乘子初始值λ0取為。因為C(TC)≤ν(CEPAC) ≤C(Tw)，原問題最優(yōu)解的上界初始值UB取為C(Tw)，Tuk=Tw，下界初始值LB取為C(TC)，Tlk=TC。在每一次拉格朗日迭代中，對任意的弧e∈A，取a=λk，b= 1，構(gòu)造sλk(e) =λkw(e) +C(e)。置。用Chu-Liu/Edmonds求出關(guān)于長度權(quán)重sλk最小的支撐樹形圖Tsλk。根據(jù)性質(zhì)3，樹形圖Tsλk滿足C(TC)≤C(Tsλk)≤C(Tw)。假如Tsλk是CEPAC 問題的一個可行解，即w(Tsλk)≤W，則C(Tsλk)是ν(CEPAC)的一個上界。假如Tsλk是CEPAC 問題的一個不可行解，即w(Tsλk)＞W(wǎng)，則C(Tsλk)是ν(CEPAC)的一個下界。所以當w(Tsλk)≤W且C(Tsλk)≤C(Tuk)時，置UB=C(Tsλk)，Tuk+1=Tsλk，Tlk+1=Tlk；當w(Tsλk)＞W(wǎng)且C(Tsλk)≥C(Tlk)時，置LB=C(Tsλk)，Tsλk，Tuk+1=Tuk。最后置k=k+ 1，置。重復上述過程。當S(Tsλk)的值幾乎接近S(Tuk)的值時算法停止，即對于任意小正數(shù)ε，有成立時，算法停止，此時找到原問題的一個近似解Tuk+1。

綜合以上分析，設(shè)計詳細的算法步驟如下：

算法：拉格朗日松弛算法

輸入：有向圖G=(V,A:w,c,p)，兩個正數(shù)W，D，任意小的正數(shù)ε。

輸出：近似解Tuk+1。

第1 步：對任意的弧e∈A，置擴容費用C(e) =d*(e)c(e)。構(gòu)造新圖G'=(V,A:w,C,W)。其中當c(e) ＜D時，C(e) =d*(e)c(e)，當c(e) ≥D時，C(e) = 0。置k= 0。

第2 步：忽略所有的約束條件，在新圖G'中用Chu-Liu/Edmonds 算法求出關(guān)于擴容費用C最小的支撐樹形圖TC，計算出w(TC)的值。假如w(TC)≤W，則TC為CEPAC 問題的最優(yōu)解，算法停止；否則置Tlk=TC，LB=C(Tlk)。

第3 步：在新圖G'中用Chu-Liu/Edmonds 算法求出關(guān)于長度權(quán)重w最小的支撐樹形圖Tw，計算出w(Tw)的值。假如w(Tw)＞W(wǎng)，則CEPAC 問題無可行解，算法停止；否則置Tuk=Tw，UB=C(Tuk)，。

第4 步：對任意的弧e∈A，構(gòu)造系數(shù)sλk(e) =λkw(e) +C(e)（即a=λk，b= 1），置。

第5 步：在新圖G'中用Chu-Liu/Edmonds 求出關(guān)于系數(shù)sλk最小的支撐樹形圖Tsλk，計算出S(Tsλk)、C(Tsλk)、w(Tsλk)的值。假如w(Tsλk)≤W且C(Tsλk)≤C(Tuk)，則置UB=C(Tsλk)，Tuk+1=Tsλk，Tlk+1=Tlk。假如w(Tsλk)＞W(wǎng)且C(Tsλk)≥C(Tlk)，則置LB=C(Tsλk)，Tlk+1=Tsλk，Tuk+1=Tuk。

第6步：假如|S(Tuk)-S(Tsλk)|≤ε，則支撐樹形圖Tuk+1為CEPAC 問題的一個近似解，輸出近似解Tuk+1，算法停止；否則置k=k+ 1，，轉(zhuǎn)第4步。

定理1 若CEPAC 問題存在可行解，則拉格朗日松弛算法一定能求出CEPAC 問題的一個近似解，且拉格朗日松弛算法的間復雜度為O(kmn)（假設(shè)算法第4步至第5步最多循環(huán)k次）。

證明：若CEPAC 問題不存在可行解，則根據(jù)拉格朗日松弛算法第3 步，有w(Tw)＞W(wǎng)成立，算法停止。

若CEPAC 問題存在可行解，則根據(jù)拉格朗日松弛算法第3 步，置Tuk=Tw，UB=C(Tuk)，。根據(jù)算法第4步，構(gòu)造系數(shù)sλ0(e) =λ0w(e) +C(e)，計算的值。根據(jù)算法第5 步，在新圖G'中用Chu-Liu/Edmonds 算法求出關(guān)于長度權(quán)重sλ0最小的支撐樹形圖Tsλ0，根據(jù)性質(zhì)3，C(Tsλ0)要么是ν(CEPAC)的上界，要么是ν(CEPAC)的下界，此時更新上界UB或LB的值。根據(jù)算法第6步，假如|S(Tu0)-S(Tsλ0) |≤ε，則支撐樹形圖Tu1為CEPAC問題的一個近似解，輸出近似解Tu1，算法停止；否則置k=k+ 1，，重復循環(huán)算法第4 步至第6步，一定存在一個正整數(shù)k，使得算法第4 步至第6 步循環(huán)k次后出現(xiàn)UB和LB幾乎相等的情況，此時有|S(Tuk)-S(Tsλk) |≤ε成立，此時得到近似解Tuk+1。

本文設(shè)計的拉格朗日松弛算法的第1 步構(gòu)造新圖，能在線性時間內(nèi)完成；第2 步的時間復雜度主要取決于利用Chu-Liu/Edmonds 算法求出關(guān)于擴容費用C最小的支撐樹形圖TC的復雜度，其復雜度為O(mn)；第3步的時間復雜度主要取決于利用Chu-Liu/Edmonds 算法求出關(guān)于擴容權(quán)重w最小支撐樹形圖Tw的復雜度，其復雜度為O(mn)；算法第4步的復雜度主要取決于構(gòu)造系數(shù)sλ0(e) =λ0w(e) +C(e)的計算量，其復雜度為O(m)；第5步的時間復雜度主要取決于利用Chu-Liu/Edmonds算法求出關(guān)于系數(shù)sλk最小的支撐樹形圖Tsλk的復雜度，其復雜度為O(mn)；第6步能在線性時間內(nèi)完成；假設(shè)算法第4 步至第6 步最多循環(huán)k次，則拉格朗日松弛算法總的時間復雜度為O(kmn)。

4 實例

已知有向網(wǎng)絡(luò)G=(V,A:w,c,p)如圖1 所示，圖中每條弧上的數(shù)字依次為長度權(quán)重、容量、單位擴容費用。設(shè)點s為根節(jié)點，d= 5，W= 18。

圖1 有向網(wǎng)絡(luò)中樹形圖擴容問題實例

根據(jù)拉格朗日松弛算法第1步，構(gòu)造新圖G'=(V,A:w,C,18)，如圖2所示。取k= 0。

圖2 構(gòu)造新圖G'

根據(jù)算法第2 步，求出以點s為根的關(guān)于擴容費用C最小的支撐樹形圖TC，A(TC)={sv4,v4v3,v3v5,v3v2,v2v1}。計算出w(TC)= 19 ＞18。置Tl0=TC，LB=C(Tl0)= 3。

根據(jù)算法第3 步，求出以點s為根的長度權(quán)重w最小的支撐樹形圖Tw，A(Tw)={sv2,v2v1,sv5,sv4,v4v3}。計 算 出w(Tw)= 13 ＜18。置Tu0=Tw，UB=C(Tu0)= 10，。根據(jù)算法第4 步，對任意的弧e∈A，構(gòu)造系數(shù)sλ0(e)=λ0w(e) +C(e)，置。根據(jù)算法第5 步，在新圖G'中求出以點s為根的關(guān)于系數(shù)sλ0最小的支撐樹形圖Tsλ0，A(Tsλ0)={sv4,sv5,v4v3,v3v2,v2v1}。計算出S(Tsλ0)= 26、C(Tsλ0)= 6、w(Tsλk)= 15 ＜18 且C(Tsλ0)≤C(Tu0)，則置UB=C(Tsλ0)= 6，Tu1=Tsλ0，Tl1=Tl0。根據(jù)算法第6 步，|S(Tu0)-S(Tsλ0) |=28.5-26=2.5 ＞ε，置k=1，，重復第4 步至第6 步，得出：，A(Tsλ1)={sv4,sv5,v4v3,v3v2,v2v1}，S(Tsλ1)=17.2、C(Tsλ1)= 6、w(Tsλ1)= 15 ＜18，UB=C(Tsλ1)= 6，Tu2=Tsλ1，Tl2=Tl1，|S(Tu1)-S(Tsλ1)|= 26 - 17.2 =8.8 ＞ε。置k= 2，，第4 步至第6 步，得出：，A(Tsλ2)={sv4,sv5,v4v3,v3v2,v2v1}，S(Tsλ2)= 17.2、C(Tsλ2)= 6、w(Tsλ2)= 15 且C(Tsλ2)=C(Tu2)，UB=C(Tsλ1)= 6，Tu3=Tsλ2，Tl3=Tl2，|S(Tu2)-S(Tsλ2) |= 17.2 - 17.2 = 0 ＜ε，則支撐樹形圖Tu3=Tsλ2為CEPAC 問題的一個近似解，輸出近似解Tu3（A(Tu3) ={sv4,sv5,v4v3,v3v2,v2v1}），算法停止。

綜上所述，算法第4 步至第6 步循環(huán)3 次就得到近似解Tu3。當問題規(guī)模比較大，計算時間是一個問題時，我們的拉格朗日算法可以快速地獲得一個近似解。

5 總結(jié)

本文對一類帶約束的支撐樹形圖容量擴張問題（CEPAC）展開研究。對任意的弧e∈A，我們構(gòu)造新的系數(shù)s(e) =aw(e) +bC(e)，其中a，b為非負的常數(shù)。不考慮長度權(quán)重限制的條件，在圖G中找出關(guān)于系數(shù)s最小的支撐樹形圖Ts，并得出C(Ts)是CEPAC問題的一個更佳的上界或下界、拉格朗日乘子λk滿足等結(jié)論。最后把上述結(jié)論應(yīng)用在CEPAC 問題的拉格朗日算法設(shè)計中，該算法能求出原問題的一個近似解。

本文得出的結(jié)論以及提出的算法同樣適用于其他類型的雙權(quán)重限制性支撐樹問題。