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

Summary 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 ID...

Full description

Saved in:
Bibliographic Details
Published in:Concurrency and computation 2017-03, Vol.29 (5), p.np-n/a
Main Authors: Cruz, Francisco, Espinosa, Antonio, Moure, Juan C., Cerquides, Jesus, Rodriguez‐Aguilar, Juan A., Svensson, Kim, Ramchurn, Sarvapali D.
Format: Article
Language:English
Subjects:
Algorithms
Associations
Complexity
Computation
Concurrency
Design improvements
Dynamic programming
Microprocessors
multi agent systems
multi-core systems
Multiagent systems
Optimization
Parallel processing
set partitioning problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Summary 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.
ISSN:1532-0626
1532-0634
DOI:10.1002/cpe.3969