有限資源下最大可靠性網(wǎng)絡流中斷模型

趙 佳，于 華

(中國科學院大學工程管理與信息技術學院，北京100049）

1 前言

網(wǎng)絡流中斷問題是一類經(jīng)典的網(wǎng)絡流優(yōu)化問題，對此類問題的相關研究起源于19世紀60年代[1，2]。此問題可以視為Stackelberg[3]博弈的特殊情況，模型中有兩個局中人分別成為中斷者和入侵者，中斷者先選擇中斷策略抵御入侵者，中斷策略一般為在某些邊上設置中斷點或者監(jiān)測裝置，其目的是在有限資源下盡可能減少入侵者帶來的傷害。Steinrauf等[4]利用網(wǎng)絡流中斷模型研究了在城市之間如何設置關卡來防止毒品進入一些大城市。Wood[5]證明了此問題屬于NP-完全（non-deterministic polynomial completeness）問題，之后的研究大多從啟發(fā)式算法的角度解決此問題[6～9]。Wood[5]又將網(wǎng)絡流中斷問題化為整數(shù)規(guī)劃問題并給出了兩個有效的不等式來縮小解空間。事實上，CPLEX是IBM(International Business Machines Corporation)研發(fā)的一款可以求解整數(shù)規(guī)劃問題的軟件，可以解決較大規(guī)模的整數(shù)規(guī)劃問題。而在實際應用中，入侵者突破已設置中斷點的情況也很常見，這促使目前對網(wǎng)絡流中斷問題的研究加入了隨機性，即中斷者在邊上設置中斷點時需要考慮對此邊中斷不一定成功。Cormican等[10]提出了隨機網(wǎng)絡流中斷模型并設計了相應的近似算法。Berry等[11]將隨機網(wǎng)絡流中斷模型應用于市區(qū)水網(wǎng)的檢測問題中，在其研究中將檢測器放置在管道中，檢測器通過水的特征（如水溫、氯含量、顏色、傳導性和pH等）來檢測水中是否有毒，這種檢測手段不是100%正確的。隨著“9.11事件”的發(fā)生此類模型有了新的應用方向，比如國土安全（homeland security）[12]、關鍵設施和關鍵資源(critical infrastructure and key resources，CIKR)[13]以及其他涉及恐怖襲擊事件的領域。Morton等[14]從國土安全的角度將網(wǎng)絡流中斷問題用于核走私的研究中，文中通過在可能的運輸路徑上設置放射檢測器來最小化走私者走私成功的概率。結合關鍵設施保護的應用，Scaparra等[15]以網(wǎng)絡流中斷問題為基礎建立了雙層整數(shù)規(guī)劃模型并給出了隱含枚舉(implicit enumeration)算法，此算法實際上和枚舉算法相差甚少。事實上，大部分中斷問題都可以轉化為雙層整數(shù)規(guī)劃問題[15，16]。目前對于雙層整數(shù)規(guī)劃問題的研究沒有實質(zhì)性的突破。雙層整數(shù)規(guī)劃問題的難度一般取決于下層規(guī)劃問題，下層規(guī)劃問題如果是線性規(guī)劃問題則此雙層整數(shù)規(guī)劃問題可很容易轉化成整數(shù)規(guī)劃問題，進而可用CPLEX來解決；下層規(guī)劃問題如果是線性整數(shù)規(guī)劃問題通常只能采用遍歷手段。

考慮到監(jiān)測點可能失效的情況，本文在網(wǎng)絡流中斷模型的基礎上加入了可靠策略的概念，此概念是指即使某些監(jiān)測點失效仍然能夠達到原有的目的。本文的模型是在給定資源情況下，通過在起點到終點的所有路徑設置一定數(shù)量的監(jiān)測點來更好抵御入侵者，這與隨機網(wǎng)絡流中斷模型中將所有監(jiān)測點設置為相等的成功監(jiān)測概率相同。事實上可靠性的思想是必要的，假設一個監(jiān)測點能夠成功監(jiān)測異常情況的概率是80%（這在很多應用尤其是國土安全等領域是不理想的），則這一異常情況能夠被兩個監(jiān)測點監(jiān)測出的概率為1-（1-80%）2=96%；而被三個監(jiān)測點監(jiān)測出的概率為1-（1-80%）3=99.2%。我們的模型是在有限的資源下，選擇一些邊設置監(jiān)測點使得從起點到終點的所有路徑包含盡可能多的已被監(jiān)測的邊，即最大化所有路徑包含已監(jiān)測邊數(shù)量的最小值。此研究不僅可直接應用于一些其他的網(wǎng)絡中斷模型中，如邊境防御、CIKR、水資源監(jiān)測等，同時也提供了一種解決雙層整數(shù)規(guī)劃模型的方法。

2 模型

G(N，D，s，t，a，R)表示以N為頂點集，D為邊集，s為起點，t為終點的有向圖，其中函數(shù)a:D→R+表示在邊(i，j)∈D上設置監(jiān)測點所需的花費aij，R表示中斷者的資源限制。此模型是指在給定資源限制R下，即使入侵者能夠通過中斷者在某些邊上所設置的監(jiān)測點，仍然不能從起點s到達終點t，即最大化從s到t的所有路徑中包含監(jiān)測點的邊的數(shù)量的最小值。模型有下面的線性整數(shù)規(guī)劃形式：

式（1）中，ρ為所有從s到t的路徑；xij=1表示在邊(i，j)上設置監(jiān)測點，否則xij=0。

一般來說，即使圖的規(guī)模不大，兩點之間所有路徑的數(shù)量也非常大，從計算復雜性角度來說，兩點之間所有路徑的數(shù)量是圖的規(guī)模的指數(shù)次冪。為此將PATH模型轉化為下面的雙層整數(shù)規(guī)劃模型：

式(2)中，f為給定任意可行xij后如下規(guī)劃問題的最優(yōu)目標函數(shù)值：

式（3）中，xij表示的意義與在PATH模型中相同，邊(t，s)是終點t到起點s的虛擬邊；fts為虛擬邊(t，s)上的虛擬流量；fij為邊(i，j)上的流量；tij=1為入侵者會破壞邊(i，j)上所設置的監(jiān)測點，否則tij=0。

在給出兩個模型等價性的證明之前，需要對資源R給出一些限制。顯然，若資源R不能夠使得在s到t的每條路徑中至少含有一個帶有監(jiān)測點的邊，即PATH模型的最優(yōu)值為0，則BIP模型的下層規(guī)劃問題無可行解。筆者指出這一臨界值是很容易判斷的。

命題1.令G(N，D，a)是 圖G(N,D)中 邊(i，j)∈D的容量限制為aij的 網(wǎng) 絡 圖 ，R1是G(N，D，a)的最大流。則opt(PATH)≥1當且僅當R≥R1，其中opt(PATH)是模型PATH的最優(yōu)目標函數(shù)值。

證明：由于R1是G(N，D，a)的最大流值，根據(jù)最大流最小割定理，R1也是G(N，D，a)的最小割量。令x是G(N，D，a)的最小割，即從s到t的所有路徑都包含x中的至少一條邊，顯然(x，1)是模型PATH的最優(yōu)解。故當R≥R1時必有opt(PATH)≥1，反之亦成立。

綜合可得，若R≤R1，模型PATH無可行解；若R=R1，opt(PATH)=1。下文如無特別說明，約定R≥R1。

命題2.模型BIP等價于模型PATH，也即在相同的圖中，對于相同的參數(shù)R，他們有相同的目標函數(shù)值。

證明：令(x，k)是模型PATH的可行解，需證明(f，x，k)也是模型BIP的可行解，其中f=0，僅需證明模型BIP的上層規(guī)劃問題中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。由于在上層規(guī)劃約束中f≤0，則不存在任何從s到t的路，由于∑(i，j)∈Dtij≤k-1可知在任意s到t的路P*中必有∑(i，j)∈P*xij≥k，從而可得 (x，k)也是模型PATH的可行解。

下面僅需解決模型BIP，如在前言中所示，其下層規(guī)劃是整數(shù)規(guī)劃，這在一般情況下是無法將雙層整數(shù)規(guī)劃模型轉化為整數(shù)規(guī)劃模型的，故此需要一些轉化手段。

3 模型求解

由于雙層整數(shù)規(guī)劃模型的難點在于下層規(guī)劃，為解決模型BIP，首先從下層規(guī)劃的討論開始。

3.1 線性規(guī)劃松弛

一個常用的處理整數(shù)規(guī)劃方法就是求解其線性規(guī)劃松弛。由于在上層規(guī)劃中xij=0，1并且在下層規(guī)劃中tij≤xij，我們將用tij≥0來代替tij=0，1。由此得到如下的下行規(guī)劃形式：

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

證明：由于fts≤1，將圖G(N，D)的每條邊加上流量限制1不會對模型IP的最優(yōu)解產(chǎn)生變化。因此如果有一條從s到t的路流量不為0，則可令這條路上的所有邊的流量為1，其余邊的流量為0即可得到流值為1的最優(yōu)解。否則顯然有opt(IP)=0。

命題3.設(f，x，k)是模型BIP的最優(yōu)解，則至少存在一條從s到t的路P0滿足

證明：若(f，x，k)是模型BIP的最優(yōu)解，由命題2可知，(x，k)是模型PATH的最優(yōu)解，也即k是模型PATH的最優(yōu)目標函數(shù)值。若對任意從s到t的路P*都有，則 (x，k+1)是模型 PATH的可行解，這與PATH的最優(yōu)目標函數(shù)值是k相矛盾。

根據(jù)引理1和命題3，我們有如下關于模型IP和模型LP最優(yōu)值的相關關系式：

定理1.

其中opt(IP)是模型IP的最優(yōu)值，opt(LP)是模型LP的最優(yōu)值。

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

由命題3可知，存在一條從s到t的路P0滿足模型LP的對偶有如下形式：

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

則：

模型LP中的其余約束條件容易檢驗，且此可行解對應的目標函數(shù)值為

構造模型DLP的可行解如下，設

令G(N，D，β)是圖G(N,D)中邊 (i，j)∈D的容量限制為βij的網(wǎng)絡圖，α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中的其余約束條件可容易檢驗，且此可行解對應的目標函數(shù)值為由對偶定理可知，所構造的模型LP和模型DLP的可行解都是最優(yōu)解，且最優(yōu)目標函數(shù)值為

接下來可用對偶方法來處理模型LP。

3.2 線性規(guī)劃對偶

在定理1的證明中分別構造了模型LP和模型DLP的最優(yōu)解，由此可直接得到如下推論：

對任意模型 BIP的可行解 (f，x，k)，若opt(IP)=0，則存在一個模型DLP的最優(yōu)解(α，β，βts，a，γ) 滿 足 ：對任意的(i，j)∈D成立。

由定理1可知，模型BIP的上層規(guī)劃中的約束f≤0等價于opt(DLP)=(k-1)/k，則由推論可知，f≤0等價于如下的不等式組有可行解：

由于當用(IE1)代替上層規(guī)劃中的約束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等價的如下混合整數(shù)規(guī)劃模型：

MIP可由CPLEX軟件解得，完成了從含有圖G(N，D)的規(guī)模的指數(shù)次冪數(shù)量級個約束的模型PATH到僅含有與圖G(N，D)的規(guī)模同階數(shù)量級個約束的模型MIP的轉化。即：

定理3.對于給定的圖G(N，D)，constraint(MIP)=O( ||D)

其中 ||D表示D中元素個數(shù)，constraint(MIP)表示模型M中約束個數(shù)。

4 模型擴展

本節(jié)討論可靠網(wǎng)絡中斷模型的兩個不同形式。

4.1 中斷點

在以上的討論中限制了僅能對邊設置監(jiān)測點，本小節(jié)考慮在頂點設置監(jiān)測點的情況。此種情況僅需將每個頂點i∈N換成兩個頂點i1和i2，并加上邊(i1，i2)，并且所有在原圖G(N，D)中進入頂點i的邊全部進入頂點i1，所有在原圖G(N，D)中離開頂點i的邊全部離開i2。在新構造的圖中用前述的轉換方法可完成模型約束的簡化。

4.2 多個起點和多個終點

此時僅需設置一個超級起點和超級終點，并將超級起點連接所有原有起點，將所有原有終點連接超級終點，并將在新建的所有邊上的中斷費用設置足夠大即可。

5 結語

本文考慮了一種新的網(wǎng)絡中斷模型，鑒于此模型約束條件的復雜性，利用線性規(guī)劃理論及其他工具對此模型的約束條件進行了極大的簡化。在理論上說提供了一個解決雙層整數(shù)規(guī)劃模型的方法，從應用上說此模型可直接用于邊境控制、國土防御以及水資源監(jiān)測等領域，具有一定的理論和應用價值。

[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