CDCLとは何か｜失敗を再訪禁止の学習節へ変換する
CDCL（Conflict-Driven Clause Learning）とは、候補を選ぶDecision、そこから必然的に決まるUnit Propagation、矛盾の検知、原因節の解析、学習節の追加、非時系列バックトラックを反復するSAT求解手続である。
重要なのは、失敗を物語として保存することではない。同じ失敗領域へ戻らない短い禁止節へ圧縮することである。経営では、「値下げする」「在庫を増やす」「広告費を固定する」の組合せが資金下限と衝突したなら、その組合せを再訪しない節を学習する。
CDCLの基本ループ
CDCLの反復は次の段階に分解できる。
| 段階 | 内容 |
|---|---|
| Decision | 未割当変数へ仮の0/1を与える |
| Unit Propagation | 節から必然的に決まる割当を連鎖させる |
| Conflict | Hard条件との矛盾を検知する |
| Analyze | 矛盾の原因となる短い節を抽出する |
| Learn | 学習節を追加し、同じ領域への再訪を禁止する |
| Backtrack | 必要な位置まで戻り、別のDecisionへ進む |
学習節が無い探索では、同じ衝突パターンを何度も踏み直す。CDCLは衝突を再利用可能な禁止条件へ変換することで、探索空間を削る。
失敗を学習節へ圧縮する
たとえば次のDecision列が現金下限と衝突したとする。
- 値下げする
- 在庫を増やす
- 広告費を固定する
このとき必要なのは、「なぜ失敗したか」の長い説明を議事録に残すことだけではない。同じ三つの組合せを再訪しない節を追加することである。以後の探索は、その禁止領域を避けて進む。
学習節が長すぎると効果が薄い。短く、再利用可能で、Hard clauseを守る方向へ圧縮できるかが品質になる。
非時系列バックトラックも重要である。時系列の一つ前に戻るだけでは、衝突の原因より手前のDecisionに戻れないことがある。原因節が指す位置まで戻り、別の割当を試す。経営でも、「最後に触った施策」ではなく、「衝突を構成した組合せの分岐点」まで戻る必要がある。
Unit Propagationが示す必然
Decisionのあと、節から必然的に決まる割当が連鎖する。たとえば「価格を下げる」を選ぶと、粗利率の下限から「原価も下げるか、販売数量を増やすか」が強制される。どちらもHardと衝突すれば、そのDecision自体が棄却候補になる。
Unit Propagationは、感覚的な「たぶん大丈夫」を減らす。選んだ瞬間に、後続で破るHardが見えるなら、その場でConflictとして扱う方が安い。
SatisficingとWeighted MAX-SAT
実務では、すべての希望条件を同時に満たせないことがある。
| 種別 | 例 | 役割 |
|---|---|---|
| Hard clause | 法令、現金残高、品質、安全性 | 破れば棄却 |
| Soft clause | 納期、表現、品揃え、局所利益率 | 重み付きで最大化 |
Weighted MAX-SATはSoft clauseへ重みを与え、Hard clauseを守りながら満たす重みを最大化する枠組みである。「99%なら常に十分」という普遍閾値は存在しない。何をHardとし、どの重みと充足水準で止めるかを外部主体が宣言する。
CDCLはHardの衝突を学習する装置である。Softの緩和だけを繰り返してHardを後回しにすると、学習節の意味が壊れる。
Bound、Conflict、Learn、Halt
実行手順は四段階である。
- Bound：期間・資本・試行回数を固定する
- Conflict：候補を実行し、Hard clauseとの衝突を記録する
- Learn：Conflictを再訪禁止の学習節へ変換し、必要な位置までバックトラックする
- Halt：Hardをすべて満たしSoftが受入閾値へ達したら採用して停止する
上限までに達しなければ、そのラウンドをUNSATまたは未決として閉じる。目的・制約・Boundのどれを変更するかを外部主体が決める。この停止は事業全体の終了ではなく、局所探索の終了である。
外部主体が固定すべきもの
経営者はSAT Solverそのものではない。目的関数、Hard clause、許容誤差、探索上限、タイムアウトを設定する外部主体である。
計算開始前に次を固定する。
- 何を最大化するか
- 何を一度でも破れば棄却するか
- どの水準を満たせば採用するか
- どこまで探索したら打ち切るか
探索中に都合よく目的を差し替えると、結果は検証不能になる。目的を変更する場合は新しい計算ラウンドとして記録する。
確率的検証との分離
確率的検査可能証明（PCP）定理は、NPに属する主張の証明を、乱数と少数の照会を用いて確率的に検証できるという計算量理論上の結果である。PCP定理そのものから「7日間」や「1/128」という事業上の数値は導かれない。
短期間に独立した検証機会を複数置く実務設計は、PCP定理の直接適用ではない。各回で誤りを見逃す確率や独立性の仮定を満たさない場合、単純な掛け算の数値は使えない。検証項目、サンプリング方法、偽陽性・偽陰性を事前に定義する必要がある。
CDCLの学習節は決定的な禁止条件である。確率的検証の通過確率と混同してはならない。
実務例：在庫・価格・広告
次のHardを置く。
- 現金残高 ≥ 下限
- 法令・表示義務を満たす
- 品質下限を下回らない
Softとして、売上、品揃え、納期遵守率に重みを与える。Boundを30日・試行20回とする。
候補Aが「値下げ＋在庫増＋広告固定」で現金下限と衝突したら、その組合せを学習節にする。候補BがHardをすべて満たし、Softの加重和が受入閾値へ達したら採用して停止する。達しなければ、Bound内で未決とし、価格政策か在庫上限か広告上限のどれを変えるかを次ラウンドで決める。
チェックリスト
- Conflictを再訪禁止の学習節へ変換したか
- 学習節が短く再利用可能か
- HardとSoftを分け、Softの重みと受入閾値を定義したか
- 目的関数、棄却条件、許容誤差を探索前に固定したか
- Bound、Conflict、Learn、Haltの順でラウンドを閉じたか
- 採用、UNSAT、未決、再起動のいずれかを明示したか
CDCLから得られる実務上の示唆は、「失敗談を共有すれば学習になる」ではない。同じ失敗領域へ戻らない禁止条件へ圧縮し、有限資源の探索を検証可能な手続へ変えることである。
『P vs NP経営』の詳細はこちら https://link.amazon/B04IEdYsn