Solving the Coalition Structure Generation Problem on a GPU

Kim Svensson, Sarvapali D. Ramchurn, Francisco Cruz, Juan-Antonio Rodriguez-Aguilar, Jesus Cerquides
Electronics and Computer Science, University of Southampton, SO17 1BJ, UK
6th International Workshop on Optimisation in Multi-Agent Systems, 2013


   title={Solving the coalition structure generation problem on a GPU},

   author={Svensson, Kim and Ramchurn, Sarvapali and Cruz, Francisco and Rodriguez-Aguilar, Juan-Antonio and Cerquides, Jesus},



Download Download (PDF)   View View   Source Source   



We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: