本章中，系統(tǒng)地介紹一批與通信和計算機網(wǎng)絡(luò)的正常設(shè)計相關(guān)的基礎(chǔ)網(wǎng)絡(luò)設(shè)計問題（NDPs。我們這里所說的正常（有時也被稱為“標稱”或常規(guī)）網(wǎng)絡(luò)設(shè)計，意味著在設(shè)計時僅考慮網(wǎng)絡(luò)的一個狀態(tài)，即正常（）運行狀態(tài)。此時，需求是典“平均“）需求，所有資源完全可用。簡單地說，給定需求，我們要確定需要多少資源容量，及如何在一組路由/流量約束條件下，經(jīng)濟地分發(fā)這些需求。這就是通常所說的無容量限制的設(shè)計。通常情況下，它發(fā)生在中長期網(wǎng)絡(luò)規(guī)劃中。一旦網(wǎng)絡(luò)中的容量是已知的（網(wǎng)絡(luò)已安裝好，需求量給出，則問題變?yōu)槿绾螌⒘鞣峙湓诓煌穆窂缴希詢?yōu)化給定的網(wǎng)絡(luò)目標（如，最低成本路由或最大總收入。即使沒有任何額外的目標，我們?nèi)匀涣髁糠峙涞目尚行詥栴}。通常，這種分配（和/或最小成本路由）問題被稱為容量受限的問題。在短期或近期網(wǎng)絡(luò)設(shè)計時，容量不能被添加到網(wǎng)絡(luò)中，這種問題會被遇到。這些問題大多數(shù)可以被描述為鏈路路徑或節(jié)點鏈路多商品流問題；我們在第2章和第3章中已經(jīng)看到了這些類型問題的一些例子。通過章的學(xué)，解釋一描/模型在哪里以及如何優(yōu)于其他描述/模型。此外，展示路由限制、鏈路容量模塊化、非線性成本函數(shù)、以及其他方面的限制在何處出現(xiàn)、如何出現(xiàn)、以及如何處理它們。讀者很快就會明白，即使對于正常設(shè)計情況，各種可能的、重要的NDP數(shù)量也非常大，并且，同樣重要的，說明建立模型的基本規(guī)則。這些將幫助讀者在需要的時候，解決自己的問題。在第9章看到，當(dāng)在設(shè)計過程中考慮狀態(tài)時，NDP會變得更加和復(fù)雜。這種狀態(tài)包括：某些鏈路和/或節(jié)點全部或部分失敗、需求變化。在這種情況下，設(shè)計網(wǎng)絡(luò)，在失敗和/或需求變化下保持魯棒，非常。在隨后的章節(jié)中，本章將介紹的基本設(shè)計問題將被擴展，用于設(shè)計彈性（穩(wěn)?。┚W(wǎng)絡(luò)（第三部分）和其他類型常規(guī)設(shè)計問題（第二部分。基本無容量限制及容量受限我們從相對簡單、眾所周知的模型開始介紹。你會注意到，在模型中，我們清楚地對一些指數(shù)和常量未明確列出。此外，除非明確地，否則，如果一種類型的流量/容量變量沒有被指定，則它被認為是連續(xù)和非負的。此外，正如你將會看到的，在某些模型中，為了使模型更容易被理解，我們會使用冗余變量和約束條件。最后，我們還可以注意到，這一節(jié)中的所有模型都可以被定義為線性規(guī)劃（P）問題?；叵胍幌?.4節(jié)中四節(jié)點網(wǎng)絡(luò)的鏈路路徑模型。它是一個簡單無容量限制NDP問（2.4.11）?，F(xiàn)在，我們給出這個（很基本的）問題的一般指d=1,2D:p=1,2,Pd:流量需求de=12,E:常δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:需求dξee的單元（邊際）xdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負ye:e容量（連續(xù)非負目∑minimizeF eξeye（帶寬成本（4.1.1a）∑p

= （4.1.1b）∑ p

≤ （4.1.1c）e在這x=(mathbfx1,mathbfx2,...,mathbfxD)其中mathbfxd=(xd1,xd2,...,xdPd),d=1,2,D（4.1.1c）y(x)=d∑pδedpxdpe為鏈路負載。它是連續(xù)的。而（4.1.1）是一個線性規(guī)劃（P）問題（第 5.1 節(jié)。顯然DSDP的最優(yōu)解受到（4.1.1c）的約束。因此，在最優(yōu)解下，鏈路負載應(yīng)正好等于鏈路容量（否則，會有鏈路容量空閑，我們還需要為它們，這是不合理的。我們特意在這里使用不等式容量約束，這樣它就與后面將要被考慮的其他（非線性）模型一致。以上D/SDP鏈路路徑模型需要∑dd=ˉ×D路徑流變量xp中ˉ是每個需求的候選路徑的平均數(shù)，EDE個約束（不包括標準的我們想提醒你注意上面模型的頭兩行包括名約定，它們被用于DSDP問題以及這本書中以后的所有問題。在第一行的左邊，首先是問題的類型被指定（LP-線性規(guī)劃，隨后是問題（DSDP）的首字母縮寫。本書將使用這種縮寫來指代不同的問題。在D代表“規(guī)模（Dimenionng（SDP）的縮寫。然后，第二行給出了該縮寫的全稱。在第一行的右邊給出了模型的類型（在本例中為鏈路路徑模型把需求d的所有流量hd分配到它的最短路徑上。這個方法被稱為最短路徑分配規(guī)則（2.4.13）。為了更細致地研究這個問題，我們用鏈路e的負載，即方程（4.1.1c）的左側(cè)，（.1）eF=∑eξe∑d∑pδedpxdp

∑d∑pxdp∑eξeδedp

∑d∑pe這里，ζdp=e

ξeδedp是需求d的路徑p的長度（成本。因此，D/SDP問題LP:D/SDP/DLPF鏈路路徑模SDP-解耦的鏈路路徑模型xdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負∑minimizeF pζdpxdp（帶寬成本∑pxdp= d=1,2,...D/SDP/DlPFD/SDP問題的解耦版本。事實上，這是一組相互獨立的最小化問題，每一個問題針對一個特定的需求d，具有下面的形式：∑minimizeF psubjectto∑pxdp= xdp≥這個自然的解耦是目標函數(shù)（4.1.3a）的線性結(jié)構(gòu)帶來的。從（4.1.4）很容易看到，最優(yōu)解只給候選路徑集（路由或路由表）中的最短路徑分配流，并且，當(dāng)一個需求d有一個以上最短路徑的情況下，hd可以任意拆分給各最短路徑。鏈路路徑模型（4.1.1）對無向和有向圖都有效。它需要使用預(yù)定義的一套候選路徑集作為輸入（回想一下第2章的內(nèi)容；這樣的候選路徑列表可以提前產(chǎn)生，例如，選擇一個可接受的候選路徑數(shù)K，然后使用K-最短路徑算法（參見附錄C。對問題（4.1.1），也可能采用針對有向圖的節(jié)點鏈路模型（參見2.2節(jié)。在這種模型中，為每個需求d、鏈路e，提供鏈路-流變量（而不是路徑流變量），并且指明穿越鏈路e的需求hd的數(shù)量。對節(jié)點鏈路模型，我們需要引入鏈路節(jié)點關(guān)聯(lián)關(guān)系；為了做到這一點，我們引入符號aev和bev來表示鏈路節(jié)點的關(guān)聯(lián)關(guān)系，如下面的模型所示。指d=1,2D:e=12,E:?。ㄓ邢蜴溌穠12,V:常aev=1，如果鏈路e于節(jié)點v;0，否則bev1ev0，否則sd:需求d的源節(jié)點td需求dhd:dξee的單元（邊際）xed：需求d分配到鏈路e的流量大?。ㄟB續(xù)非負minimizeF

