鄭曉月

（商丘師范學(xué)院 計(jì)算機(jī)與信息技術(shù)學(xué)院，河南 商丘 476000）

背包核首次應(yīng)用是在解決大（無(wú)關(guān)聯(lián)）背包問(wèn)題上。Balas和Zemel（1980）根據(jù)實(shí)驗(yàn)觀察到線形松弛背包問(wèn)題（LKP）的解與求KP問(wèn)題最優(yōu)解的不同僅體現(xiàn)在幾個(gè)元素上，他們將包含這些元素的區(qū)間作為核。由于問(wèn)題求解之前無(wú)法精確標(biāo)識(shí)核，他們就通過(guò)估計(jì)中心元素附近區(qū)域的大小用一個(gè)近似區(qū)間來(lái)表示核[1]。使用背包核可以在分支定界（B&B）算法中獲得一個(gè)較好的下限。

這個(gè)近似核雖然使得分支定界算法效率有所提高但是核的大小卻是固定的（Martello&Toth，1990）。Pisinger引入了核的動(dòng)態(tài)擴(kuò)展思想并把它應(yīng)用到B&B算法中（Pisinger，1994），后來(lái)又用于動(dòng)態(tài)規(guī)劃算法（minknap）（Pisinger，1997）。Pisinger又將這些思想應(yīng)用于MCKP問(wèn)題并獲得了有效的解決MCKP問(wèn)題的動(dòng)態(tài)規(guī)劃算法（Pisinger，1995）。在多維背包問(wèn)題中，Puchinger，Raidl和Pferschy最近提出了一種新方法用來(lái)標(biāo)識(shí)核，并且將其應(yīng)用于一個(gè)模擬框架和一個(gè)松弛導(dǎo)向變量區(qū)域搜索以獲得近似方法用來(lái)解決MKP問(wèn)題[2]。

鑒于核思想成功解決了很多一般背包問(wèn)題，文中導(dǎo)出一個(gè)處理多維多選擇背包問(wèn)題（MMKP）的近似核，并用它精確處理這類(lèi)問(wèn)題。用三步連續(xù)的過(guò)程來(lái)定義核。方法是在解空間取一個(gè)基點(diǎn)，然后定義一個(gè)變量的排序關(guān)系。接著這個(gè)排序關(guān)系將被用來(lái)定義基點(diǎn)附近構(gòu)成背包核的合適子空間。

1MMKP核的確定

據(jù)Balas和Zemel的定義，核是背包最優(yōu)解空間和相關(guān)線性背包最優(yōu)解空間中具有不同值的元素所構(gòu)成集合的最小區(qū)域。精確的定義核C可以這樣表述（沒(méi)有臨界元素的情況不算在內(nèi)）：

其中，x*背包問(wèn)題的最優(yōu)解，N是根據(jù)它們的性價(jià)比排序后元素的集合。

不幸的是，在解決背包問(wèn)題之前這樣的核是沒(méi)辦法找到的，必須找一種方法來(lái)獲得一種近似核。根據(jù)實(shí)驗(yàn)，可以通過(guò)

下面3步得到MMKP問(wèn)題的一個(gè)近似核，具體步驟是：1）取解空間中的任意解x（有可能是不可行的），稱之為基礎(chǔ)解或者基本解。把它作為核的中心，核將圍繞這個(gè)中心來(lái)定義。如果這個(gè)點(diǎn)臨近一個(gè)最優(yōu)解，就可以得到一個(gè)小型準(zhǔn)確核。由于一個(gè)最優(yōu)解可能靠近可行性區(qū)域的邊界，因此并不強(qiáng)制要求基本解是可行的。為了簡(jiǎn)單起見(jiàn)，還假設(shè)這個(gè)基本解是整形，它可以是松弛問(wèn)題的四舍五入解或者啟發(fā)式解。

2）在變量中定義一個(gè)全序關(guān)系。令x*為最優(yōu)解，并將元素 i的變化概率表示為 Pch（i）=Pr{x*i≠xi}，其中 P是問(wèn)題所有情況下的變化概率。特別關(guān)注了具有下面特性的有序關(guān)系式：

