Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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.

Download full text files

Export metadata

Metadaten
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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.