組合拍賣競勝標確定問題圖論解決方案

黃麗+李慶

摘要：研究了組合拍賣中的競勝標確定問題，利用歸約手段巧妙地將競勝標確定問題轉(zhuǎn)化為圖論的最大權(quán)重團問題，提供了轉(zhuǎn)化的具體解決方案。該方案拓寬了組合拍賣競勝標問題的求解思路，克服和改善了計算復(fù)雜度，促進了組合拍賣在電子商務(wù)中的實際應(yīng)用。

關(guān)鍵詞：競勝標問題，組合拍賣，最大權(quán)重團，組合優(yōu)化

中圖分類號：F27文獻標識碼：A文章編號：16723198（2015）04006902

1競勝標確定問題分析

1.1競勝標確定問題模型的構(gòu)建

組合拍賣競勝標確定問題（WDP）就是以拍賣方收益或者效用最大化為目標，以拍賣商品數(shù)量為約束，根據(jù)競勝標所有投標確定競勝標集合，以及確定對應(yīng)資源配置的組合優(yōu)化問題。

假設(shè)待拍賣的商品集合定義為M={1，2，…，m}，提交的競標申請集合定義為B={B1，B2，…，Bn}，每個競標申請由競標產(chǎn)品組合和價格的二元組定義，且每個競標申請都可以對M中的任意商品組合進行投標，即Bi=，其中Si表示競標的商品組合（Si∈M），Pi表示競拍申請中投標者對物品組合Si的整體標價。根據(jù)基礎(chǔ)定義，設(shè)B為n×m的0＼1矩陣，Bij表示競標申請i和競標商品j之間的關(guān)聯(lián)關(guān)系，當競標商品j∈Si時，Bij=1，反之Bij=0。設(shè)布爾變量xi，表示第i個競標申請是否被接受，如果被接受，則xi=1，反之xi=0。因此，組合拍賣競勝標確定問題建模如下：

Maxni=0Pixi（1）

ni=0Bijxi≤1，j∈{1，2，…，m}（2）

xi∈{0，1}（3）

其中，算式（1）為該模型的目標函數(shù)，表示計算競勝標的標價和，即拍賣方利益。（2）為約束條件，表示在競勝標組合中資源無沖突分配，保證每個商品最多只能被一個競拍申請投標。WDP問題就是為了求解模型的最優(yōu)解或近似最優(yōu)解，即尋找最優(yōu)拍賣組合配置使得收益最大化的問題。

1.2競勝標確定問題求解策略分析

從問題入手，綜合分析組合拍賣問題的特征，結(jié)合計算復(fù)雜性的理論基礎(chǔ)，發(fā)現(xiàn)最大權(quán)重團問題與組合拍賣競勝標問題有很大的相似性，運用歸約技術(shù)手段可以將組合拍賣WDP問題轉(zhuǎn)化成圖論里的最大權(quán)重團問題，通過禁忌搜索算法的求解尋求WDP問題的最優(yōu)解，解決過程如圖所示：

圖1組合拍賣競勝標確定問題求解流程圖最大團問題（MCP）又稱為最大獨立集問題，是圖論中一個經(jīng)典的組合優(yōu)化問題，在圖像處理、通信網(wǎng)絡(luò)設(shè)計、統(tǒng)計物理等領(lǐng)域具有廣泛的應(yīng)用前景。組合拍賣WDP問題已經(jīng)被Rothkopf等人證明為NP（Non-deterministic Polynomial）問題，而在Karp的開創(chuàng)性論文中也證明了最大團問題是一個NP問題，最大權(quán)重團問題作為最大團問題的一個衍生問題，自然也是一個NP問題，所以組合拍賣WDP問題和最大權(quán)重團問題之間存在約化的可能性。

2競勝標確定問題與最大權(quán)重團問題的轉(zhuǎn)化

設(shè)定G=（V，E）為一個無向圖，其中V={1，2，…，n}是圖G的非空頂點集，EV×V是圖G的邊集。對任意兩個相連的頂點u，v∈U，有無序?qū)Γ╱，v）∈E，則U是G的子集。當U不被其他任意一個子集所包含，則子集U就是圖G的團。G的最大團是指G中所含頂點數(shù)最多的團。

最大權(quán)重團問題（MWCP）是MCP的衍生問題，給定無向圖G=（V，E，W），其中W為權(quán)重函數(shù)，作為圖G的一個團U，W（U）=i∈UWi。最大權(quán)重問題就是找到一個有最大權(quán)重的團U*。

例如：對于一個給定的組合拍賣WDP問題的實例B={B1，B2，…，Bn}，其中Bi=（i=1，2，…，n），可以通過以下約化方案將其轉(zhuǎn)化為加權(quán)最大團問題實例G=（V，E，W）。

（1）將WDP問題中的每一個競勝申請抽象為加權(quán)最大團問題的圖頂點，即：對每一個Bi，定義一個權(quán)重為Pi的頂點i∈V與之對應(yīng)，這樣可得到圖G的頂點V={1，…，n}，Wi=Pi；