其中N是變量集合，≤0是集合上的有序關(guān)系。有序關(guān)系初始位置上的變量在最優(yōu)解上比在基本解上更可能取不同的值。

根據(jù)實(shí)驗(yàn)獲得這種有序關(guān)系的方法是，首先要從統(tǒng)計(jì)學(xué)的觀點(diǎn)通過(guò)幾個(gè)實(shí)例對(duì)比基本解和最優(yōu)解[3]，并且估計(jì)每個(gè)變量的變化概率。然后，檢查各個(gè)優(yōu)先函數(shù)以便找到一個(gè)適合賦予具有較高變化概率變量較高優(yōu)先權(quán)的函數(shù)，最后基于優(yōu)先權(quán)值定義有序關(guān)系。

3）利用這個(gè)有序關(guān)系圍繞基本解定義一個(gè)子空間。做這件事有一個(gè)簡(jiǎn)單的方法，那就是取關(guān)系中第一個(gè)變量k作為核中元素，并且在基本解中固定其他變量的值。假設(shè)所有元素已經(jīng)根據(jù)有序關(guān)系排序，則核可以用下式表示：

而且，子空間可以通過(guò)設(shè)置xi=x~ii?C來(lái)定義。通過(guò)這個(gè)方法，這個(gè)有序關(guān)系可以隨著核的擴(kuò)展，通過(guò)的增加輕松拓展子空間。在解空間上增加約束條件可以用來(lái)定義子空間，在前面的方法中，變量固定就相當(dāng)于給等式添加了約束。因此，可以假設(shè)元素已經(jīng)根據(jù)有序關(guān)系排序，通過(guò)添加與基本解相關(guān)的約束來(lái)定義子空間。下面的篇幅中將會(huì)用到這種思想。

在多維多選擇背包問(wèn)題中，可以定義兩種有序關(guān)系而不是一種，一種是針對(duì)類(lèi)的，一種是針對(duì)每類(lèi)中元素的。因此，可以基于這兩種有序關(guān)系來(lái)確定子空間。舉個(gè)例子：根據(jù)這兩種有序關(guān)系對(duì)各類(lèi)和類(lèi)中元素都進(jìn)行排序，然后首先取k1類(lèi)子集和在這些類(lèi)中k2元素子集，其他g-k1類(lèi)子集中變量根據(jù)基本解進(jìn)行設(shè)置，設(shè)置類(lèi) i（i=1，…，k1）中其他 ni-k2元素的變量為0。這也可以從另一方面看，令和 x∈{0，1}t為一個(gè)代表MMKP整數(shù)解的t維向量。這個(gè)解用另一種方式可以表示成一個(gè)g維向量s，其中Si∈Ni·si表示類(lèi)i中該元素被選定。根據(jù)（4）式，這兩種表達(dá)形式是一致的。

將上式看作解的整數(shù)表達(dá)式，在這個(gè)表達(dá)式中，核可以被看做一個(gè)變量的子集和一個(gè)變量所能取得的值的子集。

2MMKP問(wèn)題的精確算法

這一部分主要闡述精確解決MMKP問(wèn)題的B&B算法。先是談一下算法的總體概要，接著是描述算法每一步的細(xì)節(jié)，最后分析了算法的存儲(chǔ)復(fù)雜度。

2.1 樹(shù)結(jié)構(gòu)和遍歷算法

不像以前核的大小固定，取而代之的是現(xiàn)在排列的B&B樹(shù)導(dǎo)致核會(huì)隨著遍歷而增大。假設(shè)已經(jīng)根據(jù)前部分定義的MMKP核對(duì)類(lèi)和元素進(jìn)行了排序。樹(shù)就會(huì)自然基于核中定義的排序方法就像圖1描述的那樣排列。這棵樹(shù)共有層。樹(shù)的i層對(duì)應(yīng)第（g-i+1）類(lèi)。層的i分支對(duì)應(yīng)類(lèi)的元素。第i層第j條分支的擴(kuò)展節(jié)點(diǎn)用nij來(lái)表示。圖1是B&B樹(shù)的結(jié)構(gòu)，和元素都已基于核中定義的有序關(guān)系排序，第一組元素構(gòu)成了基本解。

