本番に乗せる — 実装と運用のリアル

この章は他の章より泥臭い。
ツール選び、アーキテクチャ、性能調整、観測 (observability)、12ヶ月の導入計画 —— 教科書では拾い切れない実戦知だ。

9.1 まずアーキテクチャの全体像

本番システムの参照アーキテクチャを 1 枚にすると、こうなる。

9.2 ライブラリ早見表

9.3 CP-SAT を効かせる小技

並列ワーカーを忘れない

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 60
solver.parameters.num_search_workers = 8       # ← これ一行で何倍も速くなる
solver.parameters.log_search_progress = True

num_search_workers は CP-SAT が並列に 異なる戦略で探索するワーカー数。 CPU コア数程度に上げるだけで、シングルスレッドの 3〜10 倍速くなる。これを忘れる人が多い。

ヒント (warm start) を渡す

# ヒューリスティクス層が作った初期解 schedule_init を渡す
for (j, o), start_value in schedule_init.items():
    model.AddHint(start_vars[(j, o)], start_value)

良いヒントがあると CP-SAT は序盤で良い UB を取れる → 枝刈りが効く → ぐっと速くなる。

収束カーブを記録する

class Logger(cp_model.CpSolverSolutionCallback):
    def __init__(self, makespan):
        super().__init__()
        self.makespan = makespan
        self.history = []
    def on_solution_callback(self):
        self.history.append((self.WallTime(), self.Value(self.makespan)))

logger = Logger(makespan)
solver.SolveWithSolutionCallback(model, logger)
# あとで history を眺めて「どこで止まったか」を見る

9.4 ALNS の実装テンプレ

Python の alns ライブラリを使うと、フレームワークが全部用意されている。
あなたがやるのは「destroy 関数」「repair 関数」を書くだけ。

from alns import ALNS, State
from alns.accept import RecordToRecordTravel
from alns.select import RouletteWheel
from alns.stop import MaxIterations
import numpy.random as rnd

class ScheduleState(State):
    def __init__(self, schedule):
        self.schedule = schedule
    def objective(self):
        return makespan(self.schedule)

# destroy: 関連の深いジョブを一括除去
def related_removal(state, rng, frac=0.2):
    s = copy.deepcopy(state)
    k = int(len(s.schedule.jobs) * frac)
    for j in pick_related_jobs(s.schedule, k, rng):
        s.schedule.remove(j)
    return s

# repair: 後悔値で挿入
def regret_insertion(state, rng):
    s = copy.deepcopy(state)
    while s.schedule.has_unscheduled():
        j = pick_max_regret(s.schedule)
        s.schedule.insert_at_best(j)
    return s

alns = ALNS(rnd.default_rng(42))
alns.add_destroy_operator(related_removal)
alns.add_destroy_operator(random_removal)
alns.add_repair_operator(regret_insertion)
alns.add_repair_operator(greedy_insertion)

result = alns.iterate(
    build_initial_state(problem),
    select=RouletteWheel(scores=[5, 2, 1, 0.5], decay=0.8, num_destroy=2, num_repair=2),
    accept=RecordToRecordTravel(0.05, 0.0, 1e-4),
    stop=MaxIterations(20_000),
)

9.5 王道のハイブリッド: LNS × CP-SAT

本書の現代的なクライマックス: ALNS の repair を CP-SAT で厳密に解く。

def hybrid_lns(problem, initial, time_budget):
    current = initial
    best = current
    end = time.time() + time_budget
    while time.time() < end:
        # 1) 一部 (例: 機械 1 台 / ある日) を抜く
        fixed, free = pick_neighborhood(current)
        # 2) free 部分だけ CP-SAT で厳密最適化 (時間制限 30 秒)
        model = build_cp_model(problem, fixed=fixed)
        solver = cp_model.CpSolver()
        solver.parameters.max_time_in_seconds = 30
        solver.Solve(model)
        candidate = extract_schedule(model, solver)
        if candidate.makespan < best.makespan:
            best = candidate; current = candidate
        elif accept(current, candidate): current = candidate
    return best

9.6 計画を一級市民にする

これは本書でいちばん声を大にして言いたい部分。

SchedulingPlan {
    id: UUID
    created_at: timestamp
    horizon: TimeWindow
    inputs_snapshot_id: UUID        # 入力データの凍結ID
    parameters: { ... }              # ソルバ設定
    objective_values: {
        makespan: 132.5,
        total_tardiness: 18.0,
        total_setup: 24.0
    }
    solver_metadata: {
        solver: "cp-sat",
        wall_time: 28.4,
        lower_bound: 128.0,
        gap_percent: 3.5,
        status: "FEASIBLE"
    }
    decisions: [...]                 # 各ジョブの割当て・開始・終了
    parent_plan_id: UUID?            # 前計画への参照
    explanations: [...]              # クリティカル工程・選択根拠
}

こうしておくと、後でこういうことができる:

• 「あの計画と今の計画は何が違うのか」を構造化された差分で出す
• 「もし M3 が壊れなかったら」を What-if で再計算
• 過去計画を再現テスト (リグレッション)
• ソルバーを差し替えても入出力契約は変わらない

Terraform の Plan/Apply、CockroachDB Optgen、Kubernetes Scheduling Framework と同じ哲学だ。 計画はオブジェクトであって、ログじゃない。

9.7 ハマる症状と対策

9.8 観測 (observability) は最初から

最適化エンジンをブラックボックスにしないこと。 最低限ロギングすべき:

• 📉 収束カーブ: 時間 vs 上界・下界
• ⚖️ ソフト制約違反のカウント: 全部ハードだと INFEASIBLE しか出ない
• 🔥 クリティカルパス: makespan の支配要因 = L2 説明の素材
• 🏭 ボトルネック機械: 稼働率トップ = 投資判断の素材
• 🔄 計画差分: 前計画との変更量 = 現場混乱の指標
• ⏱ 再計画レイテンシ: トリガから反映まで

9.9 機械学習を、どこに、どれくらい入れるか

2025〜2026 年の文献を眺めると、ML を組合せ最適化に入れる場所は 3 つに収まる。

9.10 12 ヶ月導入のたたき台

9.11 最後に伝えたいこと

組合せ最適化は、見方によっては絶望的な分野だ。
NP困難、指数爆発、保証なし、現場では使ってもらえない…

だが本書を読んでくれた今、わかってもらえるはず —— そんなに絶望でもない。

そして最大の合言葉は ——

読了ありがとう。
最後は付録 (用語集と参考文献)。ここから先の旅の地図として使ってほしい。