厳密に解く反対側の世界
ここまでは「最適は諦めて、現実的な解を出す」道を歩んできた。
だが世の中には、「最適を諦めない」と決めた人たちもいる。
彼らの武器は 厳密解法。
そして驚くべきことに、現代では両者が手を組むのが王道だ。
この章は短い。だがあなたの世界観を変える章だ。 「メタヒューリスティクス vs 厳密」という古い対立軸を捨てて、 **「両者を協調させる」**という現代の見方に着地する。
6.1 厳密解法ってなに?
「最適解を保証する解法」だ。
時間は最悪のとき指数的にかかる。だが、解けたときには「これが最適です」と数学的に言える。
6.2 分枝限定法 (Branch and Bound)
厳密解法の心臓部にあるのが 分枝限定法 (B&B)。
「全列挙」を、賢く枝刈りしながら行うアルゴリズムだ。
B&B の戦い方:
- 解空間を「変数の値で場合分け」して木に展開する
- 各ノードで「ここから先、絶対これ以上良くなれない」下界を計算
- 下界が「既に持っている最良解」を超えたら → そのサブツリーごと刈り取る
枝刈りが効くほど早く解ける。
「下界を鋭くする」のと「変数の場合分け順を賢くする」のが、商用ソルバーが半世紀かけて競ってきた領域だ。
6.3 整数計画 (MIP) — 業界の王様
B&B の応用先で最も成功したのが MIP (Mixed Integer Programming)。 意思決定変数の一部が整数 (特に 0/1) で、目的関数と制約が線形な問題。
古典のソルバー (Gurobi, CPLEX) は、過去 30 年でハードウェアを除いて 1000 倍以上速くなった。 昔は手も足も出なかった数万変数の問題が、今は普通に解ける。
ただし、「MIP に書きやすい」問題と「書きにくい」問題がある。
線形不等式と相性が良い問題は MIP が強い。
論理構造が支配的なスケジューリングは、CP の方が圧倒的に強い。
6.4 CP-SAT — スケジューリングの最強カード
本書で本当に推したいのが Google OR-Tools の CP-SAT ソルバー。 無料、Python から触れる、ドキュメントが豊富。そして本気で速い。
三種の神器
| 機能 | 役割 |
|---|---|
IntervalVar | 「開始 + 長さ + 終了」を 1 変数として宣言できる。タスクをそのまま表せる |
NoOverlap | 同じ機械上の区間は重ならない (disjunctive resource) |
Cumulative | 容量を持つリソース (電力、人員) のピーク制御 |
これらを使うと、JSP が 30 行で書ける。第7章でやる。
実務メモ — まず CP-SAT新規プロジェクトで「ジョブ・タスク・機械・順序・段取り・容量」が出てきたら、
まず CP-SAT で書く。これは現代の常識。
自前のアルゴリズムに数週間使う前に、CP-SAT が解けるかを確認すること。
6.5 ヒューリスティクスと厳密 ——「敵」じゃなく「相棒」
昔は「小さい問題は厳密、大きい問題はメタヒューリスティクス」と棲み分けていた。
現代は違う。両者を握手させるのが王道だ。
古い世界観
- 厳密 vs メタヒューリスティクス
- どちらか選ぶ
- ベンチマークでの最適到達が指標
現代の世界観
- 厳密ソルバーをサブルーチンとして使う
- 両者を組み合わせる
- 「制限時間内に実用解 + 下界 + 説明」
マッチヒューリスティクス: 三つの王道パターン
① LNS over MIP/CP
解の一部を固定 → 残りを厳密ソルバーで完璧に解く
→ ALNS の repair を CP-SAT にする、と言えば前章の続き
② Local Branching
「現解からハミング距離 k 以内」を MIP の制約として追加 → その中で厳密最適化
③ Warm Start (ヒント)
ヒューリスティクスで作った解を、CP-SAT/MIP の初期解として渡す
→ 早い段階で良い上界が出て、枝刈りが効く
6.6 大規模問題への分解
本当に大きな問題は、厳密ソルバーでも単独では解けない。 そういうとき「問題を割る」テクニックがある。
- Column Generation: 変数が膨大なときに使う。「いま必要な変数」だけを動的に生成する。シフトスケジューリングの定番。
- Benders 分解 / LBBD: 「マスター問題 + サブ問題」に分ける。 「機械への割当てだけ MIP で決め、各機械のスケジュールは CP で解く」というハイブリッドが LBBD の典型。
- Lagrangean 緩和: 厄介な制約をペナルティ化して下界を作る
これらは深い話で、本気で必要になるまで詳細は不要。
「これくらいの大きさになると、こういう道具を使う」というレベルで頭の隅に置いておけばいい。
6.7 使い分けのチート表
| 状況 | 第一候補 | 代替 |
|---|---|---|
| 変数 1000 程度、線形制約 | MIP (Gurobi / HiGHS) | — |
| スケジューリング (〜5000 タスク) | 🌟 CP-SAT | ALNS |
| VRP (〜500 顧客) | ALNS / HGS / LKH | CP-SAT |
| JSP / FJSP (〜50×20) | CP-SAT | ALNS + LBBD |
| 10⁴ タスク以上 | 分解 + メタヒューリスティクス | Column Generation |
| 不確実性込み | Rolling Horizon + matheuristic | 確率的計画 |
6.8 この章の振り返り
- 厳密解法には MIP / CP / DP の三本柱がある。共通基盤は B&B。
- スケジューリング系で迷ったら、まず CP-SAT。
- 大規模問題は分解 (Column Generation、Benders、Lagrangean) で割る。
- マッチヒューリスティクスで、ヒューリスティクスと厳密ソルバーを協調させる。
- もう「ヒューリスティクス vs 厳密」ではない。両者を組み合わせる設計の時代。
これで本書の前半 (アルゴリズム編) は終わり。
次の章から、本書のもう一つの主役 ——「現実の生産スケジューリング」 に入る。