圖1 B&B樹(shù)的結(jié)構(gòu)Fig.1 Structure of B&B tree

算法.基于核的B&B算法

輸入.一個(gè)MMKP問(wèn)題的實(shí)例。

輸出.一個(gè)關(guān)于問(wèn)題的準(zhǔn)確可行性解或者聲明問(wèn)題的不可行性

//步驟 1：預(yù)處理

1）處理對(duì)應(yīng)的LMMKP問(wèn)題。令lmmkp為計(jì)算得到的解。

2）如果lmmkp是整數(shù)的或者不可行的，則終止算法。

3）使用lmmkp的雙值計(jì)算關(guān)聯(lián)MCKP問(wèn)題。

4）處理關(guān)聯(lián)LMCKP問(wèn)題。令lmckp為計(jì)算得到的解。同時(shí)，將上凸線存入一個(gè)雙鏈接列表。

//步驟 2：約束處理

1）基于約束的松緊程度對(duì)約束集合進(jìn)行排序。

2）去掉負(fù)系數(shù)。

3）使用lmmkp的雙值計(jì)算混合替代約束并將它添加到約束集合中。

//步驟3:核計(jì)算（根據(jù)第3部分定義的方法）

1）四舍五入lmckp獲得基本解。

2）在lmckp中使用臨界差別對(duì)類(lèi)進(jìn)行排序。

3）在lmmkp中使用檢驗(yàn)數(shù)在每一個(gè)類(lèi)中對(duì)元素進(jìn)行排序。

//步驟 4：遍歷

1）使用核來(lái)構(gòu)造樹(shù)。

2）設(shè)置當(dāng)前解狀態(tài)為null，設(shè)置X為null。

3）深度優(yōu)先遍歷樹(shù)：

①對(duì)于每一個(gè)節(jié)點(diǎn) ni，j：的應(yīng)用。 因?yàn)橛?O（ng）條線，總的i.設(shè)置 Xg-i+1=j.

ii.使用lmckp和上凸線遍歷計(jì)算上限。

iii.如果X違反某一個(gè)約束條件、或者無(wú)法推導(dǎo)出可行性解、或者計(jì)算出的上限不如當(dāng)前上限，則去除當(dāng)前節(jié)點(diǎn)。

②無(wú)論何時(shí)遍歷到樹(shù)根并且X是一個(gè)比當(dāng)前解更好的解則：

i.用替換當(dāng)前解。

ii.更新混合替代約束。

iii.使用lmckp固定變量。

4）返回當(dāng)前結(jié)果或者如果解為空則聲明問(wèn)題不可行。

對(duì)樹(shù)采用深度優(yōu)先的方式進(jìn)行遍歷。遍歷過(guò)程中，當(dāng)取ni，j的值時(shí)設(shè) Xg-i+1=j，其中 X是當(dāng)前部分解的整數(shù)表示，Xk是它的第k部分。因?yàn)楹酥械念?lèi)是根據(jù)變化概率的減少來(lái)排序的，樹(shù)末端的那些類(lèi)更可能取他們基本解的值而不是別的什么值。因此，通過(guò)這種形式的遍歷，能更好地確定類(lèi)的值，而且這種遍歷消耗很少的內(nèi)存。當(dāng)算法遍歷到樹(shù)根時(shí)，如果能找到更好的解，當(dāng)前解將被替換。注意，由于基本解是可行的，并且手動(dòng)將基本解的元素放在開(kāi)始位置，所以算法遍歷到的第一個(gè)當(dāng)前解就是基本解。

