A clique-based exact method for optimal winner determination in combinatorial auctions

• Winner determination (WDP) is a key problem in combinatorial auctions with many applications.
• We develop a clique-based branch-and-bound algorithm for the WDP.
• We show extensive computational results on three test suites of popular WDP benchmark instances.
• We compare the performance with the general CPLEX 12.4 solver.
• We demonstrate both approaches complement each other.

Given a set of items to sell and a set of combinatorial bids, the Winner Determination Problem (WDP) in combinatorial auctions is to determine an allocation of items to bidders such that the auctioneer’s revenue is maximized while each item is allocated to at most one bidder. WDP is at the core of numerous relevant applications in multi-agent systems, e-commerce and many others. We develop a clique-based branch-and-bound approach for WDP which relies on a transformation of WDP into the maximum weight clique problem. To ensure the efficiency of the proposed search algorithm, we introduce specific bounding and branching strategies using a dedicated vertex coloring procedure and a specific vertex sorting technique. We assess the performance of the proposed algorithm on a large collection of benchmark instances in comparison with the CPLEX 12.4 solver and other approaches. Computational results show that this clique-based method constitutes a valuable and complementary approach for WDP relative to the existing methods.