English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/130923
Compartir / Impacto:
Estadísticas
Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Título

Parallelisation and application of AD3 as a method for solving large scale combinatorial auctions

AutorCruz-Mencia, Francisco; Cerquides, Jesús; Espinosa, Antonio; Moure, Juan Carlos; Rodríguez-Aguilar, Juan A.
Palabras claveCombinatorial auctions
Large-scale coordination
Large-scale optimisation
Linear programming
Fecha de publicación2015
EditorSpringer
ResumenAuctions, 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 (AD3) has been shown to ef- ficiently 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 AD3. Moreover, we present PAR-AD3, the first parallel implementation of AD3. PAR-AD3 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- AD3 becomes the algorithm of choice to solve large-scale WDP LP relaxations for hard instances. Furthermore, PAR-AD3 has potential when considering large- scale coordination problems that must be solved as optimisation problems.
URIhttp://hdl.handle.net/10261/130923
DOI10.1007/978-3-319-19282-6_10
ISBN978-331919281-9
ISSN03029743
Aparece en las colecciones: (IIIA) Comunicaciones congresos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
LNCS9037_153-168.pdf700,94 kBAdobe PDFVista previa
Visualizar/Abrir
Mostrar el registro completo
 


NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.