Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems

Francisco Cruz, Jesus Cerquides, Juan A. Rodriguez-Aguilar, Antonio Espinosa, Sarvapali D. Ramchurn, Kim Svensson, Juan Carlos Moure Lopez

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)

Abstract

Copyright © 2016 John Wiley & Sons, Ltd. The coalition structure generation problem is well known in the area of multi-agent systems. Its goal is to establish coalitions between agents while maximizing the global welfare. Among the existing different algorithms designed to solve the coalition structure generation problem, DP and IDP are the ones with smaller temporal complexity. After analyzing the operation of the dynamic programming and improved dynamic programming algorithms, we have identified which are the most frequent operations and propose an optimized method. In addition, we study and implement a method for dividing the work into different threads. To describe incremental improvements of the algorithm design, we first compare performance of an improved single central processing unit core version where we obtain speedups ranging from 7 × to 11 ×. Then, we describe the best resource use in a multi-thread optimized version where we obtain an additional 7.5 × speedup running in a 12-core machine.
Original languageEnglish
Article numbere3969
Pages (from-to)1-11
JournalConcurrency and Computation: Practice and Experience
Volume29
Issue number5
DOIs
Publication statusPublished - 10 Mar 2017

Keywords

  • dynamic programming
  • multi agent systems
  • multi-core systems
  • set partitioning problem

Fingerprint

Dive into the research topics of 'Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems'. Together they form a unique fingerprint.

Cite this