∑e ifv=aevxed bevxed ifv?=sd, v=1,2,..., d=1,2,...,

?h ifv= ∑d

≤ e=1,2,...需求約束（4.1.5b通常被稱為流量守恒定律。注意問題（4.1.1的模型（4.1.5c的左邊是鏈路e的負載ye(x)。DSDP的節(jié)點鏈路模型（4.1.5）需要D×E個流變量（鏈路容量變量是輔助的）和E+D×V個約束（不包括標準的變量非負約束。模型（4.1.5）也可以應(yīng)用到無向圖。即：由兩條與原始鏈路具有相同單位成本的、有（?。o向（參閱練習(xí)4.1DSDP中的節(jié)點-（4.1.5）中了。各種最短路徑算法（例如Dijktra算法或廣度優(yōu)先搜索算法）的介紹見附錄C。事實上，我們還可以引入另一個節(jié)點鏈路模型。它比模型（4.1.5）有更少的流變量LP：D/SDP/MNLF節(jié)點鏈路模型d=1,2D:e=12,E:v12,V:常aev=1，如果鏈路e于節(jié)點v;0，否bev=1，如果鏈路e中止于節(jié)點v;0∑hvv′:起始于節(jié)點v，中止于節(jié)點v′的需求d的大小Hv= v′?=vhvv′:起始于節(jié)點v的所有需求的總量ξe:鏈路e的單元成本∑變xev：節(jié)點v為各種需求，在鏈路e上流出的流minimizeF

∑e∑e

= v=1,2,...,V ebvxev

eevxev′=hvv′ v,v=1,2,...,V,v?=v∑v

