1. |
- Präntare, Fredrik, 1990-, et al.
(författare)
-
Hybrid Dynamic Programming for Simultaneous Coalition Structure Generation and Assignment
- 2021
-
Ingår i: PRIMA 2020: Principles and Practice of Multi-Agent Systems. - Cham : Springer. - 9783030693220 - 9783030693213 ; , s. 19-33
-
Konferensbidrag (refereegranskat)abstract
- We present, analyze and benchmark two algorithms for simultaneous coalition structure generation and assignment: one based entirely on dynamic programming, and one anytime hybrid approach that uses branch-and-bound together with dynamic programming. To evaluate the algorithms’ performance, we benchmark them against both CPLEX (an industry-grade solver) and the state-of-the-art using difficult randomized data sets of varying distribution and complexity. Our results show that our hybrid algorithm greatly outperforms CPLEX, pure dynamic programming and the current state-of-the-art in all of our benchmarks. For example, when solving one of the most difficult problem sets, our hybrid approach finds optimum in roughly 0.1% of the time that the current best method needs, and it generates 98% efficient interim solutions in milliseconds in all of our anytime benchmarks; a considerable improvement over what previous methods can achieve.
|
|