下一部分添加測(cè)深實(shí)驗(yàn)后，當(dāng)算法遍歷這棵樹(shù)時(shí)實(shí)際上就是在模仿核的擴(kuò)展操作。算法通過(guò)基本解開(kāi)始運(yùn)行，如果算法無(wú)法證明這個(gè)解的最優(yōu)性，它就會(huì)定義只有一個(gè)類(lèi)（類(lèi)1）的核并固定其他類(lèi)的變量，然后算法完全枚舉這個(gè)核推導(dǎo)出的子空間。如果用測(cè)深實(shí)驗(yàn)無(wú)法證實(shí)最優(yōu)性，算法會(huì)用下一個(gè)最有可能的類(lèi)擴(kuò)展核并且當(dāng)核外類(lèi)的變量固定時(shí)完全枚舉核的子空間，等等。很容易看出來(lái)，為了獲得最優(yōu)解，算法經(jīng)過(guò)完全搜索核空間后擴(kuò)展核仍然是根據(jù)類(lèi)的大小保持著最小擴(kuò)展屬性[4]。由于核中元素也是經(jīng)過(guò)排序的，所以算法首先檢測(cè)到得元素最有可能被納入最優(yōu)解，所以很可能快速得到最優(yōu)解。就像前面提到的，核的這種使用策略類(lèi)似B&B算法中變量和節(jié)點(diǎn)選擇的啟發(fā)式方法。

2.2 測(cè)深實(shí)驗(yàn)

為了有效地修剪子樹(shù)，用3步操作對(duì)一個(gè)節(jié)點(diǎn)做測(cè)深實(shí)驗(yàn)。如果該節(jié)點(diǎn)在這3步操作的某一步失敗了，它將被測(cè)出深度。第一個(gè)實(shí)驗(yàn)，使用混合替代約束的擴(kuò)展。令一般的0-1背包問(wèn)題為：

其中c是一個(gè)n維目標(biāo)系數(shù)向量，A是一個(gè)非負(fù)約束系數(shù)m×n矩陣，b是一個(gè)約束的右端項(xiàng)m維向量。帶有目標(biāo)函數(shù)約束的替代約束將伴隨結(jié)果出現(xiàn)在下面的約束公式中，稱為公式（5）的混合替代約束：

其中u是一個(gè)雙乘數(shù)的m維向量，LB是問(wèn)題實(shí)例的下限。這個(gè)約束可被用于變量固定和多維背包問(wèn)題中嵌套邏輯消減的產(chǎn)生。

通過(guò)觀察發(fā)現(xiàn)因?yàn)檫@個(gè)約束較緊，并且可用于固定變量，因此可以像其他約束一樣對(duì)其進(jìn)行擴(kuò)展并有效用于測(cè)深實(shí)驗(yàn)。注意在混合替代約束中，簡(jiǎn)單上限被排除掉以便獲得較強(qiáng)的約束。對(duì)于MMKP問(wèn)題，GUB約束被排除掉就是這樣的原因。如果任意節(jié)點(diǎn)都可能違反約束限制，說(shuō)明約束是有效的，并且這些節(jié)點(diǎn)可以被測(cè)深[5]。用當(dāng)前下限的值作為L(zhǎng)B，因此這個(gè)約束的右端項(xiàng)將會(huì)隨著遍歷的進(jìn)行動(dòng)態(tài)變化。

第二個(gè)實(shí)驗(yàn)中，只是簡(jiǎn)單地檢測(cè)一下一個(gè)節(jié)點(diǎn)能否推導(dǎo)出一個(gè)可行解。公式（7）幫助完成這個(gè)檢測(cè)。如果下式成立則ni，j被 做 測(cè) 深 處 理 ：

公式（7）意思是，即使累加某個(gè)約束的消耗量和剩余類(lèi)的最小消耗以至違犯了約束限制，仍然沒(méi)有能從該節(jié)點(diǎn)中導(dǎo)出可行解。在每個(gè)節(jié)點(diǎn)中，保存每個(gè)約束（包括混合替代約束）消耗量的和，因此利用父節(jié)點(diǎn)的信息我們可以逐步計(jì)算出上面的檢測(cè)結(jié)果。

最后，使用關(guān)聯(lián)LMCKP問(wèn)題計(jì)算一個(gè)節(jié)點(diǎn)的上限并與當(dāng)前值相比較。如果它小于等于當(dāng)前值，則當(dāng)前節(jié)點(diǎn)將被做測(cè)深處理。由于這一步最浪費(fèi)時(shí)間，所以將其放在后面。

