有限资源下最大可靠性网络流中断模型

赵 佳，于 华

(中国科学院大学工程管理与信息技术学院，北京100049）

1 前言

网络流中断问题是一类经典的网络流优化问题，对此类问题的相关研究起源于19世纪60年代[1，2]。此问题可以视为Stackelberg[3]博弈的特殊情况，模型中有两个局中人分别成为中断者和入侵者，中断者先选择中断策略抵御入侵者，中断策略一般为在某些边上设置中断点或者监测装置，其目的是在有限资源下尽可能减少入侵者带来的伤害。Steinrauf等[4]利用网络流中断模型研究了在城市之间如何设置关卡来防止毒品进入一些大城市。Wood[5]证明了此问题属于NP-完全（non-deterministic polynomial completeness）问题，之后的研究大多从启发式算法的角度解决此问题[6～9]。Wood[5]又将网络流中断问题化为整数规划问题并给出了两个有效的不等式来缩小解空间。事实上，CPLEX是IBM(International Business Machines Corporation)研发的一款可以求解整数规划问题的软件，可以解决较大规模的整数规划问题。而在实际应用中，入侵者突破已设置中断点的情况也很常见，这促使目前对网络流中断问题的研究加入了随机性，即中断者在边上设置中断点时需要考虑对此边中断不一定成功。Cormican等[10]提出了随机网络流中断模型并设计了相应的近似算法。Berry等[11]将随机网络流中断模型应用于市区水网的检测问题中，在其研究中将检测器放置在管道中，检测器通过水的特征（如水温、氯含量、颜色、传导性和pH等）来检测水中是否有毒，这种检测手段不是100%正确的。随着“9.11事件”的发生此类模型有了新的应用方向，比如国土安全（homeland security）[12]、关键设施和关键资源(critical infrastructure and key resources，CIKR)[13]以及其他涉及恐怖袭击事件的领域。Morton等[14]从国土安全的角度将网络流中断问题用于核走私的研究中，文中通过在可能的运输路径上设置放射检测器来最小化走私者走私成功的概率。结合关键设施保护的应用，Scaparra等[15]以网络流中断问题为基础建立了双层整数规划模型并给出了隐含枚举(implicit enumeration)算法，此算法实际上和枚举算法相差甚少。事实上，大部分中断问题都可以转化为双层整数规划问题[15，16]。目前对于双层整数规划问题的研究没有实质性的突破。双层整数规划问题的难度一般取决于下层规划问题，下层规划问题如果是线性规划问题则此双层整数规划问题可很容易转化成整数规划问题，进而可用CPLEX来解决；下层规划问题如果是线性整数规划问题通常只能采用遍历手段。

考虑到监测点可能失效的情况，本文在网络流中断模型的基础上加入了可靠策略的概念，此概念是指即使某些监测点失效仍然能够达到原有的目的。本文的模型是在给定资源情况下，通过在起点到终点的所有路径设置一定数量的监测点来更好抵御入侵者，这与随机网络流中断模型中将所有监测点设置为相等的成功监测概率相同。事实上可靠性的思想是必要的，假设一个监测点能够成功监测异常情况的概率是80%（这在很多应用尤其是国土安全等领域是不理想的），则这一异常情况能够被两个监测点监测出的概率为1-（1-80%）2=96%；而被三个监测点监测出的概率为1-（1-80%）3=99.2%。我们的模型是在有限的资源下，选择一些边设置监测点使得从起点到终点的所有路径包含尽可能多的已被监测的边，即最大化所有路径包含已监测边数量的最小值。此研究不仅可直接应用于一些其他的网络中断模型中，如边境防御、CIKR、水资源监测等，同时也提供了一种解决双层整数规划模型的方法。

2 模型

G(N，D，s，t，a，R)表示以N为顶点集，D为边集，s为起点，t为终点的有向图，其中函数a:D→R+表示在边(i，j)∈D上设置监测点所需的花费aij，R表示中断者的资源限制。此模型是指在给定资源限制R下，即使入侵者能够通过中断者在某些边上所设置的监测点，仍然不能从起点s到达终点t，即最大化从s到t的所有路径中包含监测点的边的数量的最小值。模型有下面的线性整数规划形式：

式（1）中，ρ为所有从s到t的路径；xij=1表示在边(i，j)上设置监测点，否则xij=0。

一般来说，即使图的规模不大，两点之间所有路径的数量也非常大，从计算复杂性角度来说，两点之间所有路径的数量是图的规模的指数次幂。为此将PATH模型转化为下面的双层整数规划模型：

式(2)中，f为给定任意可行xij后如下规划问题的最优目标函数值：

式（3）中，xij表示的意义与在PATH模型中相同，边(t，s)是终点t到起点s的虚拟边；fts为虚拟边(t，s)上的虚拟流量；fij为边(i，j)上的流量；tij=1为入侵者会破坏边(i，j)上所设置的监测点，否则tij=0。

在给出两个模型等价性的证明之前，需要对资源R给出一些限制。显然，若资源R不能够使得在s到t的每条路径中至少含有一个带有监测点的边，即PATH模型的最优值为0，则BIP模型的下层规划问题无可行解。笔者指出这一临界值是很容易判断的。

命题1.令G(N，D，a)是 图G(N,D)中 边(i，j)∈D的容量限制为aij的 网 络 图 ，R1是G(N，D，a)的最大流。则opt(PATH)≥1当且仅当R≥R1，其中opt(PATH)是模型PATH的最优目标函数值。

证明：由于R1是G(N，D，a)的最大流值，根据最大流最小割定理，R1也是G(N，D，a)的最小割量。令x是G(N，D，a)的最小割，即从s到t的所有路径都包含x中的至少一条边，显然(x，1)是模型PATH的最优解。故当R≥R1时必有opt(PATH)≥1，反之亦成立。

综合可得，若R≤R1，模型PATH无可行解；若R=R1，opt(PATH)=1。下文如无特别说明，约定R≥R1。

命题2.模型BIP等价于模型PATH，也即在相同的图中，对于相同的参数R，他们有相同的目标函数值。

证明：令(x，k)是模型PATH的可行解，需证明(f，x，k)也是模型BIP的可行解，其中f=0，仅需证明模型BIP的上层规划问题中f≤0成立。若其不成立，由于tij是0-1变量，则存在一条从s到t的路P*，对于所有其上的边都有tij=xij，但∑(i，j)∈Dtij≤k-1 与∑(i，j)∈P*xij≥k矛盾。

反之令(f，x，k)是模型BIP的可行解，其中f=0。由于在上层规划约束中f≤0，则不存在任何从s到t的路，由于∑(i，j)∈Dtij≤k-1可知在任意s到t的路P*中必有∑(i，j)∈P*xij≥k，从而可得 (x，k)也是模型PATH的可行解。

下面仅需解决模型BIP，如在前言中所示，其下层规划是整数规划，这在一般情况下是无法将双层整数规划模型转化为整数规划模型的，故此需要一些转化手段。

3 模型求解

由于双层整数规划模型的难点在于下层规划，为解决模型BIP，首先从下层规划的讨论开始。

3.1 线性规划松弛

一个常用的处理整数规划方法就是求解其线性规划松弛。由于在上层规划中xij=0，1并且在下层规划中tij≤xij，我们将用tij≥0来代替tij=0，1。由此得到如下的下行规划形式：

引理1.opt(IP)∈{0,1}

证明：由于fts≤1，将图G(N，D)的每条边加上流量限制1不会对模型IP的最优解产生变化。因此如果有一条从s到t的路流量不为0，则可令这条路上的所有边的流量为1，其余边的流量为0即可得到流值为1的最优解。否则显然有opt(IP)=0。

命题3.设(f，x，k)是模型BIP的最优解，则至少存在一条从s到t的路P0满足

证明：若(f，x，k)是模型BIP的最优解，由命题2可知，(x，k)是模型PATH的最优解，也即k是模型PATH的最优目标函数值。若对任意从s到t的路P*都有，则 (x，k+1)是模型 PATH的可行解，这与PATH的最优目标函数值是k相矛盾。

根据引理1和命题3，我们有如下关于模型IP和模型LP最优值的相关关系式：

定理1.

其中opt(IP)是模型IP的最优值，opt(LP)是模型LP的最优值。

证明：“⇐”由opt(IP)≤opt(LP)以及定理1可直接得到。

由命题3可知，存在一条从s到t的路P0满足模型LP的对偶有如下形式：

首先构造模型LP的可行解。令

则：

模型LP中的其余约束条件容易检验，且此可行解对应的目标函数值为

构造模型DLP的可行解如下，设

令G(N，D，β)是图G(N,D)中边 (i，j)∈D的容量限制为βij的网络图，αi是图G(N，D，β)中从s到i的最短路长度。则对于所有的i∈P0，P0中从s到i的路一定是图G(N，D，β)中从s到i的最短路并且αt=1。否则设P1是P0中从s到i的路，P0=P1+P2且P3是图G(N，D，β)中从s到i的最短路。则P3+P2是图G(N，D，β)中从s到t的路且αt＜1，由此可知∑(i,j)∈P3+P2xij＜k，这与x的可行性矛盾。

有：

1）若(i，j)∈D且i，j∈P0，αi-αj+βij=0 ；

2）若 (i，j)∈D且i∈P0，j∉P0，

3）若 (i，j)∈D且i∉P0，j∈P0，

其中⇒*是由于若βij=0，则必有αi≥αj

4）若 (i，j)∈D且i∉P0，j∉P0，模型DLP中的其余约束条件可容易检验，且此可行解对应的目标函数值为由对偶定理可知，所构造的模型LP和模型DLP的可行解都是最优解，且最优目标函数值为

接下来可用对偶方法来处理模型LP。

3.2 线性规划对偶

在定理1的证明中分别构造了模型LP和模型DLP的最优解，由此可直接得到如下推论：

对任意模型 BIP的可行解 (f，x，k)，若opt(IP)=0，则存在一个模型DLP的最优解(α，β，βts，a，γ) 满 足 ：对任意的(i，j)∈D成立。

由定理1可知，模型BIP的上层规划中的约束f≤0等价于opt(DLP)=(k-1)/k，则由推论可知，f≤0等价于如下的不等式组有可行解：

由于当用(IE1)代替上层规划中的约束f≤0时x和β都是变量，此时(IE1)中的第一个不等式就是未知量的二次形式，需将其转化成一次形式。

3.3 模型线性化

用θij代替 (1-xij)βij，并且对于任意 (i，j)∈D加入如下不等式组：

得到：

定理2.如果IE1有可行解，则IE2也有可行解，反之亦然。

证明：令 (α*，βts*，β*)是 IE1的可行解，对任意(i，j)∈D令θij=(1-xij)βij，则 (α*，βts*，β*，θ*)是 IE2的可行解。

反之，令 (α*，βts*，β*，θ*)是 IE2 的可行解，对任意(i，j)∈D有：

则

因此 (α*，βts*，β*)是 IE1的可行解。

令ε=1/k，综合以上结论，得到与模型BIP等价的如下混合整数规划模型：

MIP可由CPLEX软件解得，完成了从含有图G(N，D)的规模的指数次幂数量级个约束的模型PATH到仅含有与图G(N，D)的规模同阶数量级个约束的模型MIP的转化。即：

定理3.对于给定的图G(N，D)，constraint(MIP)=O( ||D)

其中 ||D表示D中元素个数，constraint(MIP)表示模型M中约束个数。

4 模型扩展

本节讨论可靠网络中断模型的两个不同形式。

4.1 中断点

在以上的讨论中限制了仅能对边设置监测点，本小节考虑在顶点设置监测点的情况。此种情况仅需将每个顶点i∈N换成两个顶点i1和i2，并加上边(i1，i2)，并且所有在原图G(N，D)中进入顶点i的边全部进入顶点i1，所有在原图G(N，D)中离开顶点i的边全部离开i2。在新构造的图中用前述的转换方法可完成模型约束的简化。

4.2 多个起点和多个终点

此时仅需设置一个超级起点和超级终点，并将超级起点连接所有原有起点，将所有原有终点连接超级终点，并将在新建的所有边上的中断费用设置足够大即可。

5 结语

本文考虑了一种新的网络中断模型，鉴于此模型约束条件的复杂性，利用线性规划理论及其他工具对此模型的约束条件进行了极大的简化。在理论上说提供了一个解决双层整数规划模型的方法，从应用上说此模型可直接用于边境控制、国土防御以及水资源监测等领域，具有一定的理论和应用价值。

[1]Wollmer R.Removing arcs from a network[J].Operations Research,1964,12(6):934-940.

[2]Durbin E.An interdiction model of highway transportation[R].RM-4945-PR,RAND Research Memorandum,1966.

[3]Simaan M,Cruz Jr J B.On the Stackelberg strategy in nonzerosum games[J].Journal of Optimization Theory and Applications,1973,11(5):533-555.

[4]Steinrauf R L.Network interdiction models[R].Naval Postgraduate School Monterey CA,1991.

[5]Wood R K.Deterministic network interdiction[J].Mathematical and Computer Modelling,1993,17(2):1-18.

[6]Benders J F.Partitioning procedures for solving mixed-variables programming problems[J].Numerische mathematik,1962,4(1):238-252.

[7]Wagner D K.Disjoint(s,t)cuts in a network[J].Networks,1990,20(4):361-371.

[8]Barnhart C,Johnson E L,Nemhauser G L,et al.Branch-andprice:Column generation for solving huge integer programs[J].Operations Research,1998,46(3):316-329.

[9]Lim C,Smith J C.Algorithms for discrete and continuous multicommodity flow network interdiction problems[J].IIE Transactions,2007,39(1):15-26.

[10]Cormican K J,Morton D P,Wood R K.Stochastic network interdiction[J].Operations Research,1998,46(2):184-197.

[11]Berry J W,Fleischer L,Hart W E,et al.Sensor placement in municipal water networks[J].Journal of Water Resources Planning and Management,2005,131(3):237-243.

[12]KettlDF.contingentcoordinationpracticalandtheoreticalpuzzlesfor homeland security[J].The American Review of Public Administration,2003,33(3):253-277.

[13]Brown G,Carlyle M,Salmerón J,et al.Defending critical infrastructure[J].Interfaces,2006,36(6):530-544.

[14]Morton D P,Pan F,Saeger K J.Models for nuclear smuggling interdiction[J].IIE Transactions,2007,39(1):3-14.

[15]Scaparra M P,Church R L.A bilevel mixed-integer program for critical infrastructure protection planning[J].Computers&Operations Research,2008,35(6):1905-1923.

[16]Royset J O,Wood R K.Solving the bi-objective maximum-flow