A Non-Exact Approach and Experiment Studies on the Combinatorial Auction Problem
A Non-Exact Approach and Experiment Studies on the Combinatorial Auction Problem
复制标题
组合拍卖问题的非精确方法和实验研究
DOI：
10.1109/hicss.2005.34
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Yi Zhu
中科院分区：
文献类型：
--
作者：
Yunsong Guo;A. Lim;B. Rodrigues;Yi Zhu
在本文中，我们将组合拍卖式经纪问题作为设定的包装问题，并使用混合本地移动应用模拟的退火启发式，以解决该问题。我们研究了解决问题的现有精确和非精确方法，并分析了这些方法的性能。我们使用CATS测试集和测试用例比较了启发式方法CPLEX 8.0求解器和另一种非脱颖而出的算法Casanova，认为比猫更困难。结果表明，该方法与CPLEX 8.0具有竞争力，并且与CPLEX和Casanova相比，在使用其他实例时，该方法分别获得了CATS病例的最佳解决方案，最高可达15％和40％的溶液。
In this paper we formulate a combinatorial auction brokering problem as a set packing problem and apply a simulated annealing heuristic with hybrid local moves to solve the problem. We study the existing exact and non-exact approaches to the problem and analyze the performance of those approaches. We compared our heuristic with the leading exact method CPLEX 8.0 solver and another non-exact algorithms Casanova using both the CATS test sets and test cases believed more difficult than CATS. Results show that the method is competitive with CPLEX 8.0 and obtains near optimal solutions for the CATS cases and up to 15% and 40% better solutions compared with CPLEX and Casanova, respectively, when the other instances were used.