一类带约束的支撑树形图容量扩张问题

杨子兰 李 睿 杨惠娟

（1.丽江文化旅游学院信息学院，丽江 674199；2.昭通学院数学与统计学院，昭通 657000）

引言

随着互联网的不断发展，我们的生活越来越网络化、信息化、数据化。“未来网络作为战略新兴产业的重要发展方向，预计在2030 年将支撑万亿级、人机物、全时空、安全、智能的连接与服务，将重点聚焦在加速业务创新、促进运营商转型、满足工业互联网需求等方面的发展”[1]。通信网络作为现代社会重要的基础设施，其通信流量传输能力也面临着严峻挑战。为应对庞大的需求压力和发展压力，对现有的网络进行升级变成学者们一直关注的一个热点问题[2-10]。通信网络分为有线通信网络和无线通信网络。有线通信网络往往是大型通信网络的主干道和基础设施[11]。有线通信网络受到外界隐私的干扰程度小，不管在保密层面还是可靠性层面都展现出独具的优势[12]，所以有线通信网络具有不可替代的作用[13]。有线通信通常借助于金属导线、光纤等有形媒介来对信息进行传输[13]。

为解决有线通信网络拥塞问题，我们考虑对现有的网络拓扑结构进行升级，然而，对现有的网络拓扑结构进行升级，需要消耗资源，这就涉及各种费用问题。

为应对高峰期客户的流量需求值，为确保可靠地通信，我们把用户抽象成图论中的顶点，把传输信息的连通载体抽象成图论中的边，提出带约束的支撑树形图容量扩张问题（The Capacity Expansion Problem of Spanning Arborescence with Constraints，CEPAC）[10]。CEPAC 问题的数学模型如下：

其中Γ为有向图G中所有支撑树形图构成的集合。有向图G=(V,A:w,c,p)，V表示图G的顶点集，A表示图G的边集合，且 |V|=n，|A|=m。对任意的弧e∈A，正数w(e)、c(e)、p(e)分别表示弧e的长度权重、容量、单位扩张费用。正数W表示长度权重限制指标值，正数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]对冷链商品物流配送路径问题展开研究，通过将启发式搜索算法与拉格朗日松弛算法相结合,对冷链配送的网络模型进行动态优化调整,获取最优路径解。席磊，刘治洪等[15]重复更新Q 学习拉格朗日松弛算法，来获取多区域协同。程琳，宁翊森等[16]为研究一类时空网络下的弧路径问题，设计一个拉格朗日松弛启发式算法，可以有效地处理模型中的耦合约束。晋美珠，韩晓霞等[17]提出一种改进的拉格朗日算法以求解一类大规模的机组组合问题。Requejo C[18]针对权重受限的最小支撑树问题（WMST），作者构造出WMST 问题的一种有效的上、下界，并且提出两种基于拉格朗日的WMST算法。仿真实验表明算法是有效的。

受Requejo C 的启发，我们对CEPAC 问题进行进一步研究，获得CEPAC 问题的有效的上、下界，并设计改进的拉格朗日松弛算法求解CEPAC问题。

本文的创新点有两个方面。

第一个方面，理论的创新。通过研究CEPAC问题，得出C(Ts)是CEPAC问题的一个更佳的上界或下界的结论。其次证明了拉格朗日乘子λk满足。这些结论同样适用于其他的限制性双权重支撑树形图问题。

第二个方面是算法的创新。在本文设计的拉格朗日算法中，对任意的弧e∈A，构造特殊的系数sλk(e) =λkw(e) +C(e)，并求出关于系数sλk最小的支撑树形图Tsλk，通过判断w(Tsλk)的值是否大于W来有效更新上界UB或更新下界LB，效果较好。

1 CEPAC问题的上下界的分析

Requejo C 对CEPAC 问题的数学模型进行分析。为方便叙述，对任意的弧e∈A，记C(e) =d*(e)c(e)。当c(e) ＜D时，C(e) =d*(e)c(e)，当c(e) ≥D时，C(e) = 0，于是CEPAC问题的目标函数变为 minT∈Γ∑e∈TC(e)。设T是一棵支撑树形图，则记w(T) =∑e∈Tw(e)，C(T) =∑e∈TC(e)。

在不考虑长度权重限制的条件下，设TC表示图G中关于扩容费用C最小的支撑树形图，即TC=(V,ATC)且，设Tw表示图G中关于长度权重w最小的支撑树形图，即Tw=(V,ATw)且。设ν(CEPAC)表示CEPAC 问题的最优值，则有C(TC)≤ν(CEPAC) ≤C(Tw)成立。若CEPAC 问题有解，则Tw是可行解；当w(TC)＞W时，TC是不可行解。因此，我们得出以下性质：

性质1 若w(TC)≤W，则TC是CEPAC问题的最优解。

性质2 若w(TC)＞W，则CEPAC问题有最优解的充分必要条件是w(Tw)≤W。

假如w(Tw)＞W，则CEPAC 问题无解。假如w(Tw)≤W且C(Tw)=C(TC)，则Tw是CEPAC 问题的一个最优解。

