Pasar al contenido principal

UNA APROXIMACION DECLARATIVA PARA MODELIZAR, ANALIZAR Y RESOLVER PROBLEMAS

TIN2013-45732-C4-4-P

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D (Excelencia / Generación de Conocimiento)
Año convocatoria 2013
Plan Estatal 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Unidad de gestión Secretaría de Estado de Educación, Formación Profesional y Universidades
Centro beneficiario AGENCIA ESTATAL CONSEJO SUPERIOR DE INVESTIGACIONES CIENTIFICAS (CSIC)
Identificador persistente http://dx.doi.org/10.13039/501100003329

Resultados relacionados

Resultados totales (Incluyendo duplicados): 3
Encontrada(s) 1 página(s)

DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Adding laziness in BnB-ADOPT+

  • Lee, Jimmy
  • Meseguer, Pedro
  • Su, Wen
In distributed constraint optimization, agents executing BnB-ADOPT+ react eagerly to cost changes: they send non-redundant COST messages to their parents as soon as they receive new messages. We have observed that a lazier reaction (not sending COST messages until a condition is met) substantially decrements the number of messages sent and causes only a small variation in ENCCCs. This approach combines nicely with soft arc consistency maintenance during search. We provide experimental evidence of the benefits of this approach on several benchmarks., This research has been supported by the following grants: CUHK413808, CUHK413710 and CUHK413713 from the Research Grants Council of Hong Kong SAR, the CSIC / RGC Joint Research Scheme grants S-HK003/12 and 2011HK0017, TIN2013-45732-C4-4-P from Spanish MINECO, and Generalitat de Catalunya SGR- 2014-118, Peer Reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

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

  • Cruz-Mencia, Francisco
  • Cerquides, Jesús
  • Espinosa, Antonio
  • Moure, Juan C.
  • Rodríguez-Aguilar, Juan Antonio
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 (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., Research supported by MICINN projects TIN2011-28689-C02-01, TIN2013-45732-C4-4-P and TIN2012-38876-C02-01, Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Paving the way for Large-Scale Combinatorial Auctions

  • Cruz-Mencia, Francisco
  • Cerquides, Jesús
  • Espinosa, Antonio
  • Moure, Juan C.
  • Rodríguez-Aguilar, Juan Antonio
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 AD3. Moreover, we contribute with PAR-AD3, the first parallel implementation of AD3. We show that while AD3 is up to 4.6 times faster than CPLEX in a single-thread execution, PAR-AD3 is up to 23 times faster than parallel CPLEX in an 8-core architecture. Copyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved., This research has been supported by MICINN-Spain under contracts TIN2011-28689-C02-01, TIN2013-45732-C4-4-P and TIN2012-38876-C02-01., Peer reviewed