Massively Parallel and Distributed Solvers for Domain-Independent Dynamic Programming
Please always quote using this URN: urn:nbn:de:0297-zib-103202
- In this paper, we develop distributed and parallel general-purpose solvers for combinatorial optimization through the framework of domain-independent dynamic programming (DIDP), a model-based paradigm based on dynamic programming. In particular, we parallelize heuristic state space search algorithms to develop such solvers. Benefiting from the general-purpose nature of DIDP, we apply our solvers to four problem classes: the traveling salesperson problem with time windows (TSPTW), the type1 simple assembly line balancing problem (SALBP-1), the one-to-one multi-commodity pickup and delivery traveling salesperson problem (m-PDTSP), and the type2 assembly line balancing problem with sequence-dependent setup times (SUALBP-2). We demonstrate the scalability of our solvers using up to 192 TB of RAM and 49,152 CPU cores. Using the developed solvers, we close 14 open instances of TSPTW, 49 of m-PDTSP, and 152 of SUALBP-2.
| Author: | Ryo KuroiwaORCiD, Yuji ShinanoORCiD, J. Christopher BeckORCiD |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | Dynamic Programming, Combinatorial Optimization, Massively Parallel and Distributed Algorithms |
| MSC-Classification: | 68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) |
| CCS-Classification: | D. Software |
| PACS-Classification: | 80.00.00 INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY |
| Date of first Publication: | 2026/04/10 |
| Series (Serial Number): | ZIB-Report (26-03) |
| ISSN: | 1438-0064 |