假如w(Tw)≤W≤w(TC)，则支撑树形图Tw、TC都不是CEPAC 问题的最优解。为了找到另外的支撑树形图，对任意的弧e∈A，我们构造新的系数s(e) =aw(e) +bC(e)，其中a，b为非负的常数。不考虑长度权重限制的条件，在图G中找出关于系数s最小的支撑树形图Ts，即Ts=(V,ATs)且。假如a= 0，b= 1，则Ts≡TC；假如a= 1，b= 0，则Ts≡Tw。显然C(Ts)≥C(TC)。Ts可能是CEPAC 问题的可行解，也有可能是不可行解，因此，得出以下结论：

性质3 树形图Ts满足C(TC)≤C(Ts)≤C(Tw)。假如Ts是CEPAC 问题的一个可行解，即w(Ts)≤W，则C(Ts)是ν(CEPAC)的一个上界。假如Ts是CEPAC 问题的一个不可行解，即w(Ts)＞W，则C(Ts)是ν(CEPAC)的一个下界。

因此，通过构造支撑树形图Ts，获得ν(CEPAC)的一个更好的上界或下界。

2 CEPAC问题的拉格朗日松弛有效上下界

引入拉格朗日乘子λ≥0，将CEPAC 问题数学模型中的长度权重限制条件吸收到目标函数中，得到CEPAC问题的拉格朗日松弛问题如下：

记此拉格朗日松弛问题的最优值为ν(CEPACλ)。则拉格朗日松弛问题的最优值ν(CEPACλ)是原问题最优值的一个下界，即有ν(CEPACλ) ≤ν(CEPAC)成立。

对于任意给定的一个非负实数λ，拉格朗日松弛问题CEPACλ都可以用Chu-Liu/Edmonds算法[19，20]求解。对应每一个拉格朗日乘子λ，对任意的弧e∈A，取a=λ，b= 1，构造系数sλ(e) =λw(e) +C(e)。设Tsλ是拉格朗日松弛问题CEPACλ的一个最优解，则则有ν(CEPACλ) = -λW+s(Tsλ)成立。

不同的拉格朗日乘子λ，可以获得不同的支撑树形图Tsλ。为获得最接近原问题CEPAC 最优解的下界，考虑拉格朗日松弛问题CEPACλ的对偶问题：

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

传统的拉格朗日松弛问题求解，使用次梯度优化算法。次梯度优化算法从λ取初始值λ0开始。在每次迭代中，根据λk求解对应的CEPACλk问题。通过设置步长sk、梯度方向dk的值来更新λk的值，即λk+1= max{0,λk+skdk}。

设Tsλk是第k次迭代中拉格朗日松弛CEPACλk问题的最优解，则有。

当w(Tsλk)＞W时，Tsλk是不可行解，此时根据性质3 可得出v(CEPAC) ≥C(Tsλk)，即C(Tsλk)是v(CEPAC)的一个下界；当w(Tsλk)≤W时，Tsλk是可行解，此时根据性质3 得出v(CEPAC) ≤C(Tsλk)，则C(Tsλk)是v(CEPAC)的一个上界。

性质4 拉格朗日乘子λk满足。

证明：首先设λk是非负的数，即λk≥0。设T是CEPAC 问题的任意一个可行解，则C(TC)≤C(T) ≤C(Tw)，w(Tw)≤w(T) ≤W。把x轴看作权重长度，把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的权重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时，TC的扩容费用y=C(TC)=C(Tw)-λk(w(TC) -w(Tw)) ≤C(Tw)-λk(W-w(Tw))，所以。

3 CEPAC问题的拉格朗日松弛算法

为得到最接近原问题最优解的下界，拉格朗日乘子λk取值越大越好。根据性质4，拉格朗日乘子λk满足，故本算法中拉格朗日乘子初始值λ0取为。因为C(TC)≤ν(CEPAC) ≤C(Tw)，原问题最优解的上界初始值UB取为C(Tw)，Tuk=Tw，下界初始值LB取为C(TC)，Tlk=TC。在每一次拉格朗日迭代中，对任意的弧e∈A，取a=λk，b= 1，构造sλk(e) =λkw(e) +C(e)。置。用Chu-Liu/Edmonds求出关于长度权重sλk最小的支撑树形图Tsλk。根据性质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，则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且C(Tsλk)≥C(Tlk)时，置LB=C(Tsλk)，Tsλk，Tuk+1=Tuk。最后置k=k+ 1，置。重复上述过程。当S(Tsλk)的值几乎接近S(Tuk)的值时算法停止，即对于任意小正数ε，有成立时，算法停止，此时找到原问题的一个近似解Tuk+1。

综合以上分析，设计详细的算法步骤如下：

算法：拉格朗日松弛算法

输入：有向图G=(V,A:w,c,p)，两个正数W，D，任意小的正数ε。

输出：近似解Tuk+1。

