The article presents a new model-based paradigm, Domain-Independent Dynamic Programming (DIDP), designed to solve combinatorial optimization problems. This approach is based on dynamic programming (DP), traditionally used as a problem-specific method. The authors introduce the Dynamic Programming Description Language (DyPDL), inspired by AI planning. They propose seven DIDP solvers and compare their performance with traditional mixed-integer programming (MIP) and constraint programming (CP) solvers. The article concludes by showing that DIDP outperforms MIP and CP in several problem classes.
Publication date: 2024-01-25
Project Page: https://doi.org/XXXXXXX.XXXXXXX
Paper: https://arxiv.org/pdf/2401.13883
