SwePub - sökning: L773:9783030693220 OR L773:978...

Numrering	Referens	Omslagsbild	Hitta
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.

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.

Träfflista för sökning "L773:9783030693220 OR L773:9783030693213 "