A fast approximation algorithm for solving the complete set packing problem
A fast approximation algorithm for solving the complete set packing problem
复制标题
DOI：
10.1016/j.ejor.2014.01.024
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Tri-Dung Nguyen
中科院分区：
文献类型：
--
作者：
Tri-Dung Nguyen
研究了可行子集族可能包含所有可能的对象组合的完备集填充问题。这种设置出现在组合拍卖（用于选择最佳出价）和合作博弈论（用于寻找最佳联盟结构）等应用中。虽然集合包装问题已经在文献中得到了很好的研究，其中精确和近似算法可以解决具有多达数百个对象和数千个可行子集的非常大的实例，但这些方法不能扩展到CSPP，因为可行子集的数量是指数级的。将CSPP制定为MILP并直接求解，例如使用CPLEX，对于超过20个对象的问题是不可能的。我们提出了一种新的CSPP数学公式，它直接导致了一种寻找可行集包装（上界）的有效算法。我们还提出了一个新的公式来寻找与LP松弛相比更紧的下界，并开发了一种求解相应的大规模MILP的有效方法。我们用频谱拍卖中的赢家确定问题、联盟技能博弈中的联盟结构生成问题以及文献中出现的许多其他模拟问题来测试该算法。
We study the complete set packing problem (CSPP) where the family of feasible subsets may include all possible combinations of objects. This setting arises in applications such as combinatorial auctions (for selecting optimal bids) and cooperative game theory (for finding optimal coalition structures). Although the set packing problem has been well-studied in the literature, where exact and approximation algorithms can solve very large instances with up to hundreds of objects and thousands of feasible subsets, these methods are not extendable to the CSPP since the number of feasible subsets is exponentially large. Formulating the CSPP as an MILP and solving it directly, using CPLEX for example, is impossible for problems with more than 20 objects. We propose a new mathematical formulation for the CSPP that directly leads to an efficient algorithm for finding feasible set packings (upper bounds). We also propose a new formulation for finding tighter lower bounds compared to LP relaxation and develop an efficient method for solving the corresponding large-scale MILP. We test the algorithm with the winner determination problem in spectrum auctions, the coalition structure generation problem in coalitional skill games, and a number of other simulated problems that appear in the literature.