Computationally-efficient winner determination for mixed multi-unit combinatorial auctions

Mixed Multi-Unit Combinatorial Auctions offer a high potential to be employed for the automated assembly of supply chains of agents offering goods and services. Their winner determination problem is an NP-hard problem that can be mapped into an integer program. Nonetheless, the computational cost of the current solution hinders the application of mixed multi-unit combinatorial auctions to realistic scenarios. In this paper we propose a new integer program for mixed multi-unit combinatorial auctions that severely simplifies the problem by taking advantage of the topological characteristics of the winner determination problem. Furthermore, we provide empirical evidence showing that the new IP allows to cope with much larger supply chain formation scenarios.