第1 步：对任意的弧e∈A，置扩容费用C(e) =d*(e)c(e)。构造新图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 算法求出关于扩容费用C最小的支撑树形图TC，计算出w(TC)的值。假如w(TC)≤W，则TC为CEPAC 问题的最优解，算法停止；否则置Tlk=TC，LB=C(Tlk)。

第3 步：在新图G'中用Chu-Liu/Edmonds 算法求出关于长度权重w最小的支撑树形图Tw，计算出w(Tw)的值。假如w(Tw)＞W，则CEPAC 问题无可行解，算法停止；否则置Tuk=Tw，UB=C(Tuk)，。

第4 步：对任意的弧e∈A，构造系数sλk(e) =λkw(e) +C(e)（即a=λk，b= 1），置。

第5 步：在新图G'中用Chu-Liu/Edmonds 求出关于系数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且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，，转第4步。

定理1 若CEPAC 问题存在可行解，则拉格朗日松弛算法一定能求出CEPAC 问题的一个近似解，且拉格朗日松弛算法的间复杂度为O(kmn)（假设算法第4步至第5步最多循环k次）。

证明：若CEPAC 问题不存在可行解，则根据拉格朗日松弛算法第3 步，有w(Tw)＞W成立，算法停止。

若CEPAC 问题存在可行解，则根据拉格朗日松弛算法第3 步，置Tuk=Tw，UB=C(Tuk)，。根据算法第4步，构造系数sλ0(e) =λ0w(e) +C(e)，计算的值。根据算法第5 步，在新图G'中用Chu-Liu/Edmonds 算法求出关于长度权重sλ0最小的支撑树形图Tsλ0，根据性质3，C(Tsλ0)要么是ν(CEPAC)的上界，要么是ν(CEPAC)的下界，此时更新上界UB或LB的值。根据算法第6步，假如|S(Tu0)-S(Tsλ0) |≤ε，则支撑树形图Tu1为CEPAC问题的一个近似解，输出近似解Tu1，算法停止；否则置k=k+ 1，，重复循环算法第4 步至第6步，一定存在一个正整数k，使得算法第4 步至第6 步循环k次后出现UB和LB几乎相等的情况，此时有|S(Tuk)-S(Tsλk) |≤ε成立，此时得到近似解Tuk+1。

本文设计的拉格朗日松弛算法的第1 步构造新图，能在线性时间内完成；第2 步的时间复杂度主要取决于利用Chu-Liu/Edmonds 算法求出关于扩容费用C最小的支撑树形图TC的复杂度，其复杂度为O(mn)；第3步的时间复杂度主要取决于利用Chu-Liu/Edmonds 算法求出关于扩容权重w最小支撑树形图Tw的复杂度，其复杂度为O(mn)；算法第4步的复杂度主要取决于构造系数sλ0(e) =λ0w(e) +C(e)的计算量，其复杂度为O(m)；第5步的时间复杂度主要取决于利用Chu-Liu/Edmonds算法求出关于系数sλk最小的支撑树形图Tsλk的复杂度，其复杂度为O(mn)；第6步能在线性时间内完成；假设算法第4 步至第6 步最多循环k次，则拉格朗日松弛算法总的时间复杂度为O(kmn)。

4 实例

已知有向网络G=(V,A:w,c,p)如图1 所示，图中每条弧上的数字依次为长度权重、容量、单位扩容费用。设点s为根节点，d= 5，W= 18。

图1 有向网络中树形图扩容问题实例

根据拉格朗日松弛算法第1步，构造新图G'=(V,A:w,C,18)，如图2所示。取k= 0。

图2 构造新图G'

根据算法第2 步，求出以点s为根的关于扩容费用C最小的支撑树形图TC，A(TC)={sv4,v4v3,v3v5,v3v2,v2v1}。计算出w(TC)= 19 ＞18。置Tl0=TC，LB=C(Tl0)= 3。

根据算法第3 步，求出以点s为根的长度权重w最小的支撑树形图Tw，A(Tw)={sv2,v2v1,sv5,sv4,v4v3}。计 算 出w(Tw)= 13 ＜18。置Tu0=Tw，UB=C(Tu0)= 10，。根据算法第4 步，对任意的弧e∈A，构造系数sλ0(e)=λ0w(e) +C(e)，置。根据算法第5 步，在新图G'中求出以点s为根的关于系数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。根据算法第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 步循环3 次就得到近似解Tu3。当问题规模比较大，计算时间是一个问题时，我们的拉格朗日算法可以快速地获得一个近似解。

5 总结

本文对一类带约束的支撑树形图容量扩张问题（CEPAC）展开研究。对任意的弧e∈A，我们构造新的系数s(e) =aw(e) +bC(e)，其中a，b为非负的常数。不考虑长度权重限制的条件，在图G中找出关于系数s最小的支撑树形图Ts，并得出C(Ts)是CEPAC问题的一个更佳的上界或下界、拉格朗日乘子λk满足等结论。最后把上述结论应用在CEPAC 问题的拉格朗日算法设计中，该算法能求出原问题的一个近似解。

本文得出的结论以及提出的算法同样适用于其他类型的双权重限制性支撑树问题。