Massively Parallel and Distributed Solvers for Domain-Independent Dynamic Programming

Abstract

In this paper, we develop distributed and parallel general-purpose solvers for combinatorial opti mization 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.