Paving the Way for Large-Scale Combinatorial Auctions

The Winner Determination Problem (WDP) in Combinatorial Auctions comes up in a wide range of applications. Linear Programming (LP) relaxations are a standard method for approximating combinatorial optimisation problems. In this paper we propose how to encode the WDP so that it can be approximated with AD 3. Moreover, we contribute with P AR-AD 3 , the first parallel implementation of AD 3. We show that while AD 3 is up to 4.6 times faster than CPLEX in a single-thread execution, P AR-AD 3 is up to 23 times faster than parallel CPLEX in an 8-core architecture.