组合拍卖竞胜标确定问题图论解决方案

黄丽+李庆

摘要：研究了组合拍卖中的竞胜标确定问题，利用归约手段巧妙地将竞胜标确定问题转化为图论的最大权重团问题，提供了转化的具体解决方案。该方案拓宽了组合拍卖竞胜标问题的求解思路，克服和改善了计算复杂度，促进了组合拍卖在电子商务中的实际应用。

关键词：竞胜标问题，组合拍卖，最大权重团，组合优化

中图分类号：F27文献标识码：A文章编号：16723198（2015）04006902

1竞胜标确定问题分析

1.1竞胜标确定问题模型的构建

组合拍卖竞胜标确定问题（WDP）就是以拍卖方收益或者效用最大化为目标，以拍卖商品数量为约束，根据竞胜标所有投标确定竞胜标集合，以及确定对应资源配置的组合优化问题。

假设待拍卖的商品集合定义为M={1，2，…，m}，提交的竞标申请集合定义为B={B1，B2，…，Bn}，每个竞标申请由竞标产品组合和价格的二元组定义，且每个竞标申请都可以对M中的任意商品组合进行投标，即Bi=，其中Si表示竞标的商品组合（Si∈M），Pi表示竞拍申请中投标者对物品组合Si的整体标价。根据基础定义，设B为n×m的0＼1矩阵，Bij表示竞标申请i和竞标商品j之间的关联关系，当竞标商品j∈Si时，Bij=1，反之Bij=0。设布尔变量xi，表示第i个竞标申请是否被接受，如果被接受，则xi=1，反之xi=0。因此，组合拍卖竞胜标确定问题建模如下：

Maxni=0Pixi（1）

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

xi∈{0，1}（3）

其中，算式（1）为该模型的目标函数，表示计算竞胜标的标价和，即拍卖方利益。（2）为约束条件，表示在竞胜标组合中资源无冲突分配，保证每个商品最多只能被一个竞拍申请投标。WDP问题就是为了求解模型的最优解或近似最优解，即寻找最优拍卖组合配置使得收益最大化的问题。

1.2竞胜标确定问题求解策略分析

从问题入手，综合分析组合拍卖问题的特征，结合计算复杂性的理论基础，发现最大权重团问题与组合拍卖竞胜标问题有很大的相似性，运用归约技术手段可以将组合拍卖WDP问题转化成图论里的最大权重团问题，通过禁忌搜索算法的求解寻求WDP问题的最优解，解决过程如图所示：

图1组合拍卖竞胜标确定问题求解流程图最大团问题（MCP）又称为最大独立集问题，是图论中一个经典的组合优化问题，在图像处理、通信网络设计、统计物理等领域具有广泛的应用前景。组合拍卖WDP问题已经被Rothkopf等人证明为NP（Non-deterministic Polynomial）问题，而在Karp的开创性论文中也证明了最大团问题是一个NP问题，最大权重团问题作为最大团问题的一个衍生问题，自然也是一个NP问题，所以组合拍卖WDP问题和最大权重团问题之间存在约化的可能性。

2竞胜标确定问题与最大权重团问题的转化

设定G=（V，E）为一个无向图，其中V={1，2，…，n}是图G的非空顶点集，EV×V是图G的边集。对任意两个相连的顶点u，v∈U，有无序对（u，v）∈E，则U是G的子集。当U不被其他任意一个子集所包含，则子集U就是图G的团。G的最大团是指G中所含顶点数最多的团。

最大权重团问题（MWCP）是MCP的衍生问题，给定无向图G=（V，E，W），其中W为权重函数，作为图G的一个团U，W（U）=i∈UWi。最大权重问题就是找到一个有最大权重的团U*。

例如：对于一个给定的组合拍卖WDP问题的实例B={B1，B2，…，Bn}，其中Bi=（i=1，2，…，n），可以通过以下约化方案将其转化为加权最大团问题实例G=（V，E，W）。

（1）将WDP问题中的每一个竞胜申请抽象为加权最大团问题的图顶点，即：对每一个Bi，定义一个权重为Pi的顶点i∈V与之对应，这样可得到图G的顶点V={1，…，n}，Wi=Pi；

（2）根据WDP问题中竞标申请的产品组合的冲突关系来定义边：如果两个竞标申请之间有共同的竞标产品，那么这两个竞标申请可表示成图中两个顶点之间无连接，即这两个标不能同时被选择；反之，如果无共同竞标产品，那么这两个竞标申请可表示成两个顶点之间有连接，即这两个标可以同时被选择。用Eij=1表示顶点i和顶点j之间有连接，Eij=0表示顶点i和顶点j之间无连接，则

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

0，其他

通过以上步骤的转化，就可以把组合拍卖WDP问题转化为最大权重团问题，WDP的目标函数从组合拍卖竞胜标的拍卖方收益最大化问题可以转化为最大权重团问题的团的权重最大化，用来解决最大权重团问题的算法也就可以用来解决组合拍卖WDP问题。两个问题的具体约化对应关系如下表所示：

表1约化对应关系表

约化对应关系组合拍卖WDP问题最大权重团问题相关参数BiVSi∩SjEijPiW求解结果竞胜标集合最大权重团的顶点集目标函数拍卖方收益团解的权重3组合拍卖竞胜标确定问题的约化实例测试

给定一个含有8个竞标产品，7个竞标申请组合的拍卖竞胜标确定问题实例如下：

根据约化方案，构造最大权重团问题的基本图G的过程如下：

（1）实例中的7个竞标者约化为图的7个顶点，各顶点权重如下表所示：

表2图G的顶点权重分配表

顶点编号1234567权重25202020203020（2）竞标申请的产品组合的冲突关系约化为图的边，如：B1与B4都对商品4进行了竞标，则顶点1和顶点4之间无连接；B1与B6都对商品2、8进行了竞标，则顶点1和顶点6之间无连接，等等，通过分析竞标者之间的冲突关系，可以得到图G的边集合：

表3图G的边集合（1：有连接；0：无连接）

Vj

Vi12345671-11010021-11001311-10104011-11051001-10600111-17010001-这样，可以得到如下的基本图G：

图2转化基本图G

（其中1-25等标号表示：顶点编号-顶点权重）假设约化后最大权重团问题求得加权最大团为<3，4，6>，团的权重为70，则说明组合拍卖竞胜标确定问题中的竞胜标应为B3、B4和B6，拍卖方收益为70。通过约化，使得所有用来解决最大权重团问题的解决方法都可以用来解决组合拍卖问题。

4结语

针对电子商务环境下组合拍卖竞胜标确定问题（WDP），对其本质特点进行分析，发现WDP问题与图论里最大权重团问题具有相似特性，提出利用归约技术将WDP问题的求解转化为最大权重团问题的求解，能在短时间内求出WDP问题的最优解和满意近似解，具较高效率和质量，适用较大规律的拍卖竞胜标确定问题。

参考文献

[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]傅丽芳，冯玉强.基于关联规则分析的组合拍卖竞胜标决定算法[J].系统管理学报，2008，（5）.

[8]张爱君，秦新强，龚春琼.求解最大割问题的多启动禁忌搜索算法[J].计算机应用，2014，34（5）：12711274.endprint