Tcabにおける計算複雑性 Mathematics/Computation/Proof Complexity / Circuit Complexity

Tcabの運用は、車両の配車・回送、予約と人員の割当、拠点・車両への資本配分が相互依存する組合せ最適化として捉えられる。これらを統合したモデルは、既知のNP-hard問題を特殊ケースとして含む一般形ではNP-hardとなる。ただし、実際の計算難度は、問題構造、入力規模、定式化、求める解の精度によって異なる。

本稿では、一般形の最悪時計算量と、Tcabの現場で必要な応答時間・実行可能性・解の品質保証を区別し、どの意思決定をどの時間軸で計算すべきかを整理する。中心にあるのは次の主張である。すべてを無制限に厳密最適化するのではなく、問題構造、計算時間、解の品質保証、現場の実行制約を一体で設計する。

MILP（Mixed Integer Linear Programming／混合整数線形計画）とは、線形の目的関数と制約のもとで、一部の変数を整数（多くは0/1）に制限して最適解を探す問題である。Tcabでは、成長と営業レバレッジの成果を、Competitive ROICや1株あたりFCFの増加などで評価し、現場の整数意思決定と接続する。

Mathematics / Computation：判定問題と最適化問題

Pは多項式時間で解ける問題のクラス、NPはYesの証拠を多項式時間で検証できる問題のクラスである。ここでいう「多項式時間」は、入力の大きさを n としたとき、必要ステップ数が n の多項式で抑えられることを指す。

判定問題（意思決定版）は Yes/No で答える問題である。最適化問題は最良の解を求める問題である。両者は異なる。Karp（1972）が示した21のNP完全問題は、いずれも判定問題として定式化されている。

NP-completeは、NPに属し、かつNPの任意の問題から多項式時間還元できる判定問題である。記号では NP-complete = NP ∩ NP-hard と書ける。NP-hardは、NPを丸ごと包む一段上の集合ではない。「NPに属するどの問題からも多項式時間で還元できる」という困難性の性質である。最適化問題はYes/No問題ではないため、厳密にはNPには属さず、NP-hardに分類される。

決定問題では P ⊆ NP である。本稿が言うのは、「Pの外側」という断定ではない。一般形ではNP-hardな構造を持ち、入力規模・定式化・求める精度によっては、厳密解を実用時間内に得るのが難しい。実際の計算難度は、問題構造と計算予算によって決まる。

駐車場・車両・人員は相互依存するため、個別最適化だけでは全体の整合が取れないことがある。TANAAKKグループは予約・決済・本人確認・在庫排他制御・オンデマンド配車と現地資産を垂直統合し、共通の状態情報と制約で連携して演算・制御する。これは毎回一つの巨大MILPとして解く、という意味ではない。

硬度の根拠：特殊ケースとしての還元

業務をMILPで書けることだけでは、その問題族がNP-hardであるとは限らない。整数変数の個数を固定するなどの構造制限のもとでは、多項式時間で解ける場合もある。硬度を主張するには、他の条件を固定・無効化した特殊ケースとして、既知のNP-hard／NP-complete問題を表現できることを示す必要がある。

一例として、資本配分で投資候補 i の採否を x_i ∈ {0,1}、必要資本を a_i、収益寄与を v_i、予算を B と置く。

maximize   Σi vi · xi
subject to Σi ai · xi ≤ B
           xi ∈ {0, 1}

このモデルが任意の適切な入力値を扱えるなら、古典的な0-1ナップサック問題を含む。さらに v_i = a_i として「目的値が B 以上にできるか」と問えば、Subset Sumの判定版につながる。六つの古典問題を並べる必要はない。一つでも硬い問題を特殊ケースとして含めば、一般形の困難性は示せる。本稿が確認できるのは、そのような一般モデルを構成できる、というところまでである。

古典ラベルへの分解（構造の地図）

硬度の主根拠は特殊ケース還元である。以下の六類型は、Tcabに現れる典型構造の地図として読む。

1. TSP / VRP（経路）

TSP（Traveling Salesman Problem／セールスマン巡回問題）は、都市を一度ずつ訪れて戻る最短閉路を求める。VRP（Vehicle Routing Problem／車両ルーティング問題）は、複数車両と容量制約を加えた拡張である。判定版は適切に定式化すればNP-completeに分類され、最適化版はNP-hardに分類される。

• Dantzig, Fulkerson, Johnson (1954). Solution of a large-scale traveling-salesman problem. Operations Research.
• Dantzig, Ramser (1959). The truck dispatching problem. Management Science.

Tcabではオンデマンド配車・回送の骨格にあたる。

2. Assignment / Rostering（割当・シフト）

Assignment（割当問題）は人と仕事、車と予約を一対一で対応させる。古典形はHungarian法により多項式時間で解ける（Pに分類される）。Rostering（シフト割当）は技能・連勤・最低人数が付き、一般にNP-hardに分類される。