≤ e=1,2,...變量 限制2鏈路路徑模 Pˉ×V′×(V′?1)+1ˉ×V=O(V Pˉ×V′(V′?1)+1ˉ×V=O(V22節(jié)點鏈路模 1ˉ×V×V′(V′2

1)

O(V V×V′(V′?1)

1ˉ×V=O(V改進的節(jié)點鏈路模 1ˉ×V×(V′+1)=O(V V′(V+1)+12ˉ×V=O(V Table1:這里的技巧是，約束（4.1.6b）限定了節(jié)點v生成的、流出節(jié)點v的需求（4.1.6d）限定了于節(jié)點v、目的地是節(jié)點v′的這部分流hvv′留在節(jié)點v′（4.1.1（4.1.5）×ˉD=V′×(V′?1)V′(V′≤V節(jié)點數(shù)。記平均節(jié)點度為ˉk個需求的平均候選PˉV的增長而增長，V′V，即每個節(jié)點都有需求到另一個節(jié)點，則，三種形式的D/SDP變量和約束條件的數(shù)目如表4.1所示。（2.4.13）來解決問題，D/SDPD/SDP問題的非平凡擴展的容量受限問題中，這個問題才變得顯著起來。比較這兩種類型的形式，我們應(yīng)該注意到，鏈路路徑形式（4.1.1需要一些預(yù)處理，以獲得需求的候選路徑集，因此，有時可能會麻煩。但在另外一些情況下，預(yù)定義路徑集可能用起來非常方便，因為它們允許以一種簡單的方式控制實際上允許的路徑；例如，我們可能要求只使用有限跳數(shù)的路徑，這一點在節(jié)點鏈路形式中通常不可能做到。與此相反，（4.1.5（4.1.6（例如，過長路徑的直接，只能自動掃描所有網(wǎng)絡(luò)路徑。但是，有時我們可以通過將一些的鏈路流設(shè)置為零，以排除某些類型的路徑。這個問題將在6.3.4節(jié)中討論，位置在問題（6.3.7）后。下面的4.1考慮圖4.1中的網(wǎng)絡(luò)，它包括獨立的端和傳輸節(jié)點，其中端節(jié)點不能被用作路徑的 wwe=e=e= e=e=e=e=ve=傳輸節(jié)端節(jié)Figure1:包括分開的端節(jié)點點之間）的單位成本等于2。在這種情況下，節(jié)點鏈路形式（4.1.5）不能直接使用，如：從端節(jié)點v到目的節(jié)點u的需求d1，它的最短路徑為通過節(jié)點q，w，和s的路徑{12，3，7}，長度為5?？墒?，這一路徑是被的，因為它穿過了端節(jié)點w，而端節(jié)點是不能作為路徑的中間節(jié)點的。實際上，該需求的最優(yōu)路徑是路徑{1，5，6，7}，長度為6。因此，為了排除路徑{1，2，3，7}，我們要設(shè)x21=0。這樣它就不會出現(xiàn)問題模型（約束（4.1.5b）至（4.1.5c））中了。更一般的規(guī)律是：對每個進入端節(jié)點v的鏈路e，xeddv出來的鏈為了在修改后的節(jié)點-鏈路形式（4.1.6）中避免上述情況，我們要求：對從端節(jié)點v出來的鏈路（aev=1，只有節(jié)點v對應(yīng)的流變量xev可以非零，而其他所有非v終端節(jié)點對應(yīng)的xew必須等于0用節(jié)點v出來的鏈路為不是于v的需求用。類似的假設(shè)也用于進入終端節(jié)點的鏈路。那么，對這一情況，鏈路路徑形式又如何表示呢？顯然，把路徑1，2，3，7排除出需求d=1的路徑列表即可。這是如此簡單！D/SDP設(shè)計問題時，使用一種合適的路徑算法，而避免明確地使用任何LP方法。然而，對本書下面將要討論夠工作的，而在某些情況下，節(jié)點鏈路方案不適用（9.3.2容量受限問題4.1.1節(jié)考慮的D/SDP問題同時包括流的分配和鏈路容量優(yōu)化；后者印證了它名稱中所說的“無容量限制”。現(xiàn)在，假設(shè)我們要考慮網(wǎng)絡(luò)鏈路容量給定的問題；這在一個已經(jīng)建成了的網(wǎng)絡(luò)中是很常見的情況。這樣的容量受限問題將通過字母A表示（即 分配。最簡單的容量受限問題可能如下所示常δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:dcee變xdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負∑p

= （4.1.7a）∑d∑pδedpxdp≤ e=1,2,...該組符號和問題（4.1.1）中的符號幾乎是相同的。不同的是，有ce表示給定的鏈路容量，而不是（4.1.1）中的變量ye。另外，請注意，A/PAP沒有目標函數(shù)，因此，解決A/PAPx(x1,x2,xD)，其中xd=(xd1,xd2,...,xdPd),d=1,2,...,D，其滿足約束條件（4.1.7）。A/PAP問題又是一個。對LP：A/PAP/MLPF鏈路PAP修改后的鏈路路徑模型xdp：需求d分配到路徑p目∑p

= （4.1.8b）∑ p

≤z+ e=1,2,... 了一個最初A/AP（4.1.7）原始分配問題的可行解。若它的優(yōu)化目標z?為正，則z?確定了在至少一個鏈所需的最小必要額外容量（而且可能在的、甚至所有的鏈路上，以確保最初問題可行。命題4.1如果A/PAP是可行的，那么一個包括至多DE個非零流的解x存在。證明：把一個非負松弛變量s=(s1,s2,,sE)加到約束（4.1.7b）上，我們獲得如下標準LP問題p∑xdp= d=1,2,...,Dp ∑∑δedpxdp+se= e=1,2,...,E 中等式的數(shù)目（見[Las70]§1.2），所以，命題4.1成立（詳見第5.1.3節(jié)中的例5.3）。上述證明還表明了的內(nèi)容；例如，如果所有的松弛變量在最優(yōu)解中都大于0（即，D.1絡(luò)中，有多少路徑可能帶有非零流。在大多數(shù)實際情況下，D比E大得多。因此，這意4.24.1考慮一個V100個節(jié)點的無向網(wǎng)絡(luò)，平均節(jié)點度等于5。則E250。而D接近4.3另一個有趣的A/PAP的結(jié)果如分配每個需求d的所有需求至最短路徑上（鏈路數(shù)最短。如果在得到的這種（岔）方案中，所有鏈路都飽和（

dpδedpxdp≥ 鏈路過載（即有一些鏈路e

∑δedpxdpce）A/PAP是不可行的 用，但它有一個有趣的雙重解釋，并能用于Benders分解算法（5.1710.1和練習(xí)10.10的解答中基于雙重方法的證明。練習(xí)4.4要求讀者用這種簡單直接的方 明結(jié)果。A/PAP的一個可行解，而且希望找到最好的可行解（在某種意義上。這種想法可以通過引入一個目標函數(shù)來表示。例如，目標（4.1.8a）導(dǎo)致最大化最小的未使用容量（在所有鏈。如果我們希望明確地最大流量分配之后剩余的總未使用容量，這可以表示為下述目izeF=∑ere(ce?∑d∑pδedpxdp)=∑ere(ce?ye(x))其中，對每一個鏈路e，ye(x)，像往常一樣，是流量分配向量x引起的鏈路負載，reF，不一定是線minimizeF

∑ pρdpxdp其中，ρdp

∑ereδedp為需求d的路徑Pdp關(guān)于鏈路收入re的單位收入 7.2.2注意，命題4.1適用于上述情況以及下一節(jié)中描述的問題。混合當(dāng)我們想在一定上界的范圍內(nèi)規(guī)劃鏈路容量（即，有鏈路容量變量，但是鏈路容量的上限給出）時，混合的容量受限/無容量限制問題（標記為AD）就出現(xiàn)了。這是我們迄今為止所討論的問題的一個非常簡單的擴展。常δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:需求dceeξe:鏈路e變xdp：需求d分配到路徑p上的流的大小（連續(xù)非負yee的容量（連續(xù)非負目∑ e∑p

= d=1,2,...∑ p

≤ e=1,2,...ye≤ e=1,2,...這個問題的另一個解釋是，我們希望盡量減少路由成本，這一點由鏈路的單位成本暗示。為了看到這一點，我們可以消除變量ye（它在這種情況下可被理解為鏈路負載：ye=ye(x)=

∑ pδedpxdp)，并變換成本函數(shù)為F

∑ pζdpxdpζdp=∑eδedpξe是在路徑Pdp上傳輸單位流量的成本，由鏈路單元成本產(chǎn)生。需要注意的是其它路由成本也可使用（參見第2.1節(jié)。路由限在4.1節(jié)中考慮的最優(yōu)化問題假設(shè)沒有路由限制（除了一個事實，即在鏈路路徑方式下候選路徑的集合是預(yù)先定義好的，因此，D/SDP問題可以通過最短路徑分配規(guī)則解決。然而，在許多情況下，附加的約束自然地出現(xiàn)在網(wǎng)絡(luò)中。這些約束可以是必需的技術(shù)要求，也可能是操作的限制。下面，討論一些涉及這些額外的路由約束的重問題。此，使用量受限題AAP的擴展。意這些討論對DSDP型的無容量限制問題也是有效的。多路路徑分集（PD：PahDversiy）是一個很普通的要求。它強制拆分需求到多個路徑上。如此，只要一個需求使用的路徑的鏈路（節(jié)點）不相交，單鏈路（節(jié)點）就不會影響它太多。常δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:需求dce:鏈路e變xdp：需求d分配到路徑p上的流的大小（連續(xù)非負限∑p

= d=1,2,...∑ p

≤ e=1,2,...xdp≤ d=1,2,...,D,p=1,2,...,nd(100/nd)%。求至多丟失(100/nd)%的流量?；旧?，當(dāng)路由列表包含互不相交的路徑時（更精確地說，當(dāng)一個需求的路徑列表中的任兩條路徑不同時出現(xiàn)故障時（4.2.1有意義。假設(shè)只有單鏈路故障，一個比（4.2.1）更一般的模型，如下所示。它不需要通過預(yù)處理來獲得不共用鏈路的獲選路徑列表（生成這樣路徑的算法，參考附錄C。變xdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負∑p

= d=1,2,...∑ p

≤ e=1,2,...δedpxdp≤hd/nd, e=1,2,,Ed=1,2,,D,p=12Pd（4.2.2c）約束（4.2.2c）可確保沒有鏈路承載超過允許的需求量部分。A/PD和A/GD多路徑模型的一個缺點：（4.2.1c）和（4.2.2c）中有大量的多路徑限制。在節(jié)解D/SDPPD。一個立即的問題是：簡單的是：分配需求d的hd/nd部分流量到最短路徑上（相對于鏈路的單位成本），然后把下一部分的hd/nd流量分配到下一個最短路徑上，依此類推（注意：通常比hd/nd少的流最后，讓我們考慮節(jié)點鏈路方案的多路徑要求。廣義的多路徑要求很符合節(jié)點鏈路方案，因為限制xde≤提供了（4.2.2c）的節(jié)點鏈路形式對應(yīng)。同樣，節(jié)點不相交的路徑也可以被處理。后面第4.6.1將解釋這一點。PD情況下，流的大小有上限。PD的一個自然對應(yīng)是非零流有下限的要求，即，為了模型這一問題，每個路徑-流變量關(guān)聯(lián)一個二進制變量。如果該二進制變量取值為1，那么相對應(yīng)的路徑-流變量應(yīng)承擔(dān)至少等于下界的流；然而，如果流的大小可能低于該閾值，則我們想要設(shè)置該流為零。我們通過引入兩套附加約束來實現(xiàn)此目的，如下所示：常δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:需求dbd:需求d的非ce:鏈路e變xdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負udpxdp限∑p

= d=1,2,...xdp≤ d=1,2,...,D,p=1,2,...,bdudp≤ d=1,2,...,D,p=1,2,...,∑d∑pδedpxdp≤ e=1,2,...約束（4.2.3b）和（4.2.3c）保證：當(dāng)且僅當(dāng)udp=1，xdp>0，而且，就像需要的那樣，通過一個正的限制bd，非零流獲得了一個下界。注意，通過hd，約束（4.2.3b）限制變量在A/LBF模型中的出現(xiàn)使得它難以求解。事實上，針對這一問題，還沒有任何與在二元變量空間中全搜索顯著不同的已知方法（參見5.2節(jié)中的分支定界和分枝切割法）顯然，在鏈路路徑方法中，下限規(guī)定可與PD組合。相反，你會發(fā)現(xiàn)，節(jié)點鏈路模型完全不能用于A/LBF有限需求拆分PD（至多被分配到預(yù)定數(shù)量的非零路徑（路由2.4節(jié)中，我們已說明了這種情況，但沒有給出模型。我們首先提出不分岔（單路徑）流分配的一個模型。該模型不采用通常使用的流分配變量。因為流是不可分的，所以，你或者選擇這條，或者選擇那條路徑來攜帶整個需求。正如你可能會感覺到的，這聽起來很像一個二進制的決定問題，這恰好是這里的情況。同樣，我們使用二進制變量來確保整條流只通過一條路徑。常δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:dcee變xdp：需求d分配到路徑p上的流的大小（連續(xù)非負udpudp限xdp= d=1,2,...∑p

= d=1,2,...∑d∑pδedpxdp≤ e=1,2,...約束（4.2.4b）保證了只有一個與給定需 相關(guān)聯(lián)的二進制變量等 1。與約 須使用二進制變量這一條使問題的求解變得，特別是對大型網(wǎng)絡(luò)，幾乎不可能有效地求解。事實上，對大型網(wǎng)絡(luò)也沒有太大希望找到有效的解，因為這個問題是NP完全的（對于NP完全性這一概念的重要性，讀者可參見附錄B），如下面題所示。4.2A/SPA流量分配問題是NP完全問題。命題的成立是以下兩個事實的結(jié)果1：只有兩個需求（D2）、整數(shù)流（x1px2p是整數(shù)）的A/PAP分配流量問題，是NP完全問題。第4節(jié)和本書附錄B的B.8節(jié)。事實2：在均質(zhì)的單元需求（hd≡1）特殊情況下，A/PAP整數(shù)流問題是NPk的需求（商品）k1的源代替，并且這些新需求的源節(jié)12直接意味著尋找不可分流的問題是一個NP完全問題。需要注意的是ASPA可以被簡化，寫成下面的整數(shù)規(guī)劃（IP）IP：A/SPA鏈路路徑模型udp：表示需求d分配到路徑p上的二進∑p

= d=1,2,...∑d∑pδedpxdp≤ce, 回想一下，我們已經(jīng)在3.3節(jié)使用了相同的方IP：A/ES鏈路路徑模k條路徑下等量分配kd：預(yù)定義的需求d的路udp：表示需求d分配到路徑p上的二進∑p

= d=1,2,...∑d(∑pδedpudp)hd/kd≤ e=1,2,...要理解為什么上面的方案保證了分割，我們引入一個附加的流變量：xdphdudp/kd,d=1,2,...,D,p=1,2,...,Pd等。如此，不等式（4.2.6b）等價于通常的鏈路負載不等式：∑(∑δedpxdp)≤ e=1,2,...,E。因此，約束（4.2.6a）確保了正好 kd個與給定需求d關(guān)聯(lián)的二進制變量等于1。這一點，與約束（4.2.6b）一起，確保了對應(yīng)于非零二進制變量的每條路徑都承載了需求量hd的1/kdMIP：A/AS鏈路路徑模型xdp：需求d分配到路徑p的 udp：對應(yīng)流變量xdp的二進制變∑p∑p

= d=1,2,...= d=1,2,...xdp≤udphdd=1,2,...,D,p=1,2,...,∑d(∑pδedpxdp)≤ e=1,2,...約束（4.2.7b）和（4.2.7c）聯(lián)合強制了，對于每個需求d，非零流可被分配到最多 條路徑上。我們把一些其它與需求有限相關(guān)的容量受限分配問題的模型留給讀者在這一點上，注意到節(jié)點-鏈路模型可用于單路徑分配的要求是很重要的（A/指d=1,2D:e12,E:?。ㄓ邢蜴溌穠12,V:常aev=1，如果鏈路e于節(jié)點v;0，否則bev1ev0，否則sd:需求d的源節(jié)點td需求dhd:dceeude：對應(yīng)需求d分配到鏈路e上的流的二進制∑h ≤c e=1,2,... d ∑

ifv=aevude bevude ifv?=sd, v=1,2,...,V;d=1,2,...,

ifv=觀察模型（4.2.8，它允許擴展到限制路徑跳數(shù)（在鏈路路徑方法中使用有限跳數(shù)路徑的難題，容易由候補路徑預(yù)處理來解決；參考附錄C中的生成帶跳數(shù)限制的最短路徑算法。此外，為了確保需求d的路徑穿過不超過nd條鏈路，我們可加入下面的約束：∑e

≤ d=1,2,...盡我們所知，節(jié)點-鏈路模型不適用于均勻需求分割，也不適用于在預(yù)定數(shù)量路徑之間任意分割。不過，有些意外的是，我們可以用節(jié)點鏈路模型在固定數(shù)量的鏈路不相交的路徑上分配需求。方法如下所示：IP：A/ESLDP節(jié)點鏈路模型kd:預(yù)定義的需求d的路徑數(shù)ude：對應(yīng)需求d分配到鏈路e上的流的二進制∑uh/k≤c e=1,2,...dde ∑

ifv=aevude bevude ifv?=sd, v=1,2,...,V;d=1,2,..., ifv=和以前一樣，要理解為什么上面的模型保證了分配，我們引入流變xde=hdude/kdd=1,2,D,e=1,2,E。這樣的話，不等式（4.2.10a）

∑ pxde≤cee=1,2,E，而等式（4.2.10b（為每一個需求把等式（4.2.10b）兩邊同乘 hd/kd）等同于標準流量守恒方程 ifv=aevxde bevxde ifv?=sd, v=1,2,...,V;d=1,2,..., ifv=∑aevude≤ ifv?=sd, v=1,2,..., d=1,2,...,e連接在一起，來實現(xiàn)（4.6.14.11）。在這兩種情況下，我們可以觀察到，類似的鏈路路徑模型僅需要預(yù)定義的一套鏈路不相交或節(jié)點不相交的路徑（參見附錄C整體當(dāng)我們要把需求分配到在某些需求模塊上時，整體流的要求就自然出現(xiàn)了。例如，在傳輸網(wǎng)絡(luò)中，需求通常以模塊化單元為單位給出，如：在同步光網(wǎng)絡(luò)（第3.5節(jié)）中，在兩個節(jié)點之間需要的OC-3數(shù)量。常δedp=1，如果鏈路e在需求d的路徑p上;0，否Lddhd:dceexdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負udpxdp限xdp= d=1,2,...,D,p=1,2,...,∑p

= d=1,2,...∑d∑pδedpxdp≤ce,e1,2,E（4.2.11c）xdpIP：A/MFA鏈路路徑模型udp：對應(yīng)需求d分配到路徑p的流變量的非負整數(shù)∑p

= d=1,2,... d

≤ e=1,2,...≡步簡化。在這種情況下，鏈路容量ce的單位可以和L的單位相同，即，我們用ce/Lp代ce。如此，約束（4.2.12b）變?yōu)椤芼p

δedpudp≤ce在某些情況下，流量模塊化的需求相當(dāng)于在4.2.3節(jié)中討論過的有限需求拆分要求。特別是，單路徑分配A/SPA問題（4.2.4）相當(dāng)于A/MFA（4.2.12）在Hd=1和Ld=hd,d=1,2,...,D情況下的結(jié)果。因此，它遵循命題4.2的A/MFA是一個NP型D的無容量限制設(shè)計問題可能也有模塊化流的問題。非線性鏈路維度、成本和延類型的流變量（連續(xù)值、二進制數(shù)、整數(shù)。本節(jié)中，討論其他類型鏈路維度函（除了到目前為止我們討論過的線性維度函數(shù)的情況）對無容量限制問題的影響。通常鏈路代價函數(shù)的表示是建立在鏈路維度函數(shù)的表示的基礎(chǔ)上的。鏈路維度函數(shù)Fe(ye)決定了鏈路負 y（流經(jīng)鏈路的所有流的總和，以需求量的單位表示；DVUs）和鏈路最e容量ye（以鏈路容量單元為單位表示;LCUs）之間的關(guān)系。然后，鏈路的成本被表示為鏈路容量乘以一個合適的單位成本系數(shù)ξe。到目前為止，鏈路成本函數(shù)ξeFe(ye)簡單地是具有Fe(ye)=ξeye形式的線性函數(shù)（如（4.1.1）給出的D/SDP模型中的成本F），其中，鏈鏈路模塊化是各種通信網(wǎng)絡(luò)的一個共同特點。例如，在脈沖編碼調(diào)制（PCM）系統(tǒng)中，數(shù)字中繼群（見第3.4節(jié)）有M=24的語音電路模塊；在歐洲PCM系統(tǒng)中，數(shù)字中繼線路群（即PCM基群）有M=30的中繼模塊（實際上是32個，但其中2個被用于非語音傳輸）VC-4SDH63PCM（第3.5節(jié)），等。一個典型的模塊化鏈路的鏈路負載y的成本函數(shù)F(y)顯示在圖4.2 :考慮無容量限制D/SDP設(shè)計問題（4.1.1）。如果我們現(xiàn)在引入模塊化容量的鏈路，那么，變量ye（它在（4.1.1）中是續(xù)變量）就因為模塊化，變?yōu)橐粋€離散變量。本質(zhì)上，這意味著問題（4.1.1）被修改為如下MIP模型：指d=1,2D:p=1,2,Pd:流量需求de=12,E:常δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:需求dξe:鏈路e的單位（邊際）成本M:xdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負ye:鏈路e容量，表達為鏈路模塊的數(shù)目（非負整數(shù)目∑minimizeF eξeye（帶寬成本（4.3.1a）∑p

= （4.3.1b）∑d∑pδedpxdp≤ （4.3.1c）一個解這個問題的明顯的啟發(fā)式方法是，假定一個鏈路維度函數(shù)的線性近似（如況下，這將導(dǎo)致距離最佳很遠的結(jié)果。事實上，當(dāng)鏈路容量模塊M 例4.4考慮一個全網(wǎng)狀結(jié)構(gòu)的網(wǎng)絡(luò)，它包括V個節(jié)點。每兩個節(jié)點間都有單位流的需求（hd=1,d=1,2,...,D=V(V?1)/2）。每條鏈的一個容量模塊的成本等于1（ξe≡1）。鏈路容量模塊M等于D個流量單元。由于一個鏈路模塊能夠容納所有的需求量，因此，顯然，D/ML的最優(yōu)解對應(yīng)于一個生成樹T?E，其中，如果eT，ye1；否則，ye0VV1條鏈路，所以，這樣的解的最低成本等于V?1。與此相對應(yīng)的是，最短路徑分配規(guī)則將生成這樣一個ye=1,e=12,E=V(V1)/2。其成本等于V(V1)，這是最小成本V1的V/2上例證明了，最短路徑分配規(guī)則并不適用，因為使用較長的路徑去充分利用已安裝DML是一個NP完全問題。這一點很容易通過一個類似于例4.4的證明來獲得，如下所示。命題4.3D/ML（4.3.1）問題是NP完全問題。證明，所考慮的問題解決了Steiner樹問題（STP），而STP已知是NP完全問題（見[GJ79]）。為此，STP表述如下：給定一組節(jié)點v=1,2,...,V，它的V′?V；一組鏈路e=1,2,E，它們有給定的權(quán)重ξe；需找到一個子圖T?E，使得T包含連接V′中任一對節(jié)點的一條路徑，并且最大限度地減少成本：ξ(T)=∑e∈Tξe.PV′erVV′中的節(jié)點。因此，這一問題不等同于發(fā)現(xiàn)生成所有節(jié)點V的最輕的樹。事實上，我們能夠通過rukal或Prm算法（見[ru56]）很容易地發(fā)現(xiàn)生成所有節(jié)點V4.4hd1V中的每對節(jié)點，并使MV′(V1)/2。那么（431）就解決了我們介紹的這個STP路相關(guān)聯(lián)的變量的數(shù)目，因為每種模塊類型（k=1,2,...,K）都需要一組這樣的變量。另外k1,2K:δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:需求dξek:鏈路e上一單元類型為k的模塊的成本Mk:kxdpdp上的流的大?。ㄟB續(xù)非負yek:鏈路e上類型為k的鏈路模塊的數(shù)目（非負整數(shù)目∑minimizeF kξeyek（帶寬成本（4.3.3a）∑p

= （4.3.3b）∑d∑pδedpxdp≤∑k （4.3.3c）請注意，如果這些鏈路模塊從小到大排序（M1<M2<...<MK），那么，對每條鏈路e，通常有ξe1ξe2ξeK。這一屬性導(dǎo)致如圖4.3所示的成本函數(shù)。在這個例子中，我們假定K=2，M2=2M1，ξe1<ξe2<2ξe1。此外，還有另式，來引入具有不同模塊的模塊化成本函數(shù)，即增量表征方法[DS98，Wes00]。此時，K表示步數(shù)，m1,m2,...,mK是成本函數(shù)增加（跳躍）的負載增量。鏈路e上的每個增量模塊mk的成本為ξek。這個成本模型的基本假設(shè)是，當(dāng)模塊k安裝在一個鏈時，所有的增量模塊j，j<k的鏈路模塊也必須被安裝。這導(dǎo)致了以常δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:需求dξek:鏈路e上一單元類型為k的模mkkxdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負uek:類型為k的增量鏈路模塊是否被安裝在鏈路e上的二元minimizeF

∑e∑k∑p

= d=1,2,...∑∑

≤∑m

e=1,2,... edp kue1≥ue2≥...≥ e=1,2,...2ξ2 M2=2M1 2M22M2+M13M2:10.4一類重要的非線性成本函數(shù)是凸函數(shù)（凸的概念參見附錄A）。我們從它的定義開始。一個函數(shù)f:[0,∞)→R是凸的，當(dāng)且僅當(dāng)，對[0,∞)上的任意兩點z1,z2，任意α∈[0,1]，下列關(guān)系成立αf(z1)+(1?α)f(z2)≥f(αz1+(1?z1αz1+(1-)z2z2Figure4:通常情況下，凸成本函數(shù)在通信網(wǎng)絡(luò)中被用來描述延時。例如，一個數(shù)據(jù)包網(wǎng)絡(luò)鏈路e可以模型為一個M/M/1隊列（例如，見[BG92]和第1.3.1節(jié)中的討論），而分組沿鏈路發(fā)送所經(jīng)歷的平均時延是一個關(guān)于鏈路負 y（PPS（每秒包數(shù)））的凸函數(shù)，eeFe(ye)

ce—

0≤

<CXP：A/CCF鏈路路徑模型d=1,2D:p=1,2,Pd:流量需求de=12,E:常δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:需求dFe(·):鏈路eceexdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負ye:e負荷（連續(xù)非負目minimizeFee

（4.3.6a）∑p

= （4.3.6b）∑ p

= （4.3.6c）ye≤ e=1,2,...CXP代表凸規(guī)劃問題（ConvexProgrammingProblem，參見附錄A的凸規(guī)劃問題定義。當(dāng)然，我們知道，函數(shù)不是常量；我們把在常量列表中一一列舉出來，而不是創(chuàng)建另一個類問題參數(shù)。注意，如果我們在(4.3.6a)中使用函數(shù)eF(y) e=1,2,...e ce?那么，得到的目標函數(shù)就與報文經(jīng)歷的平均網(wǎng)絡(luò)延時成正比（參見7.1.1節(jié)中的（7.1.7））。請注意，嚴格來說，具有（4.3.5）和（4.3.7）形式的函數(shù)Fe(·)在區(qū)間外是沒有意義的。當(dāng)y=ce時，它們無限大e利用懲罰函數(shù)，凸函數(shù)也可以被用來把容量受限的流分配問題轉(zhuǎn)換為無容量限制問題：我們只需要確保選擇的懲罰函數(shù)是凸的，并且當(dāng)鏈路容量超出時，會導(dǎo)致沉重的代e：F(y) ifye≤ ξ(y—c ify> 常δedp=1，如果鏈路e在需求d的路徑p上;0，否ce:eFe(·):exdp：需求d分配到路徑p上的流的大小（連續(xù)非負ye:e目minimizeFee

（4.3.8a）∑p

= d=1,2,...∑ p

= （4.3.8c）是凸函數(shù)f(x在[0,∞)上非減的充分條件。原因是，對一個非減的凸成本函數(shù)f，當(dāng)z1z2f(z1)/z1≤f(z2)/z2（這一嚴格不等式對嚴格凸函數(shù)成立），所以，將需求分開到多個路徑上是有利的，至少當(dāng)路徑有相似費用時（參見練習(xí)4.13）。我們考慮的優(yōu)化問題是凸的（它們討論性約束下讓一個凸目標函數(shù)最小，而且，它們沒有關(guān)于目標（4.3.8）或（4.3.13）的局部極小，只有一個全局最小。該最小可能在多個可行點（這些最佳點是凸的）達到（參考文獻[Las70]和附錄A。因此，當(dāng)所考慮的成本函數(shù)是可微的時（如在問題（4.3.6）中，可以使用某些形式的受限梯度最小化技術(shù)求解（請參見第5.5節(jié)。但是，在任何情況下，凸特性本身足以把考慮的問題轉(zhuǎn)換成與它們接近的LP問題。在我們的情況下，基本思路是把成本（或懲罰）Fe(·替換為它們的分段線性近似。例4.5一個凸函數(shù)的分段線性近函f(z)= for0≤z≤1(z?1)2 forz>1已在問題（4.3.8）中考慮過。（4.3.9）的一個由四個線性分段組成的分段線性近如下所示（見圖4.5）：

for0≤z≤z? for1≤z<f3(z?1)+1=3z? for2≤z<10(z?3)+4=10z? forz≥在一般情況下，我們考慮函數(shù)f(z)f(z)=fk(z)=akz+ sk?1≤z< 8ff420 0 1 2z

3 Figure5:一個凸函數(shù)的分段線性（其中s1=0，sk可以等于+∞）作為凸函數(shù)f(z)的分段線性近，z≥0。假設(shè)我y，y0。引導(dǎo)在LPf(y的值的關(guān)鍵觀察是，由于凸特性，f(z)=k12,..,K{akz+為真（4.5）LPf(y)rf(y的正確值（參照練習(xí)4.14和4.15）：minimizesubjecttor≥aky+ k=1,2,...,K.上述觀察讓我們有可能把如（4.3.6）或（4.3.8）的凸數(shù)學(xué)規(guī)劃問題轉(zhuǎn)換為LP問題，如下圖A/CPF問題所示（4.3.8（另見練習(xí)4.16）。凸懲罰函數(shù)-分段線性近似k12Ke:Fe(·連續(xù)分段線性近似aek,bek:Fe(·)的分段線性近似的線性分xdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負y:eere:Fe(y)eminimizeF

（4.3.13a）∑p

= d=1,2,...∑ p

= e=1,2,...re≥aekye+ e=1,2,...,E,k=1,2,...,述LP程序包含E個附加變量和E×K個另外的約束。在許多應(yīng)用中，近似的線性分段方程（4.3.1）的確切形式并不重要；其斜率和它們在哪里改變才真正重要。假定第一個線性分段開始于原點（0,0，這一系列片段的斜率是ak，k=1,,...,K，轉(zhuǎn)折點為0=s0<s1<s2<<sK（sK可能等于∞，類似（4.3.12）的近似minimizea1z1+a2z2+...+subjecttoy=z1+z2+...+0≤z1≤s1?0≤z2≤s2?..0≤zK≤sK?sK?1（4.3.14）z1s1z2s2?s1，，zk?1sk?1?sk?2，zk?

ksubject

kzk=0≤zk≤ k=1,...,Kmksksk?1mk就足夠了。最后，請注意，所有在第4.3.2節(jié)中考慮的問題也可以用節(jié)點鏈路符號表示。我們用一個涉及線性目標和凸約束的經(jīng)典數(shù)據(jù)網(wǎng)絡(luò)凸容量設(shè)計問題結(jié)束本節(jié)。該問題的需求是：路由是固定的，該網(wǎng)絡(luò)需要獲得一個平均分組延時的界（[BG92]。需要注意的是，固定路由意味著鏈路負載e

是固定的。延時約束是凸的，并且基于e=12,E:常y：固定路由導(dǎo)致的鏈路eeξe:鏈路eH:總流量，H?:變

∑dhd，其中hd是需求dy:e容量（非負連續(xù)e目minimizeF

∑eye≥ e=1,2,...1 e

≤（4.3.16c）這個問題有如下ye的解1√

∑√ye=ye

e? Hξ ?

ll), 最優(yōu)解可以通過觀察獲得：對連續(xù)容量變量，延時約束（4.3.16c）實際上滿足了最優(yōu)解的性（否則，容量可以減小。上述解可以通過Karush-Kuhn-ucker條件（參見附錄A中.2節(jié)，或經(jīng)典日乘法（練習(xí)4.17）容易得到。在一般情況下，凸狀的限制可以使用本節(jié)前面所描述的技術(shù)進行線性化，而帶凸約束的問題也可以轉(zhuǎn)化為它們的LP近似。此方法在第13章將得到應(yīng)用?！师羏(z1)+(1?α)f(z2)≤f(αz1+(1? f(αz1+(1- αz1+(1- z2Figure6:f(z1)/z1≥f(z2)/z2f(z1)/z1≤F(z2)/z2更自然（4.18）。例4.6基于愛爾蘭B-損耗的凹函e考慮一個網(wǎng)絡(luò)中的鏈路e（一個中繼線群。該鏈的負荷為A愛爾蘭，即：y=A。為了規(guī)劃的目的，各鏈路的阻塞率b可以被認為是固定的和相等的（例ee如，be≡0.1%），所以，相應(yīng)的鏈路維度函數(shù)ye=Fe(ye)為愛爾蘭損 的逆運（be=到實數(shù)域的擴展[Sys66]。值ye是在鏈路e上承載負荷A，且阻塞率為be時，所需的中繼線數(shù)（連續(xù)的?？梢钥吹?，F(xiàn)e(0)=0Fe(·)是[0,∞上的嚴格遞增凹函數(shù)[Sys66]一個類似于D/SDP的凹規(guī)劃問題（CVP）如指d=1,2D:p=1,2,Pd:流量需求de=12,E:常δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:需求dξe:鏈路eFe(·)exdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負y:ee目minimizeFee

∑eξeFe(y∑p

= d=1,2,...∑ p

= （4.3.18c）4332ff zFigure7:凹函數(shù)的分段線性因為維度函數(shù)的特性：當(dāng)z1<z2時，f(z1)/z1≥f(z2z25.6該問題包括線性約束下一個凹目標函數(shù)的最小化（4.3.18a，所考慮的問題的實例通常有許多在約束（4.3.18b）和（4.3.18c）確定的可行區(qū)域內(nèi)的極值點）處的局部最小值。因此，尋找全局最小可能是一個非常的任務(wù)（[Mn86]和第5.6節(jié)。4.3.2節(jié)，我們已經(jīng)展示了具有凸目標函數(shù)和線性約束條件的問題如何由LP?；舅枷胧牵拖裢範畹那闆r那樣，把凹函數(shù)Fe(·)換為它們的分段線性近（圖4.7）。例4.7一個凹函數(shù)的分段線性近f(z)=

z≥該平方根函數(shù)的一個由四個線性分段組成的分段線性近如下所示（見 for0≤z<f(z)= (z?1)/3+1=z/3+2/3 for1≤z<4(z?4)/5+2=z/5+ for4≤z<(z?9)/7+3=z/7+ forz≥定義函數(shù)f(z)f(z)=fk(z)=akz+ sk?1≤z< （其中sk可以等于+∞）作為凹函數(shù)f(z)的分段線性近。假設(shè)我們有了一個≥∑subject

k(akyk+ ∑y= u∑u k=yk≤ yk非負連續(xù)，uk二元變量意，（4.3.22）等價于下面的以二進制變量uk表示的問題：∑ kuk(aky+∑ subject u （4.3.22（個（4.3.23）∑yuk相乘的元素（k(akukybkuk)），為這一，我們引入了k個輔助變量y1,y2,...,yK和（4.3.22）中列出的附加約束。它們迫使最優(yōu)解中恰好（并且正確）有一個yk的值非零并等于y。（4.3.22）的目的是把凹數(shù)學(xué)編程問題（4.3.18）MIP凹維度函數(shù)-分段混合整數(shù)近似k12Ke，F(xiàn)e(·線性近似的連續(xù)分段aek,bek:Fe(·)的分段線性近似?:xdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負ye:eyek：鏈路e的附uek：鏈路e的附∑minimizeF k(aekyek+限∑p

= d=1,2,...∑ p∑

≤ e=1,2,...kyek= e=1,2,...∑k

= e=1,2,...yek≤ e=1,2,... k=1,2,...假設(shè)每條鏈路的分段線性近包括相同數(shù)目K的段，相對于原始近似問題，上述問題包含E×K個附加連續(xù)變量，E×K個附加二元變量，和E×(K+2)個附加約束。面搜索（例如分支定界，參見第5.2節(jié)）顯著更好的一般算法了。正如凸鏈路成本（維度）（4.3.21的確切形式并（0,0，這一系列片段的斜率是ak，k=,2,...,K，轉(zhuǎn)折點為0=s0<s1<s2<<s（sK可能是一個很大但有限的數(shù)?，類似（4.3.22）的近似如下：minimizea1z1+a2z2+...+subjecttoy=z1+z2+...+u1≥u2≥...≥(s1?s0)u2≤z1≤(s1?(s2?s1)u3≤z2≤(s2?..(sK?1?sK?2)uK≤zK?1≤(sK?1?0≤zK≤(sK?zk連續(xù)變量，uk二元變量這個限制暗示：如果uk=，k=0，那么u1=u2==uk=1，并且強制對所有的j<k0≤zk≤mk有zj=mj，對所有j>k，有zj=0(這里mk=sk?sk?1)?！苨ubject

kk∑z=kmkk1≤zk≤ k=1,...,K注意，因為冗余，我們忽略了限制u1u2uK常δedp=1，如果鏈路e在需求d的路徑p上;0，否ce:eFe(·):exdp：需求d分配到路徑p的ye:e限∑p

= d=1,2,...∑ p

= e=1,2,...Fe(ye)≤ e=1,2,...上述問題有一個為線性約束（4.3.27a）（4.3.27b）和凹約束（4.3.27c）定義的非凸（4.3.22（練習(xí)4.22它以轉(zhuǎn)換一個MIP近似問題。請注意，所有在本節(jié)考慮的問題都可以通過節(jié)點鏈路方式進行模型。預(yù)算約在許多情況下，預(yù)算約束能夠提供比最小化成本函數(shù)（如DSDP）更好的方式作為設(shè)計目標。預(yù)算約束代替了明確的最小化代價函數(shù)（4.1.1a，并允許引入另外的目標函數(shù)，如某種類型的吞吐量最大化。為了說明這個問題，考慮下面的無容量限制問題：指d=1,2D:p=1,2,Pd:流量需求de=12,E:常δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:需求dξe:鏈路e的單元（邊際）成本B:xdp：需求d分配到路徑p上的流的大?。ㄟB續(xù)非負ye:er實現(xiàn)的需求量的比例（連續(xù)非負∑p

≥ d=1,2,...∑ p

≤ e=1,2,...∑eξeye≤上述LP問題的最優(yōu)解將使用整個給定預(yù)算，以盡可能多地分配需求，同時保持住hd(d=1,2,D給出的各需求之間的比例關(guān)系。這種類型的D/SDP擴展，可以與本章中已討論過的其他無容量限制問題擴展（例如，凸成本函數(shù)或凹維度函D/BC的擴展，來描述拓撲設(shè)計問題（6.3.2節(jié)、公平網(wǎng)絡(luò)設(shè)計增量前面章節(jié)中考慮的D（因此它不是一個“新建”網(wǎng)絡(luò)新增的需求。另一個很好的擴充資源的理由是：在一個最初需求未受保護的網(wǎng)絡(luò)中，增加對需求的保護。這些情況能夠用增量網(wǎng)絡(luò)設(shè)計問題描述；它們被稱為網(wǎng)絡(luò)擴展問題。為此，問題（.1）擴展如下：指d=1,2D:p=1,2,Pd:流量需求de=12,E:常δedp=1，如果鏈路e在需求d的路徑p上;0，否hd:需求dξe:鏈路e的單元（邊際）成本ceexdp：需求d分配到路徑p上的流的大小（連續(xù)非負ye:ece以上額外的容量（連續(xù)非負目∑minimizeF eξeye（帶寬成本（4.5.2a）∑p

= （4.5.2b）∑d∑pδedpxdp≤ye+ （4.5.2c）個問題對應(yīng)于網(wǎng)絡(luò)規(guī)劃過程中的一個重要問題：網(wǎng)絡(luò)容量擴展問題，因此，它通常不需是請注意，通常，在E/SEP的最優(yōu)解y?下，由（4.5.2a）給出的成本F(y?)會大于F(y?)? eξece，其中y?∑D/SDP（4.1.1）在相同輸入需求和成本數(shù)據(jù)下的最優(yōu)解（在D/SDP中，存在是網(wǎng)絡(luò)，已經(jīng)被投入的預(yù)算（eξece）可以被更好地利用，因為原始的需求量（現(xiàn)有的網(wǎng)4.8331 Figure8:4.82413。假設(shè)模塊成本等于1，則最優(yōu)解為成本F=3，每條鏈路的容量都為ce=1?，F(xiàn)在，如果?13?和?23?的需求數(shù)量增加至35，而對?12?的需求保持不變，那么，最優(yōu)的擴展結(jié)果為：在鏈路?13?和?23?上分布增加一個額外的模塊，擴展成本F?=2。所以，F(xiàn)F5。與此相對應(yīng)的是，如果我們?yōu)榇诵滦枨髲臒o到有設(shè)計網(wǎng)絡(luò)，那么，給鏈路?13和?23F?4。所以，擴展方案要重要的是，要注意到，E/SEP類型的擴展問題可以以類似本章前面描述的、D/SDP問題建模的擴本節(jié)中，解釋一些其他問題。這些解釋便于我們使用本章前面討論過的模型框架來討論擴展的NDP問題，包括節(jié)點模型、組播連接等。我們也將回過頭來，討論NDP的鏈路路徑表示方法的優(yōu)勢。描述正如你可能已經(jīng)注意到（并為此而惱火）的，在這一章已考慮過的問題模型中，鏈路容量被作為關(guān)鍵的網(wǎng)絡(luò)資源，而節(jié)點能力沒有被明確考慮。與連接到節(jié)點的鏈路的容量相關(guān)聯(lián)的節(jié)點成本（如輸入/輸出端口和鏈路終端設(shè)備成本）可以直接算入鏈路成本中予以考慮。而另一類節(jié)點能力，來自于連接到節(jié)點的總鏈路容量以及關(guān)聯(lián)成本（例如，F(xiàn)igure9:對于有向圖（例如，在節(jié)點鏈路模型中使用的），每個節(jié)點v被其兩個拷貝（節(jié)點v′和v′′）和一個內(nèi)部有向鏈路e(v)=(V′,v′′)取代。這兩個匹配的拷貝之間的鏈路被添加所有從節(jié)點v出來的鏈路從節(jié)點v′′出來。對鏈路路徑模型中使用的圖（它們基本上是無向圖），可以用一個更簡單的方式完成。對每個節(jié)點v，一個額外的（人造的）鏈路e(v)被引入到鏈路列表。對這些人工鏈路，我們定義一些一致性系數(shù)如下：(δevdp 如果節(jié)點v屬于需求d的路徑( 否∑節(jié)點的負荷yv pδe(v)dpxdp可用于其它目的，如，為節(jié)點的負載增加一個∑δe(v)dpxdp≤ v=1,2,..., 節(jié)點v的成本，取決于它的負載 ，這可以出現(xiàn)在設(shè)計問題的目標函數(shù)中。注意v由于交換/路由機構(gòu)的結(jié)構(gòu)，節(jié)點的成本往往是高度模塊化的。內(nèi)部鏈路的概念對模型節(jié)點故障也很有用：如果一個節(jié)點出現(xiàn)故障，我們就簡單地讓它的內(nèi)部鏈路故障。注意，如果第4.2.1節(jié)的多路徑鏈路路徑方案（4.2.2也被擴展到包括節(jié)點故障，那么，多路徑約束（4.2.2c）會變少很多：δe(v)dpxdp≤ d=1,2,..., v=1,2,...,V,v?=sd,v?=δedpxdp d12D,esdtd)(esdtd之間的鏈路（有向鏈路其中，sd和td是需求d的端節(jié)點。使用節(jié)點-鏈路形式，上面的兩個限制變得xe(v)d≤ d=1,2,..., v=1,2,...,V,v?=sd,v?=xed≤ d=1,2,..., e=(sd,最后，我們來看看這一問題：用節(jié)點鏈路形式，模型在節(jié)點不相交的路徑上均分需求（參見（4.2.10），加上約束（4.2.10c））。通過節(jié)點，這些額外的約束可以簡單地換ude(v)≤ d=1,2,..., v=1,2,...,V,v?=sd,v?=注意，需求標記d不必被限定為僅指“一個節(jié)點對之間有一個需求”。例如，一個節(jié)點對可以有多個不同的需求（例如，由于不同的服務(wù)或帶寬要求。然后，用單個標識符d標記它們，已足以描述這些變量，而無需改變問題的描述。類似地，鏈路標識符e可以有趣的是，一個需求標識符可用于標識其它的、不是端到端需求的對象，例如，一個組播組的需求。這涉及到不僅僅是一對節(jié)點的多個節(jié)點。當(dāng)然，該需求需要使用“路并不是的。例如，當(dāng)一個需求標識符被用來標識不同的服務(wù)時，每個服務(wù)都能有一組候選路徑。在同一節(jié)點對之間，它們可以隨著服務(wù)的不同而不同。當(dāng)一個需求代表一個組播組種方法能夠工作的原因是，在鏈路路徑模型的鏈路容量約束中，一個鏈路需要檢查是否有路徑通過它，這可以通過“增量”指示器δedp來反映，而無需擔(dān)心是否有一條“路徑”可以進一步的是，即使一個需求標識符與一個節(jié)點對相關(guān)聯(lián)，路徑也不必限于常規(guī)的路徑。例如，實際上，一條“路徑”可以被用于表示一對路徑：主/備路徑（9.3.4節(jié)。因此，你可以看到，鏈路路徑模型有幾個非常強大的屬性；這些擴展在節(jié)點鏈路模型中幾乎是不可能的?？偨Y(jié)和進一步本章的目的是雙重的。首先，它提供了一組基本設(shè)計問題。這些問題將會在第二部分的章節(jié)中被討論。它們也會出現(xiàn)在大量網(wǎng)絡(luò)設(shè)計方面的中。這些分布在各種電信、數(shù)據(jù)通信和運籌學(xué)的期和會議錄中。這些模型使用一種一般的、統(tǒng)一的、簡潔的、概括性的、專為本書的目的而開發(fā)的符號。只要有可能，我們就嘗試了探討不同問題之間的聯(lián)系。本章模型有著優(yōu)化問題的形式，在運籌學(xué)中也被稱為數(shù)學(xué)規(guī)劃問題（數(shù)學(xué)規(guī)劃或數(shù)學(xué)程序。這通常意味著它們有下面的形式minimizeFsubjecttox∈其中，F(xiàn)x)為給定的目標函數(shù)，S為方案集（優(yōu)化空間。S通常是n維空間（參見附錄A的一個子集（在大多數(shù)情況下，無論是緊湊的或有限的。模型的這種形式允許使用優(yōu)化理論和運籌學(xué)研究中為各種數(shù)學(xué)程序而開發(fā)的各種解法（即優(yōu)化算法。然而，應(yīng)當(dāng)強調(diào)的是，在大多數(shù)情況下，作為問題建模的最后一個步驟，找到了一種數(shù)學(xué)形式（不管它可能多么好，并不意味著找到了有效解決問題的方法。正相反，在許多情況下，這只是一個通常會痛苦的過程的開始：為我們要考慮的問題的實例，1）發(fā)現(xiàn)，2）剪裁，3）應(yīng)用（實現(xiàn)）有效算法。對大型網(wǎng)絡(luò)中的問題尤其如此。在第五章中，介紹和討論一些優(yōu)化方式、方法和算法，包括LP、MIP、凸規(guī)劃、凹規(guī)劃。然后，我們會越來越清楚：什么算法可以用于本章討論的問題。同時，它將變得明顯：幾乎所有的非LP問題都難以求解，特別是大型網(wǎng)絡(luò)中。首先，一個經(jīng)驗是，隨著變量數(shù)的增長，MIP問題很快變得棘手，不管我們使用什么的MIP求解器（盡管最近幾年對MIP的求解技巧有了很大的發(fā)展，特別是在分支定切方面。這是MIP問題的一種內(nèi)在，因為在大多數(shù)情況下它們是NP完全的。其次，典型的大型凸網(wǎng)絡(luò)設(shè)計問題會受很慢收斂的困擾。最后，針對凹規(guī)劃問題的算法通常會堆積在局部極小，使它幾乎不可能找到真正的全局最優(yōu)解。我們比較確信的是，在大多數(shù)情況下，只有LP方程允許成功地應(yīng)用已有的（商業(yè)和免費的）求解器，在可接受的時間內(nèi)，得到確切的最優(yōu)方案，只要變量和約束的數(shù)量保持在一個可控水平內(nèi)。如果LP方程中的變量和約束數(shù)目變得太大，一些有效分解的方法，例如列產(chǎn)生、日松弛、Benders分解（在后面的章節(jié)中將討論）可以有效地應(yīng)用于其中，以有效地處理大型網(wǎng)絡(luò)設(shè)計，如包括數(shù)百個節(jié)點的網(wǎng)絡(luò)。但是，這些分解方法的使用，對于一個初學(xué)者來說可能是相當(dāng)?shù)?。這一切都導(dǎo)致了需要使用元啟發(fā)式算法（如模擬退火、仿真分配、進化算法、搜索）及在它們的基礎(chǔ)上發(fā)展起來的、為了處理包括整數(shù)（二元）變量和非線性成本函數(shù)的NDP（希望是接近最優(yōu)的）找到近似解；不過，制定合適的算法有時可能是麻煩的。這本書的一個貢獻是討論了網(wǎng)絡(luò)設(shè)計的啟發(fā)式方法。本章的第二個目的是要說明（并嘗試教初學(xué)者）如何構(gòu)建網(wǎng)絡(luò)設(shè)計模型，通過在模型中逐漸添加難度，以捕捉我們討論的問題的特征（有時是相當(dāng)復(fù)雜的。這些問題來自于具體的網(wǎng)絡(luò)結(jié)構(gòu)和所使用的技術(shù)。在4.1節(jié)中，我們從最簡單的維度和LP模型（分別是D型和A型）條件代表問題的不同方面。這種有條不紊的方法有助于讀者更好和更全面地理解第二章和第三章中曾討論過的問題和示例。更重要的是