一种求解组合拍卖胜者决定问题的局部搜索算法

发布时间：2018-10-29 22:29

【摘要】：拍卖是一种竞价的买卖方式。传统的拍卖是将特定物品或财产权利转让给最高应价者。组合拍卖与传统拍卖不同,组合拍卖允许投标人在多个拍卖品中自由组合,给出总价格作为出价进行竞标,而不对其中物品单独给出价格。组合拍卖在电子商务、空间分配、云计算等领域均有应用。而胜者决定问题又是组合拍卖领域的核心问题之一,有着重要的理论意义和实际应用价值。然而,胜者决定问题已经在理论上被证明是NP难问题,目前找不到多项式时间内求解的精确算法。精确算法虽然能证明输出解的最优性,但随着问题规模的扩大,它需要的求解时间将呈指数型增长,难以在可接受的时间里应对复杂的大规模实例。这类NP问题通常都需要依靠启发式算法进行近似求解,以达到可以在实际中应用的目的。局部搜索作为一类重要的启发式算法,具有简洁和高效的特点。局部搜索算法在多种NP问题求解中都有极好的表现。尽管它无法像精确算法一样给出最优解并证明其最优性,但在大规模实例上,局部搜索算法通常可以在更短时间内给出高质量的近似解。胜者决定问题在实际应用中十分重要,受到了很多关注。本文将设计和实现一种求解胜者决定问题的局部搜索算法,用于在短时间内求解较大规模的实例并使解质量尽可能提高。本文中提出的算法名为WDPLS。WDPLS基于一种高效且简明的局部搜索框架,并配有三种技术,分别为格局检测技术、自由出价技术和伪并列技术。格局检测技术是一种十分高效的用于局部搜索算法的防回溯策略。针对胜者决定问题,我们为WDPLS设计了适合该问题的格局定义,阻止算法贪婪搜索时发生回溯。在算法进行搜索时,可能会出现自由出价。这是一种特殊的出价,WDPLS优先选择自由出价以快速提升解质量。此外,在搜索过程中可能会遇到质量(得分)非常相似的落败出价。对于这些出价,伪并列技术阻止了算法过度贪婪地选择最高得分出价,从而为其他高质量出价提供了被选可能,进一步增加了解的多样性。在LG数据集上的大量实验表明,WDPLS在求解质量和求解时间上均领先于已发表的先进算法。特别地,尽管WDPLS在本文实验中被实现为单线程程序,但其在与多线程实现的算法CARA及商业求解器CPLEX相比时仍具有明显优势。同时,实验也展示出,以上三种主要技术都对WDPLS的性能有正面影响,证明了它们的有效性。
[Abstract]:An auction is a form of bidding. The traditional auction is the transfer of specific goods or property rights to the highest bidder. Combinatorial auction is different from traditional auction. Combinatorial auction allows bidders to combine freely in multiple auction items and give the total price as a bid instead of giving the price of the items. Combinatorial auctions have applications in e-commerce, space allocation, cloud computing and so on. The decision of winner is one of the core problems in the field of combinatorial auction, which has important theoretical significance and practical application value. However, the winner decision problem has been proved to be a NP problem in theory, and no exact algorithm can be found to solve it in polynomial time. Although the exact algorithm can prove the optimality of the output solution, with the expansion of the scale of the problem, the solving time it needs will increase exponentially, so it is difficult to deal with complex large-scale examples in acceptable time. This kind of NP problem usually needs to be solved by heuristic algorithm, so that it can be applied in practice. As an important heuristic algorithm, local search is simple and efficient. Local search algorithms have excellent performance in solving various NP problems. Although it can not give the optimal solution and prove its optimality just like the exact algorithm, the local search algorithm can usually give a high quality approximate solution in a shorter time. The winner decision problem is very important in practical application and has received much attention. In this paper, we design and implement a local search algorithm to solve the winner decision problem, which is used to solve large scale examples in a short time and to improve the quality of the solution as much as possible. The proposed algorithm named WDPLS.WDPLS is based on an efficient and concise local search framework with three techniques: pattern detection free bid and pseudo-juxtaposition. Pattern detection is a very efficient backtracking strategy for local search algorithms. For the winner decision problem, we design a pattern definition for WDPLS to prevent the backtracking of greedy search algorithm. Free bids may appear when the algorithm searches. This is a special bid, WDPLS preferred free bid to quickly improve the quality of the solution. In addition, the search process may encounter quality (score) very similar defeat bid. For these bids, pseudo-juxtaposition prevents the algorithm from choosing the highest score bid too greedily, thus providing other high-quality bids with the possibility of being selected, further increasing the diversity of understanding. A large number of experiments on LG datasets show that WDPLS is ahead of the published advanced algorithms in solving quality and time. In particular, although WDPLS is implemented as a single-threaded program in our experiments, it still has a significant advantage over the multithreaded algorithm CARA and the commercial solver CPLEX. At the same time, the experiments also show that the above three main technologies have a positive effect on the performance of WDPLS, which proves their effectiveness.
【学位授予单位】：东北师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：F713.359;TP18

【相似文献】