アブストラクト
| Date | 15:00-16:00 Feb 4, 2025 |
| Speaker | Ryo Kuroiwa National Institute of Informatics Japan |
| Title | Domain-Independent Dynamic Programming for Combinatorial Optimization. |
| Abstract |
Real-world problems such as routing and scheduling can be considered
combinatorial optimization, which involves making a finite set of
decisions to optimize objective functions. To solve combinatorial
optimization problems, model-based paradigms, such as mixed-integer
programming (MIP), are widely used, where a problem is formulated as a
mathematical model and then solved by a general-purpose solver. While
dynamic programming (DP) has been used for various combinatorial
optimization problems, unlike model-based paradigms, existing work
typically implemented problem-specific DP algorithms. We propose
domain-independent dynamic programming (DIDP), a novel model-based
paradigm for combinatorial optimization based on DP. In this talk, I
will introduce the modeling formalism and general-purpose solvers for
DIDP. Then, I will show that DIDP empirically outperforms commercial
optimization solvers in multiple problem classes.
|