2.3 變量固定和預(yù)處理

為了進(jìn)一步縮小搜索空間范圍，每當(dāng)算法使用下面的公式（8）獲得一個(gè)新值時(shí)就固定下變量。

其中UB（MMKP|xij=1）是MMKP的上限函數(shù)，附加約束為xij=1，LB中存放當(dāng)前約束的值。UB可以在上面的fathoming實(shí)驗(yàn)中計(jì)算出來(lái)。但是為了加快計(jì)算速度，對(duì)關(guān)聯(lián)LMCKP問(wèn)題使用一個(gè)較弱的上限。

算法的預(yù)處理分成兩步。第1步，從新整理約束。經(jīng)過(guò)第2個(gè)fathoming實(shí)驗(yàn)中，檢測(cè)了所有的約束，目的是找到有可能違反約束條件的節(jié)點(diǎn)。如果首先考慮較為嚴(yán)格的約束，則期待的約束檢測(cè)的個(gè)數(shù)就會(huì)減少[6]，用公式（9）計(jì)算約束的嚴(yán)格程度：

預(yù)處理第2步是，用約束式（10）替換每一個(gè)約束，該公式定義了同樣的解空間。

這會(huì)促使負(fù)的系數(shù)被去掉，并且既然能保證那些最小的值為0，那么公式（7）的計(jì)算就變得容易很多。在B&B算法在預(yù)處理階段計(jì)算下限是很普遍的，在這里沒(méi)有使用啟發(fā)式算法，因?yàn)榫拖?.1中所提到的那樣，希望該算法在遍歷過(guò)程中盡快獲得近似最優(yōu)解。

2.4 存儲(chǔ)復(fù)雜度分析

由于是深度優(yōu)先遍歷，最多有g(shù)個(gè)激活節(jié)點(diǎn)，g是類(lèi)的個(gè)數(shù)，也是樹(shù)的深度。對(duì)于每一個(gè)約束保持它的消耗數(shù)量，因此，對(duì)于整個(gè)遍歷就消耗了O（mg）的內(nèi)存。另外，對(duì)于第3種fathoming實(shí)驗(yàn)，在LMCKP的根部保持凸線計(jì)算以便進(jìn)一步的應(yīng)用。因?yàn)橛蠴（ng）條線，總的來(lái)說(shuō)，算法的空間復(fù)雜度是O（（m+n）g）。

3 計(jì)算結(jié)果

為了實(shí)地檢驗(yàn)算法的應(yīng)用效果，用C++編程、在P43.4 GHz、1 GB內(nèi)存的的計(jì)算機(jī)上運(yùn)行。并基于Coin CLP library（Coin-OR項(xiàng)目，2008）數(shù)據(jù)集處理LMMKP問(wèn)題和計(jì)算雙值。將文中的算法和 EMKP 算法（Sbihi，2007）進(jìn)行比較，EMKP 算法目前是處理MMKP公認(rèn)的最好算法。還與默認(rèn)設(shè)置下得CBC算法（Coin-OR project，2008）進(jìn)行比較，該算法是通用分支切割框架。這3種算法的可用內(nèi)存都是512 M，給定運(yùn)行時(shí)間是1個(gè)小時(shí)。

