A hybrid exact algorithm for complete set partitioning

摘要

In the Complete Set Partitioning problem we are given a finite set of elements where every subset is associated with a value, and the goal is to partition this set into disjoint subsets so as to maximise the sum of subset values. This abstract problem captures the Coalition Structure Generation problem in cooperative games in characteristic function form, where each subset, or coalition, of agents can make a profit when working together, and the goal is to partition the set of agents into coalitions to maximise the total profit. It also captures the special case of the Winner Determination problem in combinatorial auctions, where bidders place bids on every possible bundle of goods, and the goal is to find an allocation of goods to bidders that maximises the profit of the auctioneer.