DIDPPyとは？動的計画法で最適化問題を解くPythonソルバーの使い方・インストール・比較

DIDPPy（ディーアイディーピーパイ）は、動的計画法（DP）で組合せ最適化問題を解くPython製のソルバーです。問題ごとにDPのアルゴリズムを手で書く代わりに、状態と遷移という形でモデルを一度だけ記述すれば、あとは付属の汎用ソルバーが最適解を探索します。MIPソルバーに線形モデルを渡して解かせる発想を、動的計画法に置き換えたものと考えると理解しやすくなります。この記事では、DIDPPyの位置づけ、インストール、ナップサック問題での最小実装、ソルバーの選び方、MIPやCPとの違い、得意な問題までを最新版0.10.1（2026年4月時点）に沿って解説します。

まとめ：DIDPPyの要点

• 正体：DIDP（Domain-Independent Dynamic Programming＝ドメイン非依存の動的計画法）のPythonインターフェース。中核はRust製の didp-rs。
• モデル記述：状態・遷移・基底ケースを DyPDL という定式化で書く。線形制約ではなく「状態を1手ずつ進める」発想。
• 導入：pip install didppy だけ。Python 3.7以上、Rustコンパイラ不要、MIT／Apache-2.0のデュアルライセンスで無料。
• ソルバー：迷ったら CABS（Complete Anytime Beam Search）。用途に応じて CAASDy・LNBS・ForwardRecursion を使い分ける。
• 得意：巡回・順序決定・詰め込み系の離散最適化。時間窓付きTSPや車両経路問題では商用MIP／CPを上回る性能が論文で報告されている。
• 不得意：連続変数中心の問題、資源次元が多く状態が爆発する問題。ここはGurobiなどの商用MIPソルバーの方が向く。

以下、DIDPとは何かという位置づけから、実際に手を動かす手順、性能を引き出すチューニングまで順に見ていきます。

DIDPPyとDIDPの位置づけ：動的計画法をソルバー化する発想

DIDP（Domain-Independent Dynamic Programming）は、動的計画法を土台にしたモデルベースの組合せ最適化パラダイムです。開発したのはトロント大学の Ryo Kuroiwa 氏と J. Christopher Beck 氏で、最初の論文は2023年のICAPSで発表されました（Kuroiwa氏は現在、国立情報学研究所に所属）。DIDPPyはその実装 didp-rs（Rust製）に対するPythonバインディングにあたり、プロジェクトの公式サイトは didp.ai です。

従来の動的計画法は、ナップサックやTSPなど問題ごとにDP方程式を人手で導出し、そのつどコードを書いていました。DIDPが変えたのはこの点です。問題を 状態遷移システムとして記述する DyPDL（Dynamic Programming Description Language）という共通の言語で書けば、あとは汎用ソルバーが状態空間を探索します。線形計画のモデルをGurobiに渡すのと同じ「モデルとソルバーの分離」を、DPの世界で実現したものだと捉えると理解が早まります。

MIP・CP・メタヒューリスティクスとの違い

組合せ最適化の代表的な解法とDIDPの関係を、モデルの書き方と解の保証で整理します。数理最適化の基本的な考え方や、決定変数・目的関数・制約条件の役割を先に押さえておくと、下表の違いが立体的に見えてきます。

DIDPの探索は、ビームサーチやA*といったAIプランニング由来のアルゴリズムを、モデル作成者が与えるデュアル境界（許容的な下界／上界）で誘導する点に特徴があります。これはLP緩和で枝を刈るMIP、制約伝播で解を絞るCPとは別系統のアプローチです。さらにCABSのようなソルバーは、良い実行可能解を早く出す「アンタイム性」と、時間を与えれば最適性（または実行不能）を証明する「完全性」を両立します。前者はメタヒューリスティクスの強み、後者は厳密解法の強みで、DIDPはこの両方を1つのソルバーで狙えます。

DIDPPyのインストール

DIDPPyはPyPIでビルド済みホイールが配布されているため、導入はコマンド1行で完結します。

pip install didppy

必要条件はPython 3.7以上のみです。中身はRust製ですが、Windows・macOS・Linux向けのホイールが用意されているため、利用者がRustコンパイラを入れる必要はありません。import didppy が通れば準備完了です。最新版は0.10.1（2026年4月10日公開）で、外部ソルバーの追加インストールや商用ライセンスの手続きも一切不要です。この手軽さは、別途インストールとライセンス取得が要るGurobiの導入手順と比べたときの明確な利点です。

DIDPPyの基本的な使い方：ナップサック問題の実装

0/1ナップサック問題（重さ制限のあるナップサックに品物を詰め、価値の合計を最大化する）を題材に、モデル記述から解の取得までを追います。状態は「残り容量」と「検討中の品物番号」の2つで表せます。

状態変数とテーブルの定義

dp.Model を最大化・整数コストで作り、状態変数を追加します。品物のインデックスは要素変数、残り容量は整数変数で表し、重さと価値は定数テーブルとして登録します。

import didppy as dp

model = dp.Model(maximize=True, float_cost=False)

