基于核的MMKP問題算法研究

鄭曉月

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

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

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

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

1MMKP核的確定

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

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

不幸的是，在解決背包問題之前這樣的核是沒辦法找到的，必須找一種方法來獲得一種近似核。根據(jù)實驗，可以通過

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

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

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

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

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

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

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

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

2MMKP問題的精確算法

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

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

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

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

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

輸入.一個MMKP問題的實例。

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

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

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

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

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

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

//步驟 2：約束處理

1）基于約束的松緊程度對約束集合進行排序。

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

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

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

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

2）在lmckp中使用臨界差別對類進行排序。

3）在lmmkp中使用檢驗數(shù)在每一個類中對元素進行排序。

//步驟 4：遍歷

1）使用核來構(gòu)造樹。

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

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

①對于每一個節(jié)點 ni，j：的應(yīng)用。 因為有 O（ng）條線，總的i.設(shè)置 Xg-i+1=j.

ii.使用lmckp和上凸線遍歷計算上限。

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

②無論何時遍歷到樹根并且X是一個比當前解更好的解則：

i.用替換當前解。

ii.更新混合替代約束。

iii.使用lmckp固定變量。

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

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

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

2.2 測深實驗

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

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

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

通過觀察發(fā)現(xiàn)因為這個約束較緊，并且可用于固定變量，因此可以像其他約束一樣對其進行擴展并有效用于測深實驗。注意在混合替代約束中，簡單上限被排除掉以便獲得較強的約束。對于MMKP問題，GUB約束被排除掉就是這樣的原因。如果任意節(jié)點都可能違反約束限制，說明約束是有效的，并且這些節(jié)點可以被測深[5]。用當前下限的值作為LB，因此這個約束的右端項將會隨著遍歷的進行動態(tài)變化。

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

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

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

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

為了進一步縮小搜索空間范圍，每當算法使用下面的公式（8）獲得一個新值時就固定下變量。

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

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

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

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

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

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

3 計算結(jié)果

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

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

表1 實例的平均運行時間Tab.1 Average running time of instances

4 結(jié) 論

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

[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背包問題的改進排擠遺傳算法[J].計算機工程與設(shè)計，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]鄧長壽，趙秉巖，梁昌勇.混合二進制差異演化算法解0-1背包問題[J].計算機工程與設(shè)計，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.