為了檢測(cè)算法的效果，不但使用通用的MMKP問(wèn)題實(shí)例，也使用自己生成的實(shí)例。Han et al.（2010）研究了怎樣生成較為困難的MMKP問(wèn)題實(shí)例。結(jié)果，他們得到了很多獲益和權(quán)重之間具有不同相互關(guān)系的實(shí)例，而且這些實(shí)例的約束的松緊程度也不同。這些實(shí)例可以在網(wǎng)站Http://enstb.org/～gsimon/resources/MMKP/上找到。所有這些實(shí)例，都有g(shù)=10，n=5，m=5。表1比較了這3種算法在這些實(shí)例上的運(yùn)行時(shí)間。Han et al.的實(shí)例基于它們的生成方法分類(lèi)。每種分類(lèi)下有100～2 000個(gè)實(shí)例。在每類(lèi)方法中，報(bào)告了該算法基于實(shí)例運(yùn)行時(shí)間的平均和標(biāo)準(zhǔn)偏差。基于核的算法標(biāo)準(zhǔn)差較小，這說(shuō)明算法在實(shí)例上運(yùn)行穩(wěn)定。事實(shí)上，基于核的算法在處理一個(gè)實(shí)例時(shí)花費(fèi)的最大時(shí)間是0.24 s，而EMKP和CBC算法卻花費(fèi)了26.22 s和1 889.41 s。比較而言，EMKP算法處理復(fù)雜實(shí)例的能力比CBC強(qiáng)，這得益于它的最佳優(yōu)先遍歷策略。但對(duì)于簡(jiǎn)單實(shí)例，CBC算法要優(yōu)于EMKP。對(duì)于當(dāng)前案例，有46 000個(gè)不同難度級(jí)別的實(shí)例，從處理結(jié)果看基于核的算法效果突出。表1是根據(jù)Han et al.提供的不同種類(lèi)的實(shí)例，以秒為單位算法的平均運(yùn)行時(shí)間 （標(biāo)準(zhǔn)偏差）。每種至少包含100個(gè)實(shí)例。

表1 實(shí)例的平均運(yùn)行時(shí)間Tab.1 Average running time of instances

4 結(jié) 論

文中論述了一種精確解決多維多選擇背包問(wèn)題（MMKP）的B&B算法。首先為MMKP問(wèn)題指明一個(gè)核，就是把關(guān)聯(lián)LMCKP問(wèn)題的解作為基本點(diǎn)，同時(shí)根據(jù)傾斜變換線和檢驗(yàn)數(shù)分別對(duì)問(wèn)題的類(lèi)和元素進(jìn)行排序，依次來(lái)定義這個(gè)核。是根據(jù)核中定義的排列順序來(lái)生成B&B樹(shù)，樹(shù)的遍歷采用深度優(yōu)先算法。修剪子樹(shù)需要有3個(gè)步驟：檢測(cè)混合替代約束；檢測(cè)可行性；檢測(cè)由關(guān)聯(lián)LMCKP輔助下計(jì)算得到的上限。我們還使用了變量固定和約束排序等輔助手段以提高算法的性能。計(jì)算結(jié)果顯示，基于核的算法在處理MMKP問(wèn)題時(shí)性能優(yōu)于以往任何算法，特別是對(duì)于無(wú)關(guān)聯(lián)和少約束實(shí)例。

[1]Wilbaut C，Hanafi S.A survey of effective heuristics and their application to a variety of knapsack problems[J].IMA Journal of Management Mathematics，2008（19）:227-244.

[2]Boyer V，Elkihel M，Baz D.Heuristics for the 0-1 multidimensional knapsack problem[J].European Journal of Operational Research，2009，199（3）:658-664.

[3]Tamir A.New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems[J]，Operations Research Letters，2009，37（5）:303-306.

[4]Hsu C H，Tsou C S，Yu F J.Multicriteria tradeoffs in inventory control using memetic particle swarm optimization[J].International Journal of Innovative Computing，Information and Control，2009，5（11-A）:3755-3768.

[5]劉文濤，胡家寶.求解0-1背包問(wèn)題的改進(jìn)排擠遺傳算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（6）:102-108.LIU Wen-tao，HU Jia-bao.Improved crowding genetic algorithm for 0-1 knapsack problem[J].Computer Engineering and Design，2011，32（6）:102-108.

[6]鄧長(zhǎng)壽，趙秉巖，梁昌勇.混合二進(jìn)制差異演化算法解0-1背包問(wèn)題[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（8）:220-226.DENG Chang-shou， ZHAO Bing-yan， LIANG Chang-yong.Hybrid binary differential evolution algorithm for 0-1 knapsack problem[J].Computer Engineering and Design， 2010，31（8）:220-226.