item = model.add_object_type(number=4)
r = model.add_int_var(target=50)                       # 残り容量（初期＝ナップサック容量）
i = model.add_element_var(object_type=item, target=0)  # 検討中の品物番号（初期＝0）

w = model.add_int_table([10, 20, 30, 40])              # 各品物の重さ
p = model.add_int_table([5, 25, 35, 50])               # 各品物の価値

target は「最終的に到達させたい状態」の初期値です。品物0番・残容量50から探索を始める、という初期状態がここで定まります。

遷移と基底ケースの定義

「品物を詰める（pack）」と「見送る（ignore）」の2つの遷移を定義します。cost の dp.IntExpr.state_cost() は遷移先の状態コストを指す必須トークンで、pack では品物の価値 p[i] を上乗せします。effects は状態変数の更新、preconditions は適用条件です。

pack = dp.Transition(
    name="pack",
    cost=p[i] + dp.IntExpr.state_cost(),
    effects=[(r, r - w[i]), (i, i + 1)],
    preconditions=[i < 4, r >= w[i]],
)
model.add_transition(pack)

ignore = dp.Transition(
    name="ignore",
    cost=dp.IntExpr.state_cost(),
    effects=[(i, i + 1)],
    preconditions=[i < 4],
)
model.add_transition(ignore)

model.add_base_case([i == 4])                            # 全品物を検討し終えたら終了

add_base_case で終了条件を与えます。これを忘れると探索が止まらない、あるいは即座に解なしで終わるので必ず設定します。

ソルバーの実行と結果の取得

モデルにソルバーを渡し、search() で探索します。ここでは推奨ソルバーのCABSを使い、10秒の時間制限を設けています。

solver = dp.CABS(model, time_limit=10)
solution = solver.search()

print("最適値:", solution.cost)          # この例では 60
print("最適性の証明:", solution.is_optimal)
for t in solution.transitions:
    print(t.name)

返ってくる Solution からは、目的値 cost、解に至る遷移列 transitions、最適性が証明されたかを示す is_optimal、展開ノード数 expanded、経過秒数 time などが得られます。実行不能かどうかは is_infeasible で判定します（is_feasible という属性は存在しません）。この例では品物1と品物2を選ぶ価値60が最適解になります。

ソルバーの選び方：CABSを基本に用途で切り替える

DIDPPyは十数種類のソルバーを持ち、同じモデルでもどれを使うかで性能が変わります。公式のソルバー選択ガイドは「可能な限りCABSを使うこと」を推奨しており、アンタイム性・完全性・メモリ効率・マルチスレッド対応を備えた汎用解として最初の候補になります。

選び分けで最も間違えやすいのがコスト式の制約です。CABSを含む探索ベースのソルバーは、各遷移のコストが x + state_cost、x * state_cost、dp.max(x, state_cost)、dp.min(x, state_cost) のいずれかの形でなければ正しく動きません。この形に収まらない複雑なコスト式を使いたいときは、任意のコスト式を許容する ForwardRecursion を選びます。逆に言えば、加算コストの標準的なDPであればCABSで問題ありません。なお、時間窓付きTSPやタレントスケジューリングでは、LNBSがCABSより良い解を早く見つけた例が論文で報告されています。

モデル側で探索を速くするチューニング

ソルバーを変えずにモデル側へ情報を足すだけで、探索効率は大きく変わります。公式チュートリアルでも、基本DPモデルに次の工夫を加えると探索ノード数が大幅に減る例が示されています。

リソース変数で優越関係を使う

「小さい（または大きい）ほど有利」という単調性のある状態変数は、add_int_resource_var でリソース変数として宣言します。例えば時間窓付きTSPの現在時刻は「小さいほど残りの巡回に有利」なので less_is_better=True を指定します。こうするとソルバーは、他の状態が同じなら時刻が小さい状態だけを追えばよいと判断し、劣る状態を優越（ドミナンス）関係で探索から外せます。整数版のほか add_float_resource_var・add_element_resource_var もあります。

状態制約で無効な状態を排除する

すべての状態が満たすべき条件は add_state_constr で課します。遷移の前提条件と違い、生成された時点で条件を満たさない状態はその場で無効になり、探索から消えます。時間窓付きTSPなら「どう頑張っても時間窓に間に合わない未訪問地点が残っている状態」を切り捨てられます。条件の論理演算はPythonの and／or ではなくビット演算子 &・|・~ を使う点に注意してください。

デュアル境界で探索を誘導する

「この先どれだけコストが必要か」の見積もり（下界または上界）を add_dual_bound で与えます。これはA*の評価関数 f = g + h の h にあたり、ソルバーはこの値で探索順を決めたり、最良解より悪い枝を刈ったりします。ナップサックなら「残り品物を詰めたときの価値の上界」、TSPなら「残タスクに必要な最低移動コスト」などが典型です。良い境界を与えるほど無駄な探索が減り、扱える問題規模が広がります。

DIDPが得意な問題とベンチマークで示された性能

