基于线性结构的逆向组合拍卖算法研究

Research of reverse combinational auction algorithm based on linear structure

对逆向组合拍卖的拍卖模型和WDP问题进行了研究,报告了当前逆向组合拍卖的研究现状,分析了对称关联价值模型的基本性质。结合对称关联价值模型分析了WDP的形式化描述,在此基础上提出了基于线性结构的饱和分割区近似算法(LISAPA)。该算法避免了项目组合树的建立,并且可以在构造过程中直接由局部最优解扩展到全局最优解,从而显著的提高构造效率。实验结果表明,当拍卖项目组合数大于拍卖项目数时,该算法能够解决中标者确定问题,并且有较好的达优率。

The auction model and WDP of reverse combinational auction are studied, the current study situation of reverse combinatorial auction is reported, and the basic nature of symmetrical associated value model is analyzed. After the formalization description of WDP is analyzed by symmetrical associated value model, an approximate algorithm called LISAPA for saturation partition is presented based linear structure. The algorithm avoided the construction of items combination tree, and get the global optimun solution from local optimum solution in construction process directly, which improved the algorithm＇ s efficiency remarkably. Experimental results show that the algorithm can resolve the WDP and have better preciseness ratio when the number of permitted auction combinations is greater than the number of auction item collection.