• Kuhn (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly.
• Warner (1976). Scheduling nursing personnel according to nursing preference. Operations Research.

3. Knapsack / Bin Packing（詰込み・容量）

Knapsack（ナップサック問題）は容量内で価値を最大化する0-1選択、Bin Packing（ビンパッキング）は容量つきビンへの詰込みである。判定版はNP-complete、最適化版はNP-hardに分類される。

• Garey, Johnson (1979). Computers and Intractability（Knapsack: MP9, Bin Packing: SR1）.
• Karp, R. M. (1972). Reducibility among combinatorial problems.

Tcabでは駐車枠・車両・人員の同時利用上限や資本選択の特殊ケースがこれに対応する。

4. Facility Location（施設配置・資本配分）

どこに拠点・車両を置き、需要をどう割り当てるかを同時に決める。固定費と変動費の整数選択を含む一般形は、NP-hardに分類される。

• Cornuéjols, Fisher, Nemhauser (1977). Location of bank accounts to optimize float. Management Science.

5. Scheduling with Time Windows（時間窓）

各予約・ジョブに到着可能時間帯があり、順序と資源制約のもとで実行可能性と目的を最適化する。時間窓つきVRP（VRPTW）として扱われ、一般形はNP-hardに分類される。

• Solomon (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research.

6. Set Partition / CSP（排他・整合）

Set Partitioning（集合分割）は要素を互いに素な部分集合でちょうど覆う。CSP（Constraint Satisfaction Problem／制約充足問題）は変数・領域・制約の下で実行可能代入を探す。

在庫排他そのものは、すでに決まっている車両・時間帯の重複を検出して拒否する整合性制御として実装できる。この単純な重複確認は多項式時間で処理できる。一方、排他制約を満たす予約・車両・経路の組合せを広く探索する一般問題は、定式化によってNP-hardに分類され得る。CSPにも多項式時間で解ける制限形があるため、「制約充足だから難しい」と一括りにはできない。

• Balas, Padberg (1976). Set partitioning: A survey. SIAM Review.
• Montanari (1974). Networks of constraints. Information Sciences.

計算負荷を増やす七つの要因

コンピュータ、ロボット、AIに、財務指標を含む一体整数計画を解かせようとすると、次の要因が計算負荷を増やし得る。七つが必ず同時に「爆発」する、という意味ではない。設計上のチェックリストとして読む。

GPU、並列計算、学習を用いた探索支援は、実用上の求解性能を改善し得る。しかし、それだけで一般のNP-hard問題について、すべての入力を多項式時間で厳密に解ける保証が得られるわけではない。実際の性能は、問題構造、定式化、入力分布、許容ギャップ、計算資源に依存する。MIPソルバーは実行可能解と目的値の上下界を使い、最適性または指定した許容ギャップへの到達を判定できる。

0/1変数が n 個あるので候補は 2ⁿ 個、という説明は、単純な全列挙の大きさを示すだけである。どのアルゴリズムも全列挙しなければならないことの証明ではない。実務では、全列挙の有無ではなく、与えられた時間内に必要な品質の解と上下界が得られるかを見る。

技術：情報空間の境界条件を探索し、上下界で現象を取り出す

PやNPの枠組みが教えるのは、一般形の組合せ最適化を無制限に厳密解へ持ち込むことが難しい、という地図である。Tcabが採る技術は、その地図の上で「問題を解く」ことではない。問題の情報空間の境界条件を探索し、上界と下界の制御によって、目的の現象を決定的に取り出す一連の工程である。

ここでの情報空間とは、予約・車両・人員・時刻・資本などの変数と制約が張る実行可能領域と、その上の目的値の景観である。境界条件とは、Hard制約（破ってはならない条件）、時間窓、在庫排他、予算、応答期限、財務指標の下限など、空間の縁を定める条件である。探索とは、その縁を押し広げたり締めたりしながら、どの領域に目的の現象（実行可能な配車、充足するシフト、採算の立つ資本投入）が現れるかを見ることである。

上界と下界の制御が核である。下界は「すでに達成できた品質」、上界は「これ以上は望めない品質」を示す。両者を狭めることで、最適性の完全証明を待たずとも、目的の現象を現場に出せる確度を工学的に上げる。MIPソルバーのギャップ管理も、この工程の一形態である。

MCMC（Markov Chain Monte Carlo／マルコフ鎖モンテカルロ）は、境界近傍を歩くための道具の一つである。状態を確率的に遷移させ、目的関数（コスト、稼働、ROIC寄与、期限違反など）に従ってサンプルを集める。ただしMCMC単体が技術の定義ではない。確率的に歩いた結果を、上下界とHard制約の検定を通して決定的な指令（どの車を誰に、どの枠を閉じるか）へ落とすところまでが一連の工程である。

予約確定のような多項式時間で閉じる整合性制御は、探索に委ねず決定的に処理する。一般形の探索だけを、情報空間の境界探索と上下界制御へ載せる。関連する推論時探索の議論は、MCMCでも扱っている。

財務指標の定式化

Competitive ROICや1株あたりFCFを載せるほど、必ず整数変数が増えるわけではない。例えば、ROICの最低基準を定数 r、投入資本を IC > 0 とすると、次のように書き換えられる。

NOPAT / IC ≥ r
    ⟺  NOPAT − r · IC ≥ 0

r が定数で、NOPATとICが意思決定変数の線形関数なら、これは線形制約であり、追加の整数変数は必須ではない。

発行済株式数 N > 0 が計画期間内で固定なら、次の二つは同じ最適解を持つ。

maximize  FCF / N
maximize  FCF

「1株あたり」としたこと自体によって計算が難しくなるわけではない。反対に、株式数、資本構成、収益率、成長率などを同時に内生化して変数同士の積や比率をそのまま扱うなら、MILPではなく非線形の混合整数モデルになる可能性がある。MILPと呼ぶには、線形化が厳密なのか近似なのか、その成立条件を示す必要がある。

したがって、財務指標をどの変数・制約・目的関数として組み込むかによって、問題規模や非線形性が変わる。固定分母の比率や所与の収益率基準は、線形のまま扱える場合がある。

Proof Complexity：何の証明かを分ける

Proof Complexity（証明複雑性）は、命題が正しいことを示す証明そのものがどれだけ長くなるかを測る分野である。解を探す計算量とは別軸である。Tcabでは次の三つを混ぜない。

1. 提示された解の実行可能性確認 — 候補解を制約に代入し、整数条件などを確認する。標準的な有限符号化のMILPでは、これは多項式時間でできる。NPの「証拠を効率的に検証できる」という性質に対応する。
2. 実行可能解が一つも存在しないことの証明 — 候補解の確認とは違い、すべての可能性を排除する側の問題である（不可行性）。
3. より良い解が存在しないことの証明 — 最適性の証明である。分枝限定や切除平面の上下界がここに関わる。

ヒューリスティック解を見つけることと、その解の品質を保証することは違う。よい実行可能解の発見より、最適性ギャップを縮める証明に時間がかかる場合がある。ただし、「Tcabの証明木も必ず指数的になる」とは言えない。下界は証明体系や係数の制限などに依存する。

さらに、モデル内の保証と現実の経営成果は別である。最大化問題で実行可能解の目的値が100、証明された上界が103なら、そのモデルの最適値は100から103の間である。しかし、そこから「現実のFCFが100以上になる」とは言えない。需要予測や費用などのモデル前提が外れる可能性は別に残る。

したがって、AIが実行可能な配車案を生成しても、モデル内での最適性や近似精度が保証されるとは限らない。また、モデル内の最適性保証は、将来のROICやFCFの実現保証とは異なる。

並列計算とハードウェア制約――回路複雑性からの視点

Circuit Complexity（回路複雑性）は、問題をブール回路で解くときに、ゲート数（サイズ）や深さ（Depth）が入力サイズに対してどう増えるかを測る。計算の規模と並列性を区別する理論的な視点を提供する。

ただし、本稿はTcabの計算に対する回路サイズ・深さの下界を証明するものではない。回路の深さをレイテンシ、サイズを並列演算規模に対応させるのは、GPU/ASICの構造を説明するアナロジーである。ある定式化やアルゴリズムに依存関係が見えることは、その問題を解くすべての回路に大きな深さが必要であることの証明ではない。

実装上は、並列化可能な処理と逐次依存する処理を分け、通信・メモリアクセス・同期を含めて応答時間を評価する。「将来のAIチップなら全部解ける」「ハードウェア世代を上げても指数の壁を定数倍にするだけ」とは書かない。

四層の対応表

計算を最小にし確率空間の境界を選定する

Tcabの設計課題は、すべての意思決定を無制限に厳密最適化することではない。予約排他などの整合性制御、配車・回送などの運用計画、車両・拠点などの資本配分を連携させ、それぞれに適切な計算時間と保証水準を設定することである。

• 予約確定・在庫更新 — 整合性と応答時間を守る（単純な重複確認は多項式時間の制御として実装できる）
• 配車・回送・シフト — 時間制限つきで計画を改善し、可能な範囲で上下界や最適性ギャップを把握する
• 拠点・車両・資本配分 — より長い時間軸で収益とリスクを評価する

解の実行可能性、モデル内の最適性、現実の経営成果は区別する。厳守すべき制約（Hard）を満たしたうえで、与えられた時間内に得られる解を改善し、足りれば採用する目標（Soft）を重み付きで扱う。需要や現場状態が変化した場合には、影響範囲に応じて再計画する。

有限ホライズン化や分解は、問題を自動的にPへ変換するものではない。実務で扱う入力規模と計算時間を制御し、必要な品質を期限内に得るための設計である。Pに分類される部分ルーチンと決定的な整合性制御を切り出し、一般形については問題を解くのではなく情報空間の境界条件を探索し、上界と下界の制御によって目的の現象を決定的に取り出す。Hard制約とSoft目標を分け、共通の状態情報で連携させる。それがMathematics / Computation / Technique / Proof Complexity / Circuit Complexityを同時に見たときの、実行可能な設計境界である。