DIDPが扱えるのは「有限個の状態と遷移で表せる組合せ最適化問題」で、とりわけ経路・順序決定・詰め込み系に強みがあります。基礎論文（ICAPS 2023「Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization」）では、次の問題群でDIDPが商用MIPソルバーやCPソルバーを上回る結果が報告されました。

• 時間窓付き巡回セールスマン問題（TSPTW）・容量制約付き車両経路問題（CVRP）：状態に「未訪問集合・現在地・現在時刻」を持たせて逐次決定するDPと相性が良い。
• ビンパッキング・多次元ナップサック：残容量を状態に持つ典型的なDP。分枝限定のLPギャップに悩まされない。
• 単一機械の重み付き遅延最小化・タレントスケジューリング・組立ラインバランシング（SALBP-1）：順序決定系のスケジューリング。
• 開スタック最小化（MOSP）・グラフクリア問題：一見特殊だが状態と遷移で表現できる。

公式サイトも「VRP・パッキング・スケジューリングを含む多くの組合せ最適化問題でMIPやCPより優れた性能を示す」と明言しています。その後もアンタイム探索（ICAPS 2023）、LNBS（CP 2023）、並列ビームサーチ（AAAI 2024）と改良が続き、その後、総説版が学術誌 Artificial Intelligence に発表されています。ただし具体的な「何インスタンス中いくつ解けたか」という数値は問題・論文ごとに異なるため、厳密な比較が必要なら原論文（arXiv:2211.14409 など）を直接参照してください。

逆に不得意なのは、連続変数を多用する問題や、資源の種類が多く状態が指数的に膨らむ問題です。多次元ナップサックでも資源次元が3〜4程度までなら効果を発揮しますが、10も20もあると事実上扱えません。こうした線形計画向きの課題は、PuLPによる線形モデル化や商用MIPソルバーの方が手早く解けます。

DIDPPyでよくあるエラーと対処

DIDPPyのモデル記述には、Pythonの通常の書き方と混同しやすい落とし穴があります。エラーにならず「おかしな解しか出ない」形で現れるため、次の点を先に押さえておくと詰まりにくくなります。

• 遷移をモデルに追加し忘れる：dp.Transition(...) を作っただけでは使われません。必ず model.add_transition() で登録します。忘れると解なしで即終了します。
• Python組み込みのmax/minを使う：式の最大・最小は dp.max・dp.min を使います。組み込みの max() はモデル構築時に評価されて誤動作します。
• 論理演算にand/orを使う：条件のAND・OR・NOTはビット演算子 &・|・~ で書きます。not A or B は ~A | B です。
• 基底ケースの未設定：add_base_case を忘れると終了条件がなく探索が終わりません。
• ソルバーとコスト式の不整合：加減算以外のコスト式でCABSを使うと正しく解けません。前述のコスト式制約に合わせてForwardRecursionへ切り替えます。

公式ドキュメントには Common Mistakes とデバッグガイドの章があり、正しい記述例が整理されています。解が思うように出ないときは、まずここを確認するのが近道です。

よくある質問

DIDPPyは無料で使えますか？

はい。DIDPPyはMIT／Apache-2.0のデュアルライセンスのオープンソースで、商用利用も含めて無料です。pip install didppy でインストールでき、Gurobiのような別途のライセンス取得や購入は不要です。研究用途やプロトタイピングに気軽に使えます。

DIDPPyとGurobiやPuLPは何が違いますか？

GurobiやPuLP（＋CBC）は問題を線形の変数・制約でモデル化するMIPの世界のツールです。DIDPPyは問題を状態と遷移という動的計画法の形でモデル化します。線形制約で素直に書ける割当・ネットワーク系はMIPが有利で、巡回・順序決定・詰め込み系のようにDPと相性の良い問題ではDIDPPyが優れることがあります。両者は競合というより補完関係にあります。

DIDPPyを使うのに必要なPythonのバージョンは？

Python 3.7以上です。WindowsでもmacOSでもLinuxでもビルド済みホイールが配布されているため、Rustコンパイラを別途入れる必要はありません。最新版は0.10.1（2026年4月時点）です。

ソルバーはどれを選べばよいですか？

迷ったらCABSです。アンタイム性・完全性・メモリ効率・並列対応を備えた汎用解で、標準的な加算コストのDPならまず問題ありません。加減算以外の複雑なコスト式にはForwardRecursion、単一スレッドで最適性証明を急ぐならCAASDy、初期解の早さを優先するならLNBSを検討します。

DIDPPyで解けない問題はありますか？

連続変数を多用する問題や、資源の次元が多く状態数が爆発する問題は苦手です。多次元ナップサックでも資源次元が10を超えると事実上扱えません。こうした問題は線形計画向きなので、MIPソルバーやPuLPの方が適しています。DPの形に落とし込めるかどうかが適用可否の分かれ目です。

関連記事

• 数理最適化とは？その定義と基本的な概念を理解しよう
• 決定変数とは？目的関数・制約条件との違いと決め方【数理最適化の基本】
• PythonのPuLPライブラリで最小化問題を解決する方法とは？
• Gurobiとは？Pythonでの使い方・インストール・価格を解説