（2）根據(jù)WDP問題中競標申請的產(chǎn)品組合的沖突關(guān)系來定義邊：如果兩個競標申請之間有共同的競標產(chǎn)品，那么這兩個競標申請可表示成圖中兩個頂點之間無連接，即這兩個標不能同時被選擇；反之，如果無共同競標產(chǎn)品，那么這兩個競標申請可表示成兩個頂點之間有連接，即這兩個標可以同時被選擇。用Eij=1表示頂點i和頂點j之間有連接，Eij=0表示頂點i和頂點j之間無連接，則

Eij=1，Si∩Sj=；i，j∈{1，…，n}

0，其他

通過以上步驟的轉(zhuǎn)化，就可以把組合拍賣WDP問題轉(zhuǎn)化為最大權(quán)重團問題，WDP的目標函數(shù)從組合拍賣競勝標的拍賣方收益最大化問題可以轉(zhuǎn)化為最大權(quán)重團問題的團的權(quán)重最大化，用來解決最大權(quán)重團問題的算法也就可以用來解決組合拍賣WDP問題。兩個問題的具體約化對應(yīng)關(guān)系如下表所示：

表1約化對應(yīng)關(guān)系表

約化對應(yīng)關(guān)系組合拍賣WDP問題最大權(quán)重團問題相關(guān)參數(shù)BiVSi∩SjEijPiW求解結(jié)果競勝標集合最大權(quán)重團的頂點集目標函數(shù)拍賣方收益團解的權(quán)重3組合拍賣競勝標確定問題的約化實例測試

給定一個含有8個競標產(chǎn)品，7個競標申請組合的拍賣競勝標確定問題實例如下：

根據(jù)約化方案，構(gòu)造最大權(quán)重團問題的基本圖G的過程如下：

（1）實例中的7個競標者約化為圖的7個頂點，各頂點權(quán)重如下表所示：

表2圖G的頂點權(quán)重分配表

頂點編號1234567權(quán)重25202020203020（2）競標申請的產(chǎn)品組合的沖突關(guān)系約化為圖的邊，如：B1與B4都對商品4進行了競標，則頂點1和頂點4之間無連接；B1與B6都對商品2、8進行了競標，則頂點1和頂點6之間無連接，等等，通過分析競標者之間的沖突關(guān)系，可以得到圖G的邊集合：

表3圖G的邊集合（1：有連接；0：無連接）

Vj

Vi12345671-11010021-11001311-10104011-11051001-10600111-17010001-這樣，可以得到如下的基本圖G：

圖2轉(zhuǎn)化基本圖G

（其中1-25等標號表示：頂點編號-頂點權(quán)重）假設(shè)約化后最大權(quán)重團問題求得加權(quán)最大團為<3，4，6>，團的權(quán)重為70，則說明組合拍賣競勝標確定問題中的競勝標應(yīng)為B3、B4和B6，拍賣方收益為70。通過約化，使得所有用來解決最大權(quán)重團問題的解決方法都可以用來解決組合拍賣問題。

4結(jié)語

針對電子商務(wù)環(huán)境下組合拍賣競勝標確定問題（WDP），對其本質(zhì)特點進行分析，發(fā)現(xiàn)WDP問題與圖論里最大權(quán)重團問題具有相似特性，提出利用歸約技術(shù)將WDP問題的求解轉(zhuǎn)化為最大權(quán)重團問題的求解，能在短時間內(nèi)求出WDP問題的最優(yōu)解和滿意近似解，具較高效率和質(zhì)量，適用較大規(guī)律的拍賣競勝標確定問題。

參考文獻

[1]H.H.Hoos， C.Boutilier， Solving combinatorial auctions using stochastic local search[C].In Proceedings of the 17th National Conference on Artificial Intelligence，2000：2229.

[2]G.Ausiello， A.DAtri， M.Protasi， Structure preserving reductions among convex optimization problems[J]. Journal of Computer and System Science，1980，（21）：136153.

[3]D.Boughaci， B.Benhamou， H.Drias， Local Search Methods for the optimal winner determination problem[J].Soft Computing，2009，13（89）：905917 .

[4]Aleksandar Pekec，Michael Rothkopf H.Combinatorial auction designs[J].Management Science，2003，49（11）：14851503.

[5]Sven de Vries，Rakesh Vohra V.Combinatorial auctions：a survey[J].Incorms Journal on Computing，2003，15，（3）：284309.

[6]Q.Sandhom， S.Suri， BOB：Improved winner determination in combinatorial auctions and generalizations[J].Artificial Intelligence， 2003，145（12）：3348.

[7]傅麗芳，馮玉強.基于關(guān)聯(lián)規(guī)則分析的組合拍賣競勝標決定算法[J].系統(tǒng)管理學報，2008，（5）.

[8]張愛君，秦新強，龔春瓊.求解最大割問題的多啟動禁忌搜索算法[J].計算機應(yīng)用，2014，34（5）：12711274.endprint