%0 Conference Proceedings
%T Parallelisation and Application of AD 3 as a Method for Solving Large Scale Combinatorial Auctions
%+ IIIA-CSIC
%+ Universitat Autònoma de Barcelona = Autonomous University of Barcelona = Universidad Autónoma de Barcelona (UAB)
%+ Department of Computer Architecture & Operating Systems (CAOS)
%A Cruz-Mencia, Francisco
%A Cerquides, Jesus
%A Espinosa, Antonio
%A Moure, Juan, Carlos
%A Rodriguez-Aguilar, Juan, A.
%Z Part 4: Agent-Oriented Techniques
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 17th International Conference on Coordination Languages and Models (COORDINATION)
%C Grenoble, France
%Y Tom Holvoet
%Y Mirko Viroli
%I Springer International Publishing
%3 Coordination Models and Languages
%V LNCS-9037
%P 153-168
%8 2015-06-02
%D 2015
%R 10.1007/978-3-319-19282-6_10
%K Combinatorial auctions
%K Large-scale coordination
%K Large-scale optimisation
%K Linear programming
%Z Computer Science [cs]
%Z Computer Science [cs]/Networking and Internet Architecture [cs.NI]Conference papers
%X Auctions, and combinatorial auctions (CAs), have been successfully employed to solve coordination problems in a wide range of application domains. However, the scale of CAs that can be optimally solved is small because of the complexity of the winner determination problem (WDP), namely of finding the bids that maximise the auctioneer’s revenue. A way of approximating the solution of a WDP is to solve its linear programming relaxation. The recently proposed Alternate Direction Dual Decomposition algorithm (AD 3) has been shown to efficiently solve large-scale LP relaxations. Hence, in this paper we show how to encode the WDP so that it can be approximated by means of AD 3. Moreover, we present PAR-AD 3, the first parallel implementation of AD 3. PAR-AD 3 shows to be up to 12.4 times faster than CPLEX in a single-thread execution, and up to 23 times faster than parallel CPLEX in an 8-core architecture. Therefore PAR-AD 3 becomes the algorithm of choice to solve large-scale WDP LP relaxations for hard instances. Furthermore, PAR-AD 3 has potential when considering large-scale coordination problems that must be solved as optimisation problems.
%G English
%Z TC 6
%Z WG 6.1
%2 https://inria.hal.science/hal-01774939/document
%2 https://inria.hal.science/hal-01774939/file/978-3-319-19282-6_10_Chapter.pdf
%L hal-01774939
%U https://inria.hal.science/hal-01774939
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-WG
%~ IFIP-TC6
%~ IFIP-WG6-1
%~ IFIP-COORDINATION
%~ IFIP-DISCOTEC
%~ IFIP-LNCS-9037