講演情報
[5H3-OS-18b-06]Domain-Independent Dynamic Programming
〇黒岩 稜1,2 (1. 国立情報学研究所、2. 総合研究大学院大学)
キーワード：
探索、組合せ最適化、動的計画法、ヒューリスティック探索、汎用ソルバ
Domain-Independent Dynamic Programming (DIDP) は、組合せ最適化問題を動的計画法として定式化し、ヒューリスティック探索を用いて解く枠組みである。動的計画法による定式化では、プランニングのように、問題を状態とその変化に基づいて記述する。DIDP のソフトウェア実装として、宣言的に定式化された動的計画法モデルを解くことができる汎用ソルバが開発されている。DIDP は、数理最適化や制約プログラミングと同様の宣言的な問題解決手法であると同時に、探索アルゴリズムを幅広い組合せ最適化問題へ適用するためのプラットフォームでもある。これまでの研究で、DIDP が複数の問題で商用の数理最適化ソルバと制約プログラミングソルバを上回る性能を持つと示されている。この論文では、DIDP の基本と最近の成果を概説する。