A branch-and-cut algorithm for the Winner Determination Problem

The Winner Determination Problem is the problem of maximizing the benefit when bids can be made on a group of items. In this paper, we consider the set packing formulation of the problem, study its polyhedral structure and then propose a new and tighter formulation. We also present new valid inequalities which are generated by exploiting combinatorial auctions peculiarities. Finally, we implement a branch-and-cut algorithm which shows its efficiency in a big number of instances.