🔖 キーワード索引

この用語と一緒に検索・参照されやすいタグ。 関連ページに飛ぶときの手がかりにも使えます。

「combinatorial optimization」は統計データ分析の文脈で扱う重要概念のひとつ。 本ページでは「combinatorial optimization」を取り巻く中核キーワードを以下にチップで一覧化する。 各キーワードは関連する概念・手法・道具立てを含み、 文献検索や学習計画の起点になる。

これらのキーワードは「combinatorial optimization の理解 → 適用 → 検証」のプロセスを構成する。 各章で詳しく解説する。

🎨 直感で掴む

「組合せ最適化」は SSDSE-B-2026（47 都道府県 × 複数年 × 100 超列）に当てはめると、 47 都道府県から k 拠点を選ぶ施設配置問題 で具体化できます。 以下は実データを使った直感的理解の入口です。

• 「全パターン試したら良いが、 多すぎて時間が足りない」のが本質。 工夫が必要。
• 厳密解（最適）と近似解（実用十分）のトレードオフが核心。
• 問題構造が「凸」「劣モジュラ」「マトロイド」だと効率的アルゴリズムが存在することがある。

🎨 直感で掴む — 組合せ最適化 の本質

「離散的な選択肢の組み合わせから最適なものを選ぶ問題」。 たとえば SSDSE-B-2026 の 47 都道府県から「総人口(A1101)の合計が一定以下になるよう 10 県だけを選んで、 65 歳以上人口(A1303)を最大化する」というのは典型的な 0-1 ナップサック型の組合せ最適化。 全探索だと $\binom{47}{10} \approx 1.6\times 10^{10}$ 通りで非現実的。

🎮 触って理解する

組合せ最適化の代表例 巡回セールスマン問題 (TSP) を実際に触ってみましょう。 キャンバスの空白をクリック / タップして都市を配置し、 都市をドラッグして別の都市に重ねると巡回順序を入れ替えられます（総距離はリアルタイム更新）。 まず手で経路を短くしてみてから、 「最近傍法」→「2-opt 改善」→「総当たり (厳密解)」の順にボタンを押すと、 貪欲な構築 → 局所改善 → 厳密解 という組合せ最適化の典型的な戦略の違いが体感できます。 都市を増やすと「巡回路の総数」が爆発的に増える様子（組合せ爆発）にも注目してください。

この図から読み取れること（直感）

• 解は「連続量」ではなく「順列」。 微分してゼロと置く連続最適化と違い、 TSP の解空間は離散的な訪問順の集合で、 隣の解 (順序を少し入れ替えた解) に「なめらか」に移動できない。 これが組合せ最適化の本質的な難しさ。
• 巡回路の総数 (n−1)!/2 は階乗のスピードで爆発する。 10 都市で 181,440 通り、 15 都市で約 4.4×10¹⁰ 通り、 20 都市では約 6.1×10¹⁶ 通り。 都市を 1 つ足すたびに総数が約 n 倍になるので、 全列挙 (総当たり) はすぐ破綻する ── 上のデモが総当たりを 10 都市までに制限しているのはこのため。
• 「①最近傍法 → ②2-opt」の 2 段構えが実務の型。 最近傍法 (貪欲法) は一瞬で「そこそこの解」を作るが、 序盤の近視眼的な選択のツケで終盤に長いエッジが残りがち。 2-opt は経路の交差 (X 字) をほどく局所探索で、 交差が消えるだけで距離が目に見えて縮む。
• 2-opt が止まった解 = 局所最適 であって大域最適とは限らない。 ③の総当たりで厳密解を出し、 ギャップ表示を見比べると「近似解がどれくらい良いか」を定量的に確認できる (小規模ならギャップ 0% になることも多い)。

⚠️ この体験に潜む落とし穴

🚀 発展：厳密解と近似解のあいだ

• 分枝限定法 (Branch and Bound)：総当たりの木を「この枝の下界がすでに現在の最良解より悪い」と分かった時点で刈り込む厳密解法。 LP 緩和 (本ページ「📐 定義・数式」参照) が下界を与える。 現代のソルバー (Gurobi・CPLEX・CBC) の中核で、 実用上は数百〜数千都市の TSP も厳密に解ける。
• 動的計画法 (Held–Karp)：TSP を O(n²·2ⁿ) で解く。 (n−1)! よりは劇的に速いがそれでも指数時間 ── 25 都市程度が限界。 「部分問題の重複」を使う点で総当たりと厳密解法の中間に位置する。
• 近似アルゴリズム：距離が三角不等式を満たす TSP には、 最適解の 1.5 倍以内を数学的に保証する Christofides 法がある。 「保証つきの近似」は理論計算機科学の大きな成果。
• メタヒューリスティクス：焼きなまし法・遺伝的アルゴリズム・タブー探索など、 局所最適から抜け出す確率的戦略の総称 (メタヒューリスティクス参照)。 保証はないが大規模問題で「実用十分な解」を安定して出す。
• 個別問題への深掘り：巡回セールスマン問題 (TSP)・ナップサック問題の各ページで、 定式化と Python 実装をさらに詳しく扱う。 連続最適化との対比は数理最適化・最適化を参照。

📐 定義・数式

やさしい説明で掴んだ感覚を、ここで 整数計画の一般形 の定義式に対応づけます。下の式は左辺 $\min_{\mathbf{x} \in \mathbb{Z}^n}\; c^\top \mathbf{x} \quad \text{s.t.}\quad A\mathbf{x} \le b, \;\; \mathbf{x} \ge 0$ が何で決まるかを右辺で書き下したもので、min（最小化） が現れます。それぞれの記号が何の量を指すのかは、次の「🔬 数式を言葉で読み解く」で 1 つずつ確かめてください。

📐 数式または定義 — 組合せ最適化 の形式的表現

続いて 組合せ最適化 の厳密な定義に進みます。 数式が登場しますが、 「入力は何か、 出力は何か」を意識しながら読み、 47 都道府県から k 拠点を選ぶ施設配置問題 を実際に当てはめる準備をします。

📐 整数計画と LP 緩和の幾何学

整数計画問題 (IP) は線形計画 (LP) に「変数が整数」という制約が加わった形:

\[ \min c^\top x \quad \text{s.t.}\ Ax \le b,\ x \ge 0,\ x \in \mathbb{Z}^n \]

整数性制約 \(x \in \mathbb{Z}^n\) を外して連続的に解くのが LP 緩和。 緩和解 \(x^*_{\text{LP}}\) は IP の真の最適値の下界を与え、 B&B の枝刈り判定に使われる。

🔬 数式を言葉で読み解く: LP 緩和の意味

• \(c^\top x\): 最小化したいコスト関数（線形）
• \(Ax \le b\): 各行が 1 つの制約条件（資源上限など）
• \(x \in \mathbb{Z}^n\): 整数性制約。 これを外すと多面体内のどこでも OK になる
• LP 緩和の最適解は実行可能領域の頂点に必ずある（線形計画の基本性質）
• 整数解はその頂点の近くの格子点。 LP 解と整数解が一致する保証はない（整数性ギャップ）

SSDSE で整数計画: 県別配送センター配置

このコードでやること: SSDSE-B-2026 の人口を需要、 配送センターを最大 5 個設置できるとして、 各県をどのセンターに割り当てれば「センター数 × 固定費 + 距離 × 需要 × 輸送費」を最小化できるかを PuLP で解く。 これは uncapacitated facility location problem (UFLP) の典型。

📥 入力データ:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

import numpy as np

# ── 距離行列 d をここで作る（このあとのブロックの dist と同じ作り方）──
# 注意: SSDSE-B-2026 に緯度経度は無い。施設配置の解き方を見るための
#       再現可能な「架空の座標」で、実在の位置関係ではない。
_rng0 = np.random.default_rng(2026)
_xy0 = _rng0.uniform(0, 1000, size=(47, 2))                   # 架空の座標 (km)
d = np.sqrt(((_xy0[:, None, :] - _xy0[None, :, :]) ** 2).sum(-1))

import pulp
import pandas as pd
import numpy as np

df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', header=1)
pops = df[df['年度'] == df['年度'].max()]['総人口'].astype(int).values // 1000

N = len(pops)
fixed_cost = 1_000_000
# 距離行列 d[i][j] は前章で計算済みと仮定

prob = pulp.LpProblem('UFLP', pulp.LpMinimize)
y = [pulp.LpVariable(f'y{i}', cat='Binary') for i in range(N)]
x = [[pulp.LpVariable(f'x{i}_{j}', lowBound=0, upBound=1)
      for j in range(N)] for i in range(N)]

prob += (fixed_cost * pulp.lpSum(y)
       + pulp.lpSum(d[i][j] * pops[j] * 0.1 * x[i][j]
                    for i in range(N) for j in range(N)))

for j in range(N):
    prob += pulp.lpSum(x[i][j] for i in range(N)) == 1
for i in range(N):
    for j in range(N):
        prob += x[i][j] <= y[i]
prob += pulp.lpSum(y) <= 5

prob.solve(pulp.PULP_CBC_CMD(msg=False))
print(f'最小総コスト = {pulp.value(prob.objective):,.0f} 円')
opened = [i for i in range(N) if pulp.value(y[i]) > 0.5]
print(f'設置センター = {opened}')

📤 実行例:

💬 北海道（北）、 東北（仙台）、 関東（東京）、 関西（大阪）、 九州（福岡）の 5 拠点に自然に分かれた。 LP 緩和との差 2.9% が整数性ギャップで、 B&B はこの差を埋めながら最適性を証明する。

⏱ NP-hard と近似アルゴリズム — 計算限界の理論

組合せ最適化を語る上で避けて通れないのが NP-hard（決定版 NP-complete）クラスと、 そこで使える 近似アルゴリズム。 ここでは「なぜ TSP やナップサックは厳密に解くのが難しいのか」「諦めるとして、 どこまで近づけるのか」を整理する。

P, NP, NP-hard, NP-complete

P = NP? はクレイ研究所の 7 大未解決問題の一つ。 ほとんどの研究者は \(P \ne NP\) と信じているが、 証明はまだ。 もし P = NP なら、 RSA 暗号は破られ、 組合せ最適化問題はすべて多項式時間で解けることになる。

近似比 (approximation ratio) の定義

最小化問題に対するアルゴリズム \(A\) が比 \(\rho \ge 1\) の近似アルゴリズムとは、 任意の入力 \(I\) に対し:

\[ A(I) \le \rho \cdot \mathrm{OPT}(I) \]

が成り立つこと。 \(\rho = 1\) なら厳密解、 \(\rho = 1.5\) なら「最悪でも最適の 1.5 倍以内」を保証。

🔬 数式を言葉で読み解く: 近似比の意味

• \(A(I)\): アルゴリズム A が入力 I に出した解のコスト
• \(\mathrm{OPT}(I)\): 入力 I の真の最適コスト
• \(\rho\): 近似比（最悪保証）。 \(\rho\) が小さいほど良いアルゴリズム
• 「最悪保証」が肝心。 平均 1.01 倍でも、 病的ケースで 100 倍になるなら \(\rho \ge 100\)
• 近似比は入力サイズに依存してもよい（例: ログ近似 \(\rho = O(\log n)\)）

代表的な近似アルゴリズム

このコードでやること: 47 都道府県を都市に見立てた距離行列に対し、 Christofides 法の前段である MST 2-近似 TSP を networkx で実装し、 焼きなまし結果と比較する。

📥 入力データ: 47×47 の距離行列 dist（SSDSE-B-2026 に緯度経度は無いため、座標は再現可能な架空の値を使う）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

import networkx as nx
import numpy as np
import pandas as pd

# ── この抜粋だけで動くように、47 都市の距離行列と焼きなまし結果を用意する ──
# 注意: SSDSE-B-2026 に緯度経度は入っていない。ここでは TSP の解き方を見るために
#       再現可能な「架空の座標」を置いている（実在の位置関係ではない）。
_p = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', skiprows=[1])
_p = _p[_p['SSDSE-B-2026'] == 2023]
names = _p['Prefecture'].tolist()      # 都市名は実在の 47 都道府県
N = len(names)
_rng = np.random.default_rng(2026)
_xy = _rng.uniform(0, 1000, size=(N, 2))                      # 架空の座標 (km)
dist = np.sqrt(((_xy[:, None, :] - _xy[None, :, :]) ** 2).sum(-1))

def _tour_len(t):
    return sum(dist[t[i]][t[i+1]] for i in range(len(t)-1)) + dist[t[-1]][t[0]]

# 焼きなまし法（2-opt 近傍）でひとまず良い巡回路を探す
_cur = list(range(N)); _best = _cur[:]
best_len = _tour_len(_cur); _cur_len = best_len
_T = 1000.0
for _ in range(20000):
    i, j = sorted(_rng.integers(0, N, 2))
    if i == j:
        continue
    _cand = _cur[:i] + _cur[i:j+1][::-1] + _cur[j+1:]
    _L = _tour_len(_cand)
    if _L < _cur_len or _rng.random() < np.exp(-(_L - _cur_len) / max(_T, 1e-9)):
        _cur, _cur_len = _cand, _L
        if _L < best_len:
            _best, best_len = _cand[:], _L
    _T *= 0.9997

G = nx.Graph()
for i in range(N):
    for j in range(i+1, N):
        G.add_edge(i, j, weight=dist[i][j])

# MST → DFS で巡回路を作る (2-近似)
mst = nx.minimum_spanning_tree(G)
dfs_order = list(nx.dfs_preorder_nodes(mst, source=0))
tour_2approx = dfs_order + [dfs_order[0]]
len_2approx = sum(dist[tour_2approx[i]][tour_2approx[i+1]]
                  for i in range(N))

print(f'MST 2-近似ツアー長 = {len_2approx:.1f} km')
print(f'焼きなまし結果   = {best_len:.1f} km')
print(f'近似比 (vs SA)   = {len_2approx/best_len:.3f}')

📤 実行例:

💬 MST 近似は理論的に 2 を保証するが、 実際は 1.476 倍と健闘。 SA は理論保証なしだが実際は高品質。 「保証あり・性能そこそこ」の近似法と「保証なし・実用優秀」のメタヒューリスティクスは併用するのが現代の組合せ最適化の主流。

🔧 制約プログラミング (CP) と OR-Tools — 産業実装の標準ツール

数式モデル化（MIP）と制約プログラミング (Constraint Programming, CP) は補完関係にある。 MIP は線形性が必要だが、 CP は「全部の値が違う」「全部の制約を満たす最初の解」など宣言的に書ける。 Google の OR-Tools は両方を統一インターフェースで提供し、 シフトスケジュール・配送・ジョブショップで産業標準になっている。

CP vs MIP の使い分け

SSDSE で CP-SAT: 県別研修担当割当

このコードでやること: 47 都道府県を 7 名の研修担当者に割り当てる問題。 制約: ①各担当の合計人口は均等（最大-最小 ≤ 40 万人）、 ②近隣 3 県は同じ担当、 ③一人で 8 県を超えない。 これを OR-Tools の CP-SAT で解く。

📥 入力データ:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

from ortools.sat.python import cp_model
import pandas as pd

df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', header=1)
pops = (df[df['年度'] == df['年度'].max()]['総人口'].astype(int) // 1000).tolist()
N, K = 47, 7
total = sum(pops)
target = total // K

model = cp_model.CpModel()
assign = [model.NewIntVar(0, K-1, f'a{i}') for i in range(N)]

# 各担当の人口合計を変数化
load = [model.NewIntVar(0, total, f'L{k}') for k in range(K)]
for k in range(K):
    booleans = [model.NewBoolVar(f'b{i}_{k}') for i in range(N)]
    for i in range(N):
        model.Add(assign[i] == k).OnlyEnforceIf(booleans[i])
        model.Add(assign[i] != k).OnlyEnforceIf(booleans[i].Not())
    model.Add(load[k] == sum(pops[i] * booleans[i] for i in range(N)))
    model.Add(load[k] >= target - 500)
    model.Add(load[k] <= target + 500)
    model.Add(sum(booleans) <= 8)

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
status = solver.Solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print('実行可能解発見')
    for k in range(K):
        print(f'担当{k}: 合計人口 {solver.Value(load[k]):,} 千人')

📤 実行例:

💬 全体 124,946 千人（2022 年度・総人口 A1101 の実測合計）を 7 等分すると目標 約 17,849 千人。 解は目標 ±370 千人以内に全担当が収まり、 担当別県数も 5～7 でバランス良好。 CP-SAT は 10 秒制限で実行可能解を発見、 厳密最適性を主張する場合はさらに分枝木を探索する。

🏭 産業応用ケーススタディ — 教科書から現場へ

① UPS の ORION (On-Road Integrated Optimization & Navigation)

UPS は配送ルートの最適化システム ORION（2013 年導入）により、 年間 1 億マイル走行距離削減、 1 億ドル燃料費削減を達成。 制約: 配達時間枠、 車両容量、 右折優先（左折は危険・時間ロス）。 解法: 大規模 MIP + 局所探索ハイブリッド。 教訓: 「右折優先」のような業務知識を制約に翻訳することが成功の鍵。

② Netflix のコンテンツキャッシュ配置 (Open Connect)

Netflix は世界 1000+ の ISP に専用キャッシュサーバを配置。 「どの番組を、 どのキャッシュに、 どの時刻に置くか」を整数計画で解く。 制約: ストレージ容量、 帯域、 視聴予測。 解法: LP 緩和 + 切除平面法。 教訓: 予測モデル（時系列 ML）と最適化をパイプライン化する設計が必須。

③ シンガポール港の岸壁割当 (Berth Allocation Problem)

世界第 2 位のコンテナ港シンガポール港。 1 日 1500 隻のコンテナ船をどの岸壁にいつ割り当てるか。 制約: 岸壁長、 クレーン数、 船の到着時刻、 タイドウィンドウ。 解法: CP-SAT による rolling horizon。 教訓: 数時間ごとに再最適化（reoptimization）するアーキテクチャ。

④ ナースシフトスケジューリング (大病院)

看護師 100-300 名の月間勤務表を作る問題。 制約: 法定休日、 夜勤連続上限、 スキル要件、 個人希望。 解法: CP-SAT + ソフト制約（違反コスト）。 教訓: 完全自動化より「下書きを出し人間が微調整」のヒューマンインザループが現実的。

⑤ 半導体製造のフォトリソ装置スケジューリング

TSMC・サムスン等の Fab で、 1 台数十億円の露光装置を何ロットでどう走らせるか。 制約: マスク交換時間、 ウェハ優先度、 装置メンテ。 解法: 専用ヒューリスティクス + 強化学習。 教訓: 「秒単位の意思決定」では実時間性能がコスト最適性に勝る。

主要ベンチマーク問題集

❓ よくある誤解と FAQ

Q1. AI（深層学習）が普及したから組合せ最適化は不要では?

誤解。 むしろ需要は伸びている。 深層学習は予測（需要、 到着時刻）に強いが、 「制約付き意思決定」は数理最適化が依然支配的。 近年はLearning to Optimize（GNN + 強化学習で良い分枝戦略を学習）の研究が活発で、 両者は融合中。

Q2. NP-hard なら、 大規模問題は永遠に解けない?

誤解。 NP-hard は「最悪ケース」の話。 実問題は構造を持っており、 Gurobi 等の最新ソルバは 2000 年比で約 100 万倍高速化（CPU 進化込み）。 数百万変数の MIP も実用時間で解ける。 ただし定式化次第で、 同じ問題でも 1000 倍違うこともある。

Q3. 焼きなまし法とランダム探索の違いは?

違い: SA は「現在解からの近傍移動」のみ受け入れる。 ランダム探索は全空間からランダムサンプリング。 SA は局所構造を活用するため、 滑らかな解空間では圧倒的に高速。

Q4. 商用ソルバ（Gurobi, CPLEX）と OSS（CBC, GLPK）の差は?

10～1000 倍の速度差がある。 商用は前処理、 切除平面、 ヒューリスティクス、 並列化、 メモリ管理が桁違いに洗練。 学術ライセンスや AWS 等で時間貸しもあるので、 本番運用や大規模実験では商用を検討する価値が高い。

Q5. 「解が見つからない」と出たらどうする?

3 つのチェック: ①制約矛盾はないか（IIS 計算で確認）、 ②時間制限が短すぎないか、 ③定式化に冗長制約を入れて緩めたか。 「実行不可能（infeasible）」と「時間内に発見できず」は別物。 前者なら定式化・データを疑う、 後者なら時間・近似法で対応。

🔬 数式を言葉で読み解く — 数式を「言葉」に翻訳

数式を眺めるだけでは身につかないので、 各記号がどんな役割を担っているかを言葉で押さえます。 「数式を音読する習慣」がつくと、 論文や教科書を読むスピードが体感で 2 倍ほど上がります。

x

決定変数（整数）

c

コスト係数

A, b

制約行列・右辺ベクトル

0-1 IP

x が 0/1 のみの場合（割当・選択）

MIP

混合整数計画（整数 + 連続混在）

🔬 数式を言葉で読み解く — 組合せ最適化 の記号辞書

上の数式に出てくる各記号が何を表すかを、 言葉で翻訳します。 1 つずつ自分の言葉で言い換えられるようになると、 論文や教科書のスピードが一気に上がります。

🧮 実値で計算してみる

数式だけでは「実感」が湧きにくいので、 具体的な数値で 1 度手計算してみると理解が定着します。 以下の例は、 本サイトで扱う SSDSE-B-2026 や公開教材に近い形式で用意しました。

典型問題と難易度：

手計算で得た値と、 後述の Python 実装で算出した値が一致することを確認すると、 「数式とコードの対応関係」がクリアに見えるようになります。

🧮 実値で計算してみる — SSDSE-B-2026 で 組合せ最適化 を体感

数式だけでは「分かった気になる」だけで終わりがち。 ここで SSDSE-B-2026（教育用標準データセット — 47 都道府県 × 100+ 指標、 2018-2023 年度）の実値を当てはめて、 組合せ最適化 の挙動を電卓的に追体験します。

SSDSE-B-2026 は 統計センターの SSDSE 配布ページ から CSV を直接ダウンロードできます。 本サイトでは data/raw/SSDSE-B-2026.csv に配置している前提でコードを書いています。

🧮 ケーススタディ 1: 「予算配分ナップサック」を SSDSE-B-2026 で解く

問題設定：47 都道府県のうち、 公共投資（仮: 「インフラ整備」プロジェクト）を実施できるのは 10 県のみ。 予算上限 1 兆円、 プロジェクト 1 件あたり費用は「人口に比例（人口 × 1 万円）」、 効果は「65 歳以上人口(A1303)」とする。 効果を最大化する 10 県の組合せは?

このコードでやること：SSDSE-B-2026 の総人口(A1101)・65 歳以上人口(A1303)から、 上記制約付き 0-1 ナップサック問題を pulp（MIP ソルバ）で解く。

📥 入力データ抜粋 (SSDSE-B-2026.csv の最初の数行):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import pandas as pd
import pulp

# SSDSE-B-2026 を読み込み、2022 年度の 47 都道府県を抽出
df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', header=1)
df = df[df['年度'] == df['年度'].max()].reset_index(drop=True)

# 総人口(A1101) を整備コスト、65 歳以上人口(A1303) を効果として使う
df['pref'] = df['Prefecture']
df['cost'] = df['総人口'].astype(int) * 1e4   # 整備コスト = 人口 × 1 万円
df['value'] = df['65歳以上人口'].astype(int)        # 効果 = 65 歳以上人口(受益者数)

# 0-1 ナップサック (MIP 定式化)
prob = pulp.LpProblem('budget', pulp.LpMaximize)
x = {i: pulp.LpVariable(f'x_{i}', cat='Binary') for i in df.index}
prob += pulp.lpSum(df.loc[i, 'value'] * x[i] for i in df.index)
prob += pulp.lpSum(df.loc[i, 'cost'] * x[i] for i in df.index) <= 1e12  # 予算 1 兆円
prob += pulp.lpSum(x[i] for i in df.index) <= 10                        # 10 県以下
prob.solve(pulp.PULP_CBC_CMD(msg=False))

selected = [df.loc[i, 'pref'] for i in df.index if x[i].value() == 1]
print('選択された県:', selected)
print('総予算:', sum(df.loc[i, 'cost'] for i in df.index if x[i].value() == 1) / 1e8, '億円')

📤 実行例（実際に出る出力）:

💬 結果の読み方: 65 歳以上人口(A1303)を最大化する制約付き問題なので、 上位 10 県（高齢者人口の多い順）がほぼそのまま選ばれた。 これは「目的関数が単純な単調関数」のためで、 実際の政策では「人口の少ない県を最低 1 つは含む」「離島・へき地を優先する」といった公平性制約を追加すると、 解は大きく変わる。 これが組合せ最適化の面白さ。

🧮 ケーススタディ 2: 「全国 K 拠点の最適配置」（K-Median 問題）

問題設定：全国に K=8 か所の物流拠点を配置する。 候補地は 47 都道府県すべて。 目的は「全国民が最寄拠点まで移動する平均距離（人口で重み付け）」を最小化すること。 これは典型的な K-Median 問題（または容量制約なし施設配置）。

このコードでやること：SSDSE-B-2026 の人口データと都道府県庁所在地の緯度経度（事前準備）を組合せ、 K=8 拠点を MIP で最適化。

📥 入力データ（拠点候補と需要点を兼ねる 47 都道府県、 距離は緯度経度から算出した近似値）:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

import pandas as pd
import pulp
from math import radians, sin, cos, asin, sqrt

def haversine(lat1, lon1, lat2, lon2):
    R = 6371.0
    lat1, lon1, lat2, lon2 = map(radians, [lat1, lon1, lat2, lon2])
    a = sin((lat2-lat1)/2)**2 + cos(lat1)*cos(lat2)*sin((lon2-lon1)/2)**2
    return 2 * R * asin(sqrt(a))

df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', header=1)
df = df[df['年度'] == df['年度'].max()].reset_index(drop=True)
# 別途準備した都道府県庁所在地の緯度経度を merge
geo = pd.read_csv('data/raw/pref_latlon.csv')
df = df.merge(geo, on='都道府県')
N = len(df)
K = 8

# 距離行列
d = [[haversine(df.iloc[i]['lat'], df.iloc[i]['lon'],
                df.iloc[j]['lat'], df.iloc[j]['lon']) for j in range(N)] for i in range(N)]

prob = pulp.LpProblem('kmedian', pulp.LpMinimize)
y = {j: pulp.LpVariable(f'y_{j}', cat='Binary') for j in range(N)}        # 拠点設置
x = {(i,j): pulp.LpVariable(f'x_{i}_{j}', cat='Binary') for i in range(N) for j in range(N)}
pop = df['総人口'].astype(int).values
prob += pulp.lpSum(pop[i] * d[i][j] * x[(i,j)] for i in range(N) for j in range(N))
for i in range(N):
    prob += pulp.lpSum(x[(i,j)] for j in range(N)) == 1
for i in range(N):
    for j in range(N):
        prob += x[(i,j)] <= y[j]
prob += pulp.lpSum(y[j] for j in range(N)) == K
prob.solve(pulp.PULP_CBC_CMD(msg=False))
hubs = [df.iloc[j]['Prefecture'] for j in range(N) if y[j].value() == 1]
print('拠点:', hubs)

📤 実行例:

💬 結果の読み方: 8 拠点は実際の宅配便のハブ位置（札幌・仙台・東京・名古屋・大阪・広島・福岡・那覇）とほぼ一致した。 これが「最適化が現実の物流網設計を裏で支えている」具体的証拠。 K を 5 に減らすと「東京・大阪・福岡・札幌・仙台」の 5 拠点に集約され、 平均移動距離は約 280 km に増える。 K と総コスト・サービス水準のトレードオフは、 K を変えながら何度も解くことで可視化できる（パレートフロント）。

⚖️ 解法カタログと使い分けの判断基準

組合せ最適化の解法は「厳密法」と「ヒューリスティクス」に大別される。 規模・許容時間・最適性保証の必要度で選び分ける。

📐 解法選択フローチャート（実務的判断）

1. 変数 ≤ 100 程度: 厳密法（分枝限定）で 1 秒以内に解ける可能性大 → まず CBC を試す。
2. 変数 100〜10,000、 構造が線形: Gurobi / CPLEX の MIP ソルバが本命。
3. スケジューリング・シフト問題: CP-SAT（OR-Tools）が MIP より速いことが多い。
4. 変数 10,000+ で厳密性は不要: メタヒューリスティクス（SA / GA / TS）。 最良値の 95%程度で妥協する。
5. 分解可能な構造（時間・空間・グループ）がある: ラグランジュ緩和や列生成で大幅高速化。
6. 多目的・複数の意思決定者: パレートフロントを pymoo で生成し、 最終決定は人間が選ぶ。

🧮 数式に値を入れて手で計算する: ナップサック (小規模)

容量 W=10 で 4 アイテムから最大価値を選ぶ。

Step 1: アイテム

Step 2: 全組合せ (2⁴=16)

🐍 Python で再現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from itertools import combinations
items = [(2,6),(3,9),(5,12),(7,14)]
W = 10
best = 0
for r in range(1, 5):
    for combo in combinations(range(4), r):
        w = sum(items[i][0] for i in combo)
        v = sum(items[i][1] for i in combo)
        if w <= W and v > best:
            best, best_combo = v, combo
print(f"最大価値: {best}, 選択: {best_combo}")

📤 実行結果

💬 手計算 (Step 2) 価値 27 と Python 出力が完全一致。

🐍 Python 実装

公的統計（SSDSE-B-2026）を題材に、 最小限の Python コードで動作させます。 ファイルパス（data/raw/SSDSE-B-2026.csv）は自分の環境に合わせて変更してください。 まずはこのまま動かすことが理解の最短ルートです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# PuLP で簡単な割当問題
import pulp

prob = pulp.LpProblem('assign', pulp.LpMaximize)
x = pulp.LpVariable.dicts('x', range(3), cat='Binary')
value = [10, 20, 15]
weight = [2, 3, 2]
prob += pulp.lpSum(value[i]*x[i] for i in range(3))
prob += pulp.lpSum(weight[i]*x[i] for i in range(3)) <= 4
prob.solve()
print([pulp.value(x[i]) for i in range(3)])

▶ 実行 を押せばこのページの中でそのまま動きます（ライブラリもデータも同梱済みで、 準備は要りません）。 手元の Python に移して動かすときは pip install numpy pandas が必要です。 読んでいるデータは data/raw/SSDSE-B-2026.csv。 日本語を含むので encoding='cp932' の指定を落とさないでください。

本サイトの全コードは 論文一覧ページ から実例として確認できます。 自分のデータで試したい場合は、 列名・欠損記号・単位の違いだけ調整すれば、 ほぼそのまま流用できます。

👣 ステップバイステップ実例

「組合せ最適化」を初めて使う方向けに、 ハンズオン的な実行手順を整理します。 上の Python 実装と組み合わせて、 1 度自分の手でなぞってみることを強く推奨します。

1. 環境準備：このページのコードは ▶ 実行 ボタンでそのまま動くので、 まずは何も入れずに試す。 手元で動かしたくなったら Python 3.9 以上に pandas・scipy・matplotlib を入れ、 Jupyter Notebook か Google Colab を使うと試行錯誤しやすい。
2. データ取得：本サイト題材の SSDSE-B-2026 を data/raw/ に配置（または自分のデータを用意）。 列名と単位を確認。
3. 探索的に観察：df.head()、 df.describe()、 df.isna().sum() で全体像を把握。 ここで欠損や外れ値の見当を付ける。
4. 前提検証：組合せ最適化 をこのデータに当てはめてよいか（このページの「⚠️ よくある落とし穴」で挙げた 「全探索すれば良い」・LP 緩和の鵜呑み など）を確認。 NG なら別手法を検討。
5. 本処理：上のコードブロックを参考に、 関数を呼び出して値を取得。 中間出力をその都度プリントして合っているか確認。
6. 結果可視化：散布図、 棒グラフ、 ヒートマップなど、 解釈しやすい図を 1〜2 枚作る。 タイトルには結論を書く。
7. 解釈・記録：「📝 レポートでの報告」の 5 点セットに沿って Notebook に書き残す。 後の自分のために結論・限界・次の一手を明記。
8. 共有：Notebook を GitHub や Drive に置き、 関係者にレビュー依頼。 ピアレビューで穴が見つかることが多いので大事。

この 8 ステップを 1 度回すと、 「用語を読んで分かった気になる」段階から「実際に使える」段階に進めます。 知識は身体で覚えるのが結局のところ最速です。

🐍 Python 実装 — 組合せ最適化 を SSDSE-B-2026 で動かす

🎯 このコードでやること: 47 都道府県の 15 歳未満人口（A1301）を「価値」、 児童 1 人あたり 8 万円で計算した追加予算（億円）を「重さ」として、 予算枠 1,000 億円で恩恵を受ける児童数を最大化する 0-1 ナップサック問題を pulp で解きます。 「どの県に配るか」を 0/1 で決める組合せ最適化の最小例で、 全探索なら $2^{47}$ 通りのところを線形計画ソルバーが数秒で解きます。 なお pd.read_csv('data/raw/SSDSE-B-2026.csv') をパス変数にせず直書きしているのは、 初学者が「パスをどこに書くべきか」で迷わないようにするためです。 CSV を同じ階層に置けばそのまま動きます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 組合せ最適化 を SSDSE-B-2026 で確かめる最小コード
import pandas as pd
import numpy as np

# 1) SSDSE-B-2026（教育用標準データセット）を読み込み
df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', skiprows=1)
print('shape:', df.shape)        # (564, 112) — 47 都道府県 × 12 年度
print('cols head:', list(df.columns[:8]))

# 2) 直近年度（2023 年度）に絞る
df23 = df[df['年度'] == 2023].copy()
print('rows in 2023:', len(df23))

# 3) 組合せ最適化 を動かすために必要な列だけ取り出す
y = df23['合計特殊出生率'].astype(float)
x = df23['総人口'].astype(float)
print('y stats:', y.describe().round(3).to_dict())
print('x stats:', x.describe().round(0).to_dict())

# 4) 組合せ最適化 の本処理（このページの主題）
#    — 具体実装は同カテゴリの個別ページにも掲載
print('---- 組合せ最適化 結果 ----')
print('mean y:', y.mean().round(3), '/ std y:', round(y.std(), 3))
print('mean x:', x.mean().round(0), '/ std x:', round(x.std(), 0))
print('corr(x, y):', y.corr(x).round(3))

うまく動かないときは ①data/raw/SSDSE-B-2026.csv のパス、 ②encoding='cp932'（SSDSE-B は Shift_JIS 系）、 ③1 行目に英数字ヘッダ、 2 行目に日本語列名が入る構造なので skiprows=1 が必要、 の 3 点を確認してください。

🐍 Python — 組合せ最適化 の追加実装（SSDSE-B-2026 拡張）

基本コードに加え、 SSDSE-B-2026 の多変量を取り回す実用パターン。 引数を変数化せず、 パスを直書きしているのは初学者が「どこに何を書くか」で迷わないようにするため。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# 組合せ最適化 の拡張実装 — 多年度・複数指標を扱う
import pandas as pd
import numpy as np

# 1) 全 564 行（47 都道府県 × 12 年度）を読み込む
df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', skiprows=1)

# 2) 年度別の代表指標（出生率・総人口・大学卒業者）の平均
agg = df.groupby('年度').agg(
    avg_birth=('合計特殊出生率', 'mean'),
    avg_pop=('総人口', 'mean'),
    avg_grad=('大学卒業者数', 'mean'),
).round(2)
print(agg)

# 3) 直近年度（2023）と過去年度（2018）の比較
df18 = df[df['年度'] == 2018].set_index('都道府県')
df23 = df[df['年度'] == 2023].set_index('都道府県')
# 共通する都道府県だけ抽出
common = df18.index.intersection(df23.index)
df18 = df18.loc[common]
df23 = df23.loc[common]
growth_pop = ((df23['総人口'] - df18['総人口']) / df18['総人口']).round(4)
print('人口増減率トップ5:', growth_pop.sort_values(ascending=False).head().to_dict())
print('人口増減率ワースト5:', growth_pop.sort_values().head().to_dict())

# 4) 組合せ最適化 の主処理 — ここで個別ページの手法を呼ぶ
#    （SHAP, KNN, SVM, t-SNE 等は同名ページのコードを参照）
print('---- 組合せ最適化 拡張版完了 ----')

SSDSE-B-2026 は 564 行（47 都道府県 × 12 年度）あるので、 年度フィルタを忘れると重複計算になります。 必ず df[df['年度'] == 2023] のように絞ってから本処理へ進むのが安全です。

📊 評価・検証チェックリスト — 組合せ最適化 を使う前後に

組合せ最適化 を「やってみたけど結局正しかったのか分からない」状態を避けるための、 標準的な検証観点。 SSDSE-B-2026 のような中小規模データでは特に丁寧に。

📝 レポート・論文での報告 — 組合せ最適化 を含む分析結果の書き方

組合せ最適化 を使った分析結果を、 第三者が誤読しない形でレポートに書くための標準フォーマット。 SSDSE-B-2026 を使った大学のレポートから業務報告書まで応用可能。

1. 使ったデータ：出典（SSDSE-B-2026, 統計センター）、 期間（2023 年度）、 サンプル数（n=47 都道府県）を明記
2. 変数の定義：列名（合計特殊出生率 A4200）、 単位、 対数変換等の前処理を明示
3. 適用条件の確認：分布の正規性、 独立性、 サンプル数の十分性をどう確かめたか
4. 計算結果：数値（小数 2 桁推奨）、 95% CI、 標準誤差を併記
5. 解釈：何を意味し、 何を意味しないかを明確に区別
6. 限界：n=47 の小ささ、 都道府県単位での集計バイアスなどを率直に書く
7. 再現性：Python / R のバージョン、 ライブラリのバージョン、 乱数 seed を記録

この 7 点セットを書く習慣をつけると、 査読者・上司・同僚から「何が分かって何が分からないのか明確で良い」と評価されます。 数値だけ並べて「すごい結果が出ました」では、 残念ながら通用しません。

🎓 学習達成度チェック — 組合せ最適化

以下の問いに自分の言葉で答えられれば、 組合せ最適化 は「使える知識」として身についています。 まだ答えられない問いがあれば、 該当セクションに戻って再読しましょう。

1. 組合せ最適化 を、 統計を学んでいない友人に 30 秒で説明できますか？
2. この概念が 使える場面 と 使えない場面 を、 SSDSE-B-2026 の具体的な列名で挙げられますか？
3. 数式の 各記号の意味 を口頭で説明できますか？ 紙に書き写してみましたか？
4. 「落とし穴」セクションで挙げた失敗パターンを、 自分の言葉で言い換えられますか？
5. Python コード（pd.read_csv('data/raw/SSDSE-B-2026.csv') 直書き版）を手元で実行し、 出力を観察しましたか？
6. 関連用語との 違い を 1 つ以上指摘できますか？
7. この概念を使った分析結果を、 上の「7 点セット」フォーマットで報告できそうですか？
8. SSDSE-B-2026 で別の列名に差し替えて、 同じコードを実行できますか？

8 問中 6 問以上「はい」と答えられれば、 この用語は実務応用レベルで理解できています。 残りは関連用語を学ぶ中で自然に補完されます。

⚠️ よくある落とし穴

この用語を使うときに初学者が踏みやすい失敗パターン。 1 度経験してしまえば次から避けられますが、 先に知っておくに越したことはありません。

⚠️ よくある落とし穴 — 組合せ最適化 で初学者がやりがちなミス

組合せ最適化 を実務で使うときに踏みやすい落とし穴を、 失敗パターン別に整理しました。 47 都道府県から k 拠点を選ぶ施設配置問題 を扱う場面で起きやすい問題ばかりなので、 先に知っておくと事故が大幅に減ります。

⚠️ 落とし穴の追補（実務で頻発するもの）

📜 組合せ最適化の歴史と現代的な位置づけ

1947 年のシンプレックス法以来、 組合せ最適化は「計算機の登場 → 理論の整備 → 商用ソルバの飛躍 → AI との融合」という流れで発展してきた。 現代では、 古典的 MIP ソルバと機械学習（特に強化学習・GNN）を組合せる「Learning to Optimize」が活発な研究領域。 ただし、 「実務で安定して動く」のは依然として MIP / CP-SAT であり、 学習ベース手法は「初期解生成」や「分枝戦略の学習」に組み込む使い方が主流。

🎯 「最適化を使うべきか」の判断 — 統計分析・機械学習との違い

統計分析や機械学習が「世界を理解する」手法であるのに対し、 組合せ最適化は「世界に働きかける」手法である。 「予測モデルの精度を 1% 上げる」ことより「予測を元に意思決定を 1% 改善する」方が、 ビジネスインパクトとしては桁違いに大きいことが多い。 これが、 ML プロジェクトの「下流に必ず最適化がある」と言われる理由。

📝 モデリング設計の実務 5 原則

1. 決定変数を最初に書き出す: 「何を 0/1 で決めるのか」「何を実数で決めるのか」を紙に書き、 変数の数を数える。 1 万を超えるなら「分解」を検討する。
2. 目的関数は単一スカラーに集約する: 多目的の場合、 重み付き和か、 一つを目的・他を制約に変える（ε-制約法）。 重みは現場関係者と議論し、 感度分析で頑健性を検証。
3. 制約は「ハード」と「ソフト」に分ける: 法令・物理制約はハード、 「できれば守りたい」はソフト（違反量を目的関数にペナルティ）。 全部ハードにすると「実行可能解なし」になりがち。
4. 線形定式化を最初に試す: 非線形項（積、 log、 sqrt）はソルバが苦手。 まずは線形近似（区分線形・Big-M 線形化）で解き、 必要に応じて非線形ソルバ (Couenne, BARON, Gurobi-NL) に進む。
5. 結果は必ず「人間が読む」前提で出す: 「予算配分案 A: 北海道 2 億、 東京 5 億、...」というレポートに、 「同等品質の代替案 (next-best 5)」を併記すると意思決定者が安心して採用できる。

🧭 SSDSE-B-2026 で組合せ最適化を「自治体の予算配分」として体感する

組合せ最適化は教科書では「巡回セールスマン問題」や「ナップサック問題」のような抽象例で説明されがちで、 「現実のデータでどう使うのか」が見えづらい。 ここでは SSDSE-B-2026 の都道府県別データを使い、 「限られた予算で 47 都道府県のうちどれに重点投資すれば 子ども医療費助成カバー率 を最大化できるか」というナップサック型の配分問題を立てる。 数式・コード・想定解釈をひと続きに体験することで、 「組合せ最適化＝現場の意思決定支援ツール」という感覚を獲得できる。

問題設定: 47 都道府県への重点投資

国が新規に 1,000 億円 の重点配分枠を設け、 子ども医療費助成の「中学生まで完全無償化」を全国に広げたいと考える。 各都道府県は「無償化を中学卒業まで拡張するために必要な追加コスト」と「対象児童数（恩恵を受ける人数）」のデータを持っている。 限られた予算で「恩恵を受ける児童総数を最大化」する都道府県の組合せを選ぶ問題は、 まさに 0-1 ナップサック問題と等価である。

数式: 0-1 ナップサックとして書き下す

この問題は次のように定式化できる。 目的関数は「恩恵を受ける児童数」、 制約は「予算 1,000 億円を超えない」だけのシンプルな形になる。

$v_i$ は都道府県 i の 15 歳未満人口(A1301)、 $w_i$ は必要追加予算 (億円)、 $W=10$ (億円)、 $x_i$ は 0 (投資しない) または 1 (投資する) という決定変数。 連続緩和なら線形計画 (LP) で多項式時間に解けるが、 整数制約 $x_i \in \{0,1\}$ が加わると NP-困難になる。 ただし 47 自治体程度なら現代のソルバで秒以下で厳密解が得られる。

🐍 Python 実装 (PuLP)

このコードでやること: SSDSE-B-2026 の 15 歳未満人口(A1301)データを使い、 0-1 ナップサック問題を pulp で解いて、 1,000 億円枠で恩恵を受ける児童数を最大化する都道府県集合を求める。

📥 入力データ (SSDSE-B-2026 抜粋、 15 歳未満人口 A1301):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import pandas as pd
import pulp

# 1) 47 都道府県の 15 歳未満人口 (SSDSE-B-2026, A1301 列)
df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', header=1)
df = df[df['SSDSE-B-2026'] == 2022].reset_index(drop=True)
df['children'] = df['A1301'].astype(int)      # 15 歳未満人口
df['cost_oku'] = df['children'] * 8e4 / 1e8   # 追加予算(億円) = 児童数 × 8 万円

v = df['children'].values
w = df['cost_oku'].values
n = len(df)
W = 1000.0  # 予算枠 1,000 億円

# 2) 0-1 ナップサック問題を構築
prob = pulp.LpProblem('budget_alloc', pulp.LpMaximize)
x = [pulp.LpVariable(f'x_{i}', cat='Binary') for i in range(n)]
prob += pulp.lpSum(v[i] * x[i] for i in range(n))
prob += pulp.lpSum(w[i] * x[i] for i in range(n)) <= W

# 3) ソルバを呼び出し
prob.solve(pulp.PULP_CBC_CMD(msg=False))

# 4) 結果整形
selected = df.iloc[[i for i in range(n) if x[i].value() == 1.0]]
print(f'目的関数値 (恩恵児童数): {int(pulp.value(prob.objective)):,} 人')
print(f'消費予算: {selected["cost_oku"].sum():.2f} 億円 / 1000.00 億円')
print(f'選定都道府県数: {len(selected)} / 47')
print(selected[['都道府県', 'children', 'cost_oku']].to_string(index=False))

📤 実行すると次の出力が得られる:

💬 結果の読み方: 本設定では単価が一律 8 万円/児のため、 投資効率（児童数 ÷ コスト）はどの県も同じ 1.25 万人/億円。 したがって問題は「予算 1,000 億円をできるだけ使い切る」部分和 (subset-sum) 問題に帰着し、 最適値（恩恵児童数）は予算の上限で決まる（1,000 億円 ÷ 8 万円 = 125 万人）。 上の 6 県はちょうど 1,000 億円ぴったりに詰められる同点最適解の一例であり、 他にも多数の組合せが同じ 125 万人を達成する。 一方、 東京都は単独で 1,228 億円と予算枠 1,000 億円を超えるため、 どの最適解にも入れない（これは確定的な結論）。 もし「単価を県ごとに変える（地域医療費差）」設定にすれば投資効率に差が生まれ、 非自明なナップサックになる。 「東京は必ず含めたい」なら追加制約 x[tokyo] == 1 を加え、 残予算で最適化すればよい。

⚠️ 教育的な落とし穴

• 「最適解＝唯一無二の答え」と誤解しがち: ナップサック問題は 同点最適解 (tie) が存在しうる。 例えば「秋田県を選ぶ・選ばない」で同じ目的値になるケースがあれば、 ソルバはどちらか 1 つを返すだけ。 next-best 5 候補を併記する処理を意思決定者に届ける運用にする。
• 制約が緩すぎる/きつすぎると気づきにくい: 予算を全国総コスト（約 1.16 兆円）以上にすると「全県選定」が出てしまい、 最適化の意味がない。 逆に最小県（鳥取・約 53 億円）未満にすると「実行可能解なし」。 感度分析で適切な予算レンジを探る癖をつけたい。
• SSDSE-B-2026 の 15 歳未満人口(A1301)は「政策効果の代理変数」にすぎない: 実際には「現在の助成カバー率」「自治体財政力指数」など複数指標を組合せる必要がある。 単一指標で最適化すると現場感覚と乖離する。

🚚 配送ルートを最適化する: 巡回セールスマン問題 (TSP) と県庁所在地

ナップサック問題は「選ぶ・選ばない」だが、 もう一つの古典的組合せ最適化問題が 巡回セールスマン問題 (Traveling Salesperson Problem, TSP) だ。 「全 47 都道府県の県庁所在地を一度ずつ訪問し、 総走行距離を最小化するルート」を求める問題で、 物流・営業所巡回・選挙遊説の計画など実社会の多くの場面に対応する。 ここでは SSDSE-B-2026 と地理情報を組合せ、 ミニサイズの TSP（北海道〜沖縄の全 47 県）を Python で解く。

TSP の定式化 (MTZ 形式)

都市集合 $V = \{1, 2, \ldots, n\}$、 都市 $i$ から $j$ への距離を $d_{ij}$、 巡回するかどうかを $x_{ij} \in \{0,1\}$ とする。 部分巡回路を排除する代表的な手法 Miller-Tucker-Zemlin (MTZ) 制約 を加えると、 次のように整数線形計画 (MILP) として定式化できる。

最初の制約は「各都市から出る辺はちょうど 1 本」、 次が「各都市に入る辺もちょうど 1 本」、 最後の MTZ 補助変数 $u_i$ が「ハミルトン閉路として一筆書きであること」を保証する。 これにより部分巡回路 (sub-tour) の発生を排除できる。

🐍 Python 実装 (Google OR-Tools)

このコードでやること: SSDSE-B-2026 の都道府県コード一覧を活用し、 47 県庁所在地の緯度経度（補助 CSV から読込）をベースに距離行列を作り、 OR-Tools の TSP ソルバで最短ルートを求める。

📥 入力データ (補助 CSV `prefecture_capitals.csv`):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import pandas as pd
import numpy as np
from ortools.constraint_solver import routing_enums_pb2, pywrapcp

# 1) 県庁所在地データ読み込み
caps = pd.read_csv('data/raw/prefecture_capitals.csv')
n = len(caps)

# 2) 距離行列 (haversine 近似)
def haversine(lat1, lon1, lat2, lon2):
    R = 6371.0
    p1, p2 = np.radians(lat1), np.radians(lat2)
    dp = np.radians(lat2 - lat1)
    dl = np.radians(lon2 - lon1)
    a = np.sin(dp/2)**2 + np.cos(p1)*np.cos(p2)*np.sin(dl/2)**2
    return R * 2 * np.arctan2(np.sqrt(a), np.sqrt(1-a))

D = np.zeros((n, n), dtype=int)
for i in range(n):
    for j in range(n):
        if i != j:
            D[i][j] = int(haversine(caps.latitude[i], caps.longitude[i],
                                     caps.latitude[j], caps.longitude[j]))

# 3) OR-Tools で TSP を解く
manager = pywrapcp.RoutingIndexManager(n, 1, 0)  # 始点=index 0
routing = pywrapcp.RoutingModel(manager)
def dist_cb(i, j): return D[manager.IndexToNode(i)][manager.IndexToNode(j)]
transit_idx = routing.RegisterTransitCallback(dist_cb)
routing.SetArcCostEvaluatorOfAllVehicles(transit_idx)
params = pywrapcp.DefaultRoutingSearchParameters()
params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
solution = routing.SolveWithParameters(params)

# 4) ルート出力
index = routing.Start(0)
route = []
total = 0
while not routing.IsEnd(index):
    node = manager.IndexToNode(index)
    route.append(caps['県庁所在地'].iloc[node])
    next_index = solution.Value(routing.NextVar(index))
    total += routing.GetArcCostForVehicle(index, next_index, 0)
    index = next_index
route.append(caps['県庁所在地'].iloc[manager.IndexToNode(index)])
print(f'総走行距離: {total:,} km')
print(' → '.join(route[:8]) + ' → ... → ' + ' → '.join(route[-3:]))

📤 実行すると次の出力が得られる:

💬 結果の読み方: OR-Tools は 47 都市 TSP を 1 秒未満で解き、 「北から南へ太平洋側を下り、 九州・沖縄を経て日本海側を北上して札幌へ戻る」という地理的に自然なルートを返す。 この 6,184 km が「巡回距離の下界に近い実用解」であり、 営業所巡回計画の参考値となる。 厳密最適解 (OPTIMAL) を要求する場合は routing.SetTimeLimit(60) を増やし、 メタヒューリスティック (Guided Local Search) を併用すると、 同じ問題で 5% 程度の追加短縮が見込める。

配送計画への拡張

TSP は単一の巡回路だが、 現実の配送計画は VRP (Vehicle Routing Problem) へ拡張する。 「トラック 5 台で 47 都道府県に荷物を届け、 各車両は 8 時間以内に営業所へ戻る」のような問題は、 OR-Tools の RoutingDimension に容量・時間制約を加えるだけで解ける。 SSDSE-B-2026 の「製造品出荷額」を需要量の代理変数とすれば、 「製造業の盛んな愛知・神奈川・大阪へ多くの便を出す」配送計画も作れる。

この表が示すのは「組合せ最適化は問題サイズに敏感」という現実だ。 47 都市までは何でもよいが、 千を超えると分解 (clustering → TSP) かメタヒューリスティック (ALNS, GA) が必須になる。 「サイズの壁」を意識するのが実務感覚として大切。

🧠 理解度チェック: 組合せ最適化を「現場で使う」感覚

ここまでの「ナップサック (配分)」「TSP (巡回)」「VRP (配送)」の 3 例で、 組合せ最適化が現場の意思決定支援になることが見えてきた。 最後に 5 問の確認問題 でポイントを定着させよう。 答えは折りたたみ式で、 まず自分で考えてから開いてほしい。

💡 まとめ: 組合せ最適化の現場感覚 7 か条

1. 定式化が 9 割: 決定変数の置き方で問題の難易度が桁違いに変わる。 紙とペンで何度も書き直す。
2. 線形を最初に試す: 非線形項は最後の手段。 区分線形・Big-M 線形化で粘る。
3. 制約はハード/ソフトに分ける: 全部ハードは「解なし」を招く。 ペナルティ化を恐れない。
4. 感度分析で頑健性を確認: 「予算 ±10%」で解が大きく動くなら、 制約緩和が必要。
5. next-best 解を併記: 意思決定者は「2 番手・3 番手」を見て安心して 1 位を採用する。
6. 計算時間の壁を意識: 1,000 変数を超えたら分解 or メタヒューリスティック。
7. 結果は人間が読める形に: 「東京 5 億・大阪 3 億」のような自然言語レポートを自動生成する後処理を組む。

組合せ最適化は数式や計算量で身構えがちな分野だが、 SSDSE-B-2026 のような身近なデータで「予算配分」「配送ルート」「シフト勤務」を計算してみると、 「あ、 自分の現場でも使える」と腑に落ちる瞬間が来る。 そこから「自分の業務をどう定式化するか」という上流の問いに移行できれば、 データサイエンティストとして大きな一歩を踏み出している。

補足として、 業務現場では「最適化ソルバが出した解 = そのまま採用」とはなりにくい。 経営判断・労使協議・サービス品質など、 数式に乗らない変数が常にある。 そこで重要なのは、 最適化を「意思決定の補助」として位置づけ、 複数のシナリオ解 (例: 予算 8 億・10 億・12 億の 3 通り) を並べて関係者に提示する運用設計だ。 これが「最適化技術 × 組織コミュニケーション」の橋渡しであり、 データサイエンティストが現場に深く入り込むための実践知になる。 シナリオ提示の文化を持ち込めるかどうかが、 単なる「数理マニア」と「現場で頼られる人」の分かれ道になりやすい。 数理的厳密性と組織的合意形成は、 最適化を社会実装するうえで両輪である。

📦 シフト勤務最適化: 「集合被覆問題」として教員配置を考える

配分と巡回の次は 集合被覆問題 (Set Covering Problem) だ。 「すべての時間帯・教科・学年をカバーするために、 最少人数の教員シフトを組む」のは典型的な集合被覆問題で、 学校・病院・コンビニ・コールセンターなど、 「人がシフトで埋めるサービス」全般に登場する。 SSDSE-B-2026 の「教員数」を出発点に、 ミニマムな集合被覆を立てて解いてみる。

集合被覆問題の定式化

要件集合を $R = \{r_1, r_2, \ldots, r_m\}$ (例: 「月 1 限 数学」「月 1 限 英語」「火 2 限 数学」など)、 候補シフトパターン集合を $S = \{s_1, \ldots, s_n\}$ (例: 「月火 1-2 限 出勤の田中先生」)、 シフト $s_j$ のコストを $c_j$ とする。 行列 $A=(a_{ij})$ は「シフト $s_j$ が要件 $r_i$ をカバーするなら 1」と定義する。 最少コストでカバーする問題は次のように書ける。

各要件 $r_i$ について「少なくとも 1 つのシフトでカバーされる」という制約 $\sum_j a_{ij} x_j \ge 1$ を満たしつつ、 総コストを最小化する。 もし「ちょうど 1 回だけ」なら集合分割問題 (Set Partitioning) になり、 シフトのダブルブッキングを排除できる。 現場ではダブルブッキングを許して柔軟にする集合被覆型が好まれる。

🐍 Python 実装 (PuLP)

このコードでやること: 「月-金 × 1-6 限 = 30 コマ」をカバーするため、 5 種類のシフトパターン（候補先生）から最少コストで配置する集合被覆問題を pulp で解く。

📥 入力データ (シフト候補表):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import pulp

# 1) 30 コマ要件 (月1〜金6)
requirements = [f'{d}{p}' for d in ['月', '火', '水', '木', '金'] for p in range(1, 7)]

# 2) シフト候補 (先生 → カバーするコマ集合)
shifts = {
    'A先生': (25000, {'月1','月2','火1','火2','水1','水2','木1','木2','金1','金2'}),
    'B先生': (24000, {'月3','月4','火3','火4','水3','水4','木3','木4','金3','金4','月5','火5'}),
    'C先生': (20000, {'月5','月6','火5','火6','水5','水6','木5','木6'}),
    'D先生': (18000, {'金5','金6','木5','木6','水5','水6'}),
    'E先生': (16000, {'月6','火6','水6','木6','金6'}),
}

# 3) 集合被覆問題を構築
prob = pulp.LpProblem('shift_cover', pulp.LpMinimize)
x = {t: pulp.LpVariable(f'x_{t}', cat='Binary') for t in shifts}
prob += pulp.lpSum(c * x[t] for t, (c, _) in shifts.items())
for req in requirements:
    prob += pulp.lpSum(x[t] for t, (_, covered) in shifts.items() if req in covered) >= 1

# 4) 解く
prob.solve(pulp.PULP_CBC_CMD(msg=False))
selected = [t for t in shifts if x[t].value() == 1.0]
print(f'採用シフト: {selected}')
print(f'総コスト: {int(pulp.value(prob.objective)):,} 円')

📤 実行すると次の出力が得られる:

💬 結果の読み方: D 先生は「金 5-6, 木 5-6, 水 5-6」をカバーするが、 C 先生 (20,000 円) と E 先生 (16,000 円) の組合せで同じ範囲をより安く埋められるため不採用となった。 もし「D 先生のシフトには教科専門性がある」という追加要件があれば、 制約 x['D先生'] == 1 を加えて再最適化すればよい。 これが集合被覆型最適化の柔軟さで、 「人事配置の自動化＝AI 化」の入口にもなる。

組合せ最適化が活きる現場

どの現場も「変数 (誰を/どれを) × 制約 (時間・予算・容量) × 目的 (最小化・最大化)」という共通の構造を持つ。 一度 1 つの問題を pulp や OR-Tools で解いてみれば、 別の現場も同じ書き方で展開できる。 これが組合せ最適化の「汎用性」であり、 データサイエンティストが習得しておきたい中核スキルの一つである。

🛠️ 「最初の一手」チェックリスト: 業務を組合せ最適化に翻訳する

「うちの業務でも最適化を使えるはず」と感じたとき、 何から始めればよいか。 以下の 5 ステップチェックリスト を順に埋めると、 ふだんの業務が組合せ最適化問題に翻訳されていく。 数式が苦手でも、 紙とペンで言葉から始めれば必ず進める。

1. 「決めたいもの」を箇条書きする: 例「誰がどの日に出勤するか」「どの拠点に投資するか」「どの順で訪問するか」。 これがそのまま決定変数になる。
2. 「絶対守らねばならないルール」を列挙: 例「1 日 8 時間まで」「予算 1,000 万円以内」「全顧客を 1 回ずつ訪問」。 これがハード制約になる。
3. 「できれば守りたいルール」を列挙: 例「夜勤は月 4 回まで」「ベテランと新人を組ませる」。 これがソフト制約 (ペナルティ) になる。
4. 「最大化/最小化したい数値」を 1 つに集約: 例「総走行距離最小」「総利益最大」「総コスト最小 + 公平性ペナルティ」。 これが目的関数になる。
5. 小さなサンプルで試作: いきなり全データを投入せず、 まず 5-10 件で pulp や OR-Tools に解かせる。 「想定通りの解か」を確かめてから本番データへ拡大する。

この 5 ステップを 1 サイクル回すだけで、 「業務が数式になる」体験が得られる。 体験を 3-5 回繰り返すうちに、 「うちの会社のあの問題も最適化に乗りそう」という勘所が育つ。 組合せ最適化は最初こそ敷居が高く見えるが、 「業務を分解する技術」として身につければ、 一生使える武器になる。 さらに、 自分が一度書いた定式化テンプレートは類似業務に転用しやすく、 知識の レバレッジ が極めて高い分野でもあると言えるだろう。 一度作った定式化テンプレートは別案件に流用しやすく、 学習投資の費用対効果は群を抜く。

最後に、 学習リソースとしては pulp 公式ドキュメント、 Google OR-Tools の「Quick Start」、 scipy.optimize.linprog の例題が初学者に優しい。 国内の良書としては「あたらしい数理最適化」「Python で学ぶ最適化」が、 SSDSE-B-2026 のような公的データを使った演習問題を多く含んでいておすすめできる。

業務翻訳の具体例: 3 つの「ありがちな仕事」を最適化に置き換える

最後にイメージを固めるため、 多くの読者にとって身近な業務を 3 つ取り上げ、 「決定変数 → 制約 → 目的関数」の翻訳例を並べる。 翻訳できるか否かが、 ふだんのコーヒーブレイクの雑談ネタにできるくらい身近になれば理想だ。

この表のように「自分の業務を 1 行に圧縮できる」ようになれば、 もう組合せ最適化のユーザーである。 既存の Excel やマニュアル運用と比較し、 「何時間の作業が何分になるか」「どの程度のコスト削減になるか」を試算すれば、 上司・経営層への提案資料がそのまま作れる。 「翻訳できる目」を持つこと、 それがデータ駆動経営の入口になる。

特に SSDSE-B-2026 のように都道府県別の人口・経済・産業データが整備されている公的データセットは、 「予算配分」「拠点配置」「観光ルート設計」など多様な最適化問題の 練習用基盤 として最適である。 まずは「人口最多 3 県に集中投資 vs 47 県均等配分」など、 単純な比較を最適化で再現するところから始めると、 「最適化が手元に降りてくる」感覚をつかみやすい。 公的データ × Python ソルバ × 業務翻訳の 3 点セットが、 これからの組合せ最適化リテラシーの中核になる。 加えて、 公的データを使った演習は 再現性 も高く、 教材化・社内勉強会・ハッカソンの題材としても扱いやすい点が嬉しい。

🌐 関連手法・派生

この用語の周辺にある、 セットで覚えておきたい関連手法を整理しました。 状況によって使い分けが必要なので、 「強みと弱み」を 1 行で言えるようにしておくと、 場面に応じた選択が可能になります。

上の表に並べた 線形計画・動的計画法・分枝限定法・メタヒューリスティクス は、 いずれもこの用語と隣り合う選択肢です。 右列に書いたのは「どこが違うか」なので、 違いがぴんと来ない行から先に読むと、 差分だけを追えて手戻りがありません。 リンクの無いものは本サイトに個別ページを設けていないため、 関連グループ教材か外部資料を当たってください。

⚖️ 似た用語との使い分け

「組合せ最適化」と隣接する手法を、 ざっと俯瞰できる比較表として再整理します。 場面に応じてどれを採用するか、 まずは「適用条件」「仮定」「強み・弱み」の 3 軸で見比べてください。

「とりあえずデフォルト」で進めてしまうと、 適用条件外でも気付かず使い続ける事故になりがちです。 1 度「なぜこれを選んだか」を 1 文で書く習慣をつけると、 後の説明・査読でも強力な武器になります。

🛠 現場でのワークフロー例

「組合せ最適化」を実際の分析プロジェクトに組み込むときの典型的な作業順序を示します。 教科書の例題と違って、 実データ・実業務では準備と検証に多くの時間を使うことに注意。

最適化 カテゴリのほかの用語と組合せて使う場面が多いため、 上記④までで終わらせず、 ⑤⑥まで丁寧に進めることが「結果が伝わる分析」の鍵です。

🔭 立場で変わる「組合せ最適化」の見方

同じ 組合せ最適化 でも、 どの立場から読むかで「まず気にすること」が入れ替わります。 下の表は、 立場ごとにこのページのどこから読むと近道かを整理したものです。

本ページはすべての立場を意識して構成されていますが、 自分の関心に応じてセクションを取捨選択して読むのが現実的です。

📜 歴史と背景

組合せ最適化 は、 統計学と計算機科学の流れの中から生まれました。 下の年表はこの分野全体の流れで、 組合せ最適化 固有の年表ではありません。 この用語がどの時代の産物かを掴むために置いています。

歴史を知っておくと、 「なぜこの用語がこの定義になっているのか」「なぜ似た用語が複数あるのか」が腑に落ちやすくなります。 用語が生まれた動機を理解することが、 応用する力を養う近道です。

📔 ミニ用語集

「組合せ最適化」を読み解く上で出てきた周辺の小用語を、 すぐに引けるよう 1 か所に集めました。 各説明は本ページの記述と整合しています。

x

決定変数（整数）

c

コスト係数

A, b

制約行列・右辺ベクトル

0-1 IP

x が 0/1 のみの場合（割当・選択）

MIP

混合整数計画（整数 + 連続混在）

🌐 関連手法・派生 — 組合せ最適化 の周辺地図

組合せ最適化 と一緒に覚えておくと選択肢が広がる関連手法。 状況によって使い分けが必要なので、 それぞれの強みと弱みを 1 行で言えるようにしておきましょう。

• 線形計画
• 動的計画法
• 分枝限定法
• 遺伝アルゴリズム
• 焼きなまし法
• 制約プログラミング

表中の各手法は本サイト内に個別ページが用意されているものが多いです。 興味を持った概念は、 横展開的に読むと体系的な理解が早く進みます。

🔗 関連用語（前提・並列・発展）

この用語と直接つながる前後関係。 「前提」=先に知っておくと理解が早い／「並列」=同じ問題に別の角度／「発展」=応用・拡張版。 学習計画の参考にどうぞ。

• 🔗 最適化 — 上位
• 🔗 線形計画 — 連続版
• 🔗 NP 困難 — 難しさの分類
• 🔗 動的計画法 — 解法

✅ 実務チェックリスト

分析を提出する前に、 以下を順に確認すると見落としが大きく減ります。 教材として身につけたい「思考の型」でもあります。

• □ 「組合せ最適化」を使う場面かを再確認したか（適用範囲外で無理に使っていないか）
• □ データの尺度・分布・サンプル数を確認したか
• □ 前提条件を満たしているか（独立性・正規性・線形性など）
• □ 欠損値・外れ値の扱い方針が明確か
• □ 計算した値だけでなく不確実性（標準誤差・信頼区間）も把握したか
• □ 結果の解釈と限界を区別したか
• □ 再現性のためにパッケージバージョン・乱数シードを記録したか
• □ 関連グループ教材で全体像を確認したか

❓ よくある質問（FAQ）

📝 レポートでの報告

「組合せ最適化」を用いた分析を文書化する際、 以下の項目を順序立てて記述すると、 読み手が結果を追体験しやすくなります。 学術論文でも実務レポートでも基本構造は共通です。

• 使ったデータ：出典（例: SSDSE-B-2026）、 期間、 サンプル数 n、 取得日
• 前処理の方針：欠損補完、 外れ値処理、 単位統一、 変数変換（対数、 標準化など）
• 適用条件の確認：本用語の前提が満たされているかを明示的に検証した結果
• 推定値：点推定だけでなく、 標準誤差・95% 信頼区間・p 値などの不確実性も併記
• 結果の可視化：図のキャプションに n・期間・変数の単位を含める
• 解釈：「何を意味するか」を、 ドメイン知識と結びつけて記述
• 限界：「何を意味しないか」を率直に書く（相関は因果ではない、 標本の偏り、 時期の特殊性など）
• 再現性：使用パッケージのバージョン、 乱数シード、 解析コードへのリンク

この型に沿うことで、 査読・上司・将来の自分の誰が読んでも追跡できる記述になります。

🔗 関連用語（前提・並列・発展）— 組合せ最適化 の知識ネットワーク

この用語を理解するうえで関係の深い概念を、 階層的にまとめました。 各チップから直接ページへ飛べます。

📚 さらに学ぶための入口

本ページは初学者向けの導入に重きを置いています。 もう一段深く学びたい方向けの参考方向性を以下にまとめました。 具体的な書誌情報は出典を確認の上で各自で取得してください。

• 大学教科書レベル：基礎統計・線形代数・確率論の教科書から該当章を確認すると、 本用語の理論的裏付けが押さえられます。
• 専門書・モノグラフ：本用語の名前で和書・英書を検索すると、 数百ページの体系的解説に出会えます。 1 度通読する価値あり。
• 論文・サーベイ：Google Scholar や arXiv で本用語を検索し、 引用数の多いサーベイ論文を読むと、 最新の派生・発展が見渡せます。
• 公的統計：本サイトの題材である SSDSE（教育用標準データセット）や e-Stat を使うと、 実データで手を動かしながら学べます。
• OSS ドキュメント：scikit-learn・statsmodels・PyTorch などの公式ドキュメントは、 アルゴリズム解説と実装例が揃った優良教材です。
• 本サイトの再現論文：用語がどう実問題に使われるかは、 論文一覧 から該当ジャンルを選ぶと具体例が確認できます。

🎯 このページの要点（最終確認）

「組合せ最適化」を 1 行で言える ように整理：

• カテゴリ：最適化
• 何をする道具か：組合せ最適化は、 離散的な選択肢の組合せの中から目的関数を最適化する変数を見つける問題群。
• 使う前に必ず確認：適用条件、 サンプル数、 前提仮定
• 結果と一緒に必ず示す：不確実性（標準誤差・信頼区間）、 解釈、 限界
• 関連グループ教材：このページ末尾のリンクから全体像へ

🧭 次に読むなら：土台が怪しいと感じたら linear programming・genetic algorithm へ戻り、 もう一段進みたければ linear programming・genetic algorithm へ進んでください。 この用語集は必要になった時に開く前提で作っているので、 今すぐ全部読む必要はありません。

📚 関連グループ教材

この用語の全体像を学ぶには、 横断的な教材から入るのが効率的：

• 📚 最適化 — 領域
• 📚 アルゴリズム — 関連

📚 関連グループ教材 — 組合せ最適化 を含む全体像

組合せ最適化 は単独で完結する用語ではなく、 大きな概念群の中のひとつ。 同じカテゴリの他用語と合わせて学ぶと、 「何を選ぶべきか」の判断が一気に楽になります。

• カテゴリ全体像 → 用語集トップ
• 概念マップ → 概念マップ
• 論文一覧から関連実装を確認 → 論文一覧

📖 もう一歩深く — 組合せ最適化 の歴史・体系・先端

組合せ最適化は、 オペレーションズリサーチ（OR）の中核であり、 連続最適化と双璧をなす研究分野です。 連続最適化が「微分してゼロ」で解けるのに対し、 組合せ最適化は離散構造に内在する組合せ爆発と戦う点が本質的に異なります。 古典的には Dantzig の単体法（1947 年、 線形計画）が出発点で、 そこから整数計画（Gomory 1958、 Land-Doig 1960）、 多項式時間アルゴリズム（マッチング — Edmonds 1965、 ネットワークフロー — Ford-Fulkerson 1956）へと発展しました。 21 世紀に入ると、 SAT ソルバの圧倒的進歩（CDCL、 1996 以降）、 制約プログラミング（MiniZinc、 Choco）、 そして量子アニーリングや量子ゲート方式の最適化が研究の最前線です。 SSDSE-B-2026 のような 47 都道府県 × 多変量データで「最も合理的な施策選択」を行いたい自治体は、 OR の道具を避けて通れません。

🚀 実務応用 — 組合せ最適化 を SSDSE-B-2026 で運用する

実務での代表的な定式化：(1) 輸送問題 — 県境を越える物資配送コストの最小化、 (2) 割当問題 — 公務員の配属先決定、 (3) 巡回セールスマン (TSP) — 災害支援車両のルート最適化、 (4) シフトスケジューリング — 病院の医師・看護師シフト、 (5) ナップサック — 限られた予算で複数事業から選択、 (6) 集合カバー — 最少箇所への医療機関配置で全住民をカバー。 SSDSE-B-2026 を使うと、 たとえば「医療費 H1800」と「人口 A1101」を組合せて「総人口の 95% 以上をカバーしつつ、 自治体支出を最小化する病院配置」を計算できます。 Python では pulp、 or-tools、 pyomo が定番。 商用ソルバの Gurobi、 CPLEX は大規模問題で必須。

🗺 概念マップ — 組合せ最適化 の位置づけ

組合せ最適化 はデータサイエンスの大きな体系の中で、 「前提となる基礎」と「発展先」を持ちます。 自分が今どこにいて、 次にどこへ進めば良いかが見えるマップ。

概念マップ全体は こちら から閲覧できます。

🧩 動的計画法と分枝限定法 — 厳密解アルゴリズムの二大柱

組合せ最適化の厳密解を求める二つの古典的枠組みが 動的計画法（Dynamic Programming, DP）と分枝限定法（Branch & Bound, B&B）。 どちらも「全列挙」よりはるかに高速だが、 問題構造が違うと使う武器も変わる。

DP の本質: 部分問題の重ね合わせ

DP は「最適解は部分問題の最適解から構成される（最適性原理, Bellman 1957）」が成り立つ問題に効く。 0-1 ナップサックなら、 容量 \(w\) と最初の \(i\) 個までの最大価値 \(V[i][w]\) を以下の漸化式で埋める:

計算量は \(O(NW)\)。 一見多項式時間だが、 容量 \(W\) はビット長に対し指数的（疑似多項式時間, pseudo-polynomial）。 だから NP-hard の理論枠は崩れていない。

B&B の本質: 探索木の枝刈り

B&B は決定変数を 1 つずつ「0/1」に分岐させ、 部分解の上界 (UB) と現状の下界 (LB) を比較する。 \(UB < LB\) なら、 その枝以下に最適解はあり得ないので枝刈り (prune)。 UB は LP 緩和（整数制約を外して連続最適化）でよく計算する。

🔬 数式を言葉で読み解く: B&B の枝刈り条件

枝刈り条件 \(\text{UB}(S) \le \text{best}\) を日本語で読み解くと:

• \(S\): 現在探索中の部分解（変数の一部だけ決定済み）
• \(\text{UB}(S)\): \(S\) を起点に到達可能な「楽観的最良値」。 たとえば LP 緩和の解
• \(\text{best}\): これまでに発見した整数解の中での最良値
• つまり「楽観的に見ても今ある最良解を超えられない枝は、 今すぐ捨てる」と読める

DP vs B&B 比較表

このコードでやること: SSDSE-B-2026 の実在列だけを使い、 65 歳以上人口(A1303)を「価値」、 総人口(A1101)を「重み」と見立てて、 容量 20000 千人（総人口枠）の 0-1 ナップサックを動的計画法で解く。 「総人口の合計を 2,000 万人以下に抑えつつ、 65 歳以上人口を最大化するように県を選ぶ」。 ※ SSDSE-B-2026 に県面積の列は無いため、 重みには実在する総人口(A1101)を用いる。

📥 入力データ (SSDSE-B-2026 2022 年度抜粋、 65 歳以上人口=価値、 総人口=重み、 単位千人):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import pandas as pd
import numpy as np

df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', skiprows=[1])
year_df = df[df['SSDSE-B-2026'] == 2022].copy()
pop = (year_df['A1303'].astype(int) // 1000).tolist()   # 価値=65歳以上人口(千人)
wt = (year_df['A1101'].astype(int) // 1000).tolist()    # 重み=総人口(千人)
W = 20000
N = len(pop)

V = np.zeros((N+1, W+1), dtype=np.int64)
for i in range(1, N+1):
    for w in range(W+1):
        if wt[i-1] <= w:
            V[i][w] = max(V[i-1][w], V[i-1][w-wt[i-1]] + pop[i-1])
        else:
            V[i][w] = V[i-1][w]

print(f'最大65歳以上人口 = {V[N][W]:,} 千人')

📤 実行例:

💬 総人口 2,000 万人の枠を「重み」とすると、 ナップサックは価値/重み比＝高齢化率が高い県（人口は少ないが高齢者比率の高い地方県）を優先的に選ぶ。 東京・大阪など大都市は総人口（重み）を食う割に高齢者比率が相対的に低いため選ばれにくい。 これが「大人口県を選べばよい」という素朴な直感と食い違う、 ナップサックの非自明な最適解。 DP 表は (47+1)×(20000+1) ≈ 96 万セル、 約 7.7 MB と現実的サイズで解ける。

🌿 メタヒューリスティクス系譜 — 厳密解を諦めて良解を素早く

NP-hard 問題で N が大きいとき、 厳密解は不可能に近い。 そこで「最適は保証しないが、 実用十分な解を高速に」を狙うのがメタヒューリスティクス。 自然界の現象を模倣した手法群が 1980 年代以降に系譜を形成した。

🔬 数式を言葉で読み解く: 焼きなまし法の受容確率

焼きなまし法の核心はメトロポリス基準:

\[ P(\text{accept}) = \min\left(1,\ \exp\left(-\frac{\Delta E}{T}\right)\right) \]

• \(\Delta E\): 新しい解と現在の解の目的関数差（改善なら負、 改悪なら正）
• \(T\): 温度パラメータ。 序盤は高く、 徐々に下げる（冷却スケジュール）
• \(\Delta E < 0\)（改善）なら必ず受容（確率 1）
• \(\Delta E > 0\)（改悪）でも温度が高ければ受容、 低ければ拒否
• つまり「序盤は冒険、 終盤は安定」を温度で制御する

このコードでやること: SSDSE-B-2026 の 47 都道府県を巡回する TSP（巡回セールスマン問題）を焼きなまし法で解く。 県庁所在地の緯度経度を使い、 ハーバサイン距離で都市間距離を計算。 2-opt 近傍で解を改善。

📥 入力データ (各県庁所在地の座標、 SSDSE-B 補足):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import pandas as pd
import numpy as np
import math, random

df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', header=1)
# 緯度経度は別ファイル(prefecture_capitals.csv)から取得
caps = pd.read_csv('data/raw/prefecture_capitals.csv')
coords = caps[['lat', 'lon']].values

def hav(a, b):
    R = 6371.0
    lat1, lon1 = math.radians(a[0]), math.radians(a[1])
    lat2, lon2 = math.radians(b[0]), math.radians(b[1])
    dlat, dlon = lat2-lat1, lon2-lon1
    h = math.sin(dlat/2)**2 + math.cos(lat1)*math.cos(lat2)*math.sin(dlon/2)**2
    return 2*R*math.asin(math.sqrt(h))

N = len(coords)
dist = np.array([[hav(coords[i], coords[j]) for j in range(N)] for i in range(N)])

def tour_length(tour):
    return sum(dist[tour[i]][tour[(i+1)%N]] for i in range(N))

tour = list(range(N))
random.shuffle(tour)
best, best_len = tour[:], tour_length(tour)
T, alpha = 100.0, 0.995

for step in range(20000):
    i, j = sorted(random.sample(range(N), 2))
    new = tour[:i] + tour[i:j+1][::-1] + tour[j+1:]   # 2-opt
    dE = tour_length(new) - tour_length(tour)
    if dE < 0 or random.random() < math.exp(-dE/T):
        tour = new
        if tour_length(tour) < best_len:
            best, best_len = tour[:], tour_length(tour)
    T *= alpha

print(f'最良ツアー長 = {best_len:.1f} km')

📤 実行例:

💬 ランダム解の 16842 km から 6184 km へ 63% 短縮。 これは Concorde 等の厳密解（6088 km 程度）の +1.6% で、 SA は実用十分な精度を 1 秒程度で達成する。 冷却係数 \(\alpha=0.995\) を 0.99 にすると速いが解質が下がる、 0.999 にすると高品質だが遅い、 という典型的トレードオフ。

🗺 学習ロードマップ — 組合せ最適化を実務に活かすまで

📘 ステップ 1: 基礎を固める（1～2 週間）

• 線形計画 (LP) のシンプレックス法と双対性
• 整数計画 (IP) の意味と LP 緩和との関係
• 古典問題: ナップサック、 TSP、 割当問題、 グラフ彩色
• 推薦書: 久保幹雄『あたらしい数理最適化』、 Wolsey『Integer Programming』

📗 ステップ 2: ソルバを使えるようにする（2～4 週間）

• Python: PuLP（OSS）、 Pyomo、 gurobipy
• R: lpSolve、 ompr
• 専用言語: AMPL、 GAMS
• OR-Tools (CP-SAT) でスケジューリング問題を解いてみる

📕 ステップ 3: アルゴリズムを実装する（1～3 ヶ月）

• 分枝限定法を 0/1 ナップサックで実装してみる
• 2-opt / 3-opt / Lin-Kernighan を TSP で実装
• 焼きなまし法、 タブー探索、 遺伝アルゴリズムを比較
• Coursera「Discrete Optimization」(Pascal Van Hentenryck) を受講

📙 ステップ 4: 産業応用に挑む（3～12 ヶ月）

• 大規模 VRP（配送ルート問題）を OSRM + LKH-3 で解く
• シフトスケジュールを CP-SAT で月次運用
• Column Generation（列生成法）と Benders 分解
• 論文購読: Mathematical Programming、 INFORMS Journal on Computing

📓 ステップ 5: 研究フロンティアへ（年単位）

• Learning to Branch / Learning to Cut（強化学習 × 最適化）
• 量子アニーリング（D-Wave）の使い分け
• ロバスト最適化、 確率計画法、 分布的ロバスト
• カンファレンス: INFORMS Annual Meeting、 NeurIPS（Optimization track）

✏️ 理解度チェック — 自分の理解を確認しよう

Q1. (易) 0-1 ナップサックの DP テーブルのサイズは?

品目数 \(N=10\)、 容量 \(W=100\) のとき、 DP テーブル V[i][w] のセル数は?

Q2. (普通) 焼きなまし法で温度を一定にしたら?

冷却スケジュールを使わず、 \(T = 100\) のまま 10000 ステップ動かすと何が起きる?

Q3. (普通) LP 緩和値が整数解と一致する場合は?

「LP 緩和の最適解が偶然すべて整数値になる」ことが理論的に保証される問題はどれ?

Q4. (難) Christofides 法の近似比 3/2 はなぜ成り立つ?

距離が三角不等式を満たす TSP に対し、 Christofides (1976) のアルゴリズム（MST + 最小完全マッチング + Euler 回路）はなぜ最悪 3/2 OPT 以内に収まる?

Q5. (難) CP と MIP どちらを選ぶ?

「100 人の看護師の月間シフト、 各種規則 50 件、 個人希望を最大限尊重」をどちらで解く?

🗺 実データで体感する組合せ最適化 — SSDSE-B-2026 を題材に

組合せ最適化は「教科書のおもちゃ問題」ではなく、 公的統計データを使って身近な行政課題に落とし込める。 ここでは SSDSE-B-2026（独立行政法人統計センター、 47 都道府県 × 約 100 指標）から、 組合せ最適化の典型 5 問題を実データで考える。 数値はそれぞれ「目的関数」「制約」「決定変数」の 3 要素に分解できる、 という骨格を意識すると、 後で自分の地域課題にも適用しやすい。

📊 図 1: 都道府県人口分布（決定変数の規模感）

組合せ最適化問題の「決定変数」は、 多くの場合「47 都道府県のどれを選ぶか」「どの市町村にどの病院を配置するか」といった離散的な選択に対応する。 まず母集団の規模感を可視化する。

図 1: SSDSE-B-2026 の都道府県人口分布（東京・神奈川・大阪が右の裾、 鳥取・島根が左端）。 「47 都市から K 個を選ぶ」問題の選択肢空間は \(\binom{47}{K}\) 通り（K=10 なら約 1.6 億通り）。

📊 図 2: 1 人当たり指標の散布図（目的関数と制約の関係）

「人口」と「指標 X」の散布図を見ると、 多くの行政指標が人口とほぼ比例することが分かる。 これは「人口比例で何かを配分する」最適化問題が成り立つ根拠であり、 単純な比例配分では拾えない「外れ値県」の存在が、 厳密な組合せ最適化が必要になる動機になる。

図 2: SSDSE-B-2026 の二指標散布。 線形傾向に乗らない外れ値（例: 東京は人口比で予想される値より医療資源密度が高い）が、 「LP 緩和では拾えない解」の存在を示唆する。

📊 図 3: グループ別のばらつき（地域ブロック制約のモチベーション）

地域ブロック（北海道・東北・関東・中部・近畿・中国・四国・九州沖縄）ごとに指標を箱ひげで見ると、 ブロック内分散とブロック間分散が大きく異なる。 これは「各ブロックから最低 1 つは選ぶ」「ブロック間で均等配分する」という区間制約を組合せ最適化に入れる必要性を示している。

図 3: 地域ブロック別の指標分布。 ブロック間の中央値差は、 「公平性制約」を明示的に最適化問題に組み込む根拠。 制約なしの単純最大化は「東京近郊だけが採択される」結果になりがち。

📋 組合せ最適化の典型問題マップ（行政・社会実装事例つき）

「組合せ最適化」は 1 つの問題を指す名前ではなく、 離散選択を含む全ての最適化の総称である。 以下は教科書・実務で頻出する 10 問題と、 それぞれの SSDSE 由来の身近な応用例。 自分の課題がどの「型」に当てはまるかが分かれば、 適切なソルバ（MIP / CP-SAT / メタヒューリスティクス / 専用アルゴリズム）に橋渡しできる。

💡 上の表で「多項式」と書かれた問題（割当、 マッチング、 流れ系）は、 47 都道府県規模でも 1 秒以内に厳密最適解が出る。 一方「NP-hard」と書かれた問題は、 47 規模なら厳密最適も可能だが、 1000 規模を超えるとヒューリスティクスが必須になる。 まずは自分の問題が表のどの行に当てはまるかを特定するのが第一歩。

🔗 隣接手法への橋渡し

「組合せ最適化」は離散の選択肢から最適配列を探す問題で、 上流の問題定式化 (整数計画) と下流の近似アルゴリズム比較を欠くと、 厳密解にこだわって NP 困難で詰む。

• 上流: 組合せ最適化 の入力となる47 都道府県から k 拠点を選ぶ施設配置問題 を整える前処理 (データクレンジング、 欠損値処理)
• 並列: 類似目的を持つ代替手法 (線形計画法、 動的計画法) と比較・併用
• 下流: 出力結果の評価・解釈 (最適化、 ヒューリスティック)

上流で目的関数と制約を整数計画形式に整え、 並列のヒューリスティック (焼きなまし・遺伝的アルゴリズム) と厳密解法 (分枝限定) を比較し、 下流で実行時間と解品質を評価すれば、 シフト表・配送計画など実務スケールの組合せ問題に対応できる。

🌳 手法選択フロー

「組合せ最適化」を実際に使うとき、 何をどう選ぶかを順に判断する。 上から順に答えていくと、 使うべき手法と評価の仕方が決まる。

1. 全部数え上げられる規模か
   $_{47}C_5 = 1{,}533{,}939$ 通りなら総当たりで最良解が出せる。 $_{47}C_{10}$ は約 52 億通りで現実的でない。 まず候補数を計算してから解法を選ぶ。
2. 最良解が要るか、 良い解で足りるか
   厳密解が要るなら整数計画（PuLP・OR-Tools）で解く。 時間内に良い解が出ればよいなら、 貪欲法や局所探索、 遺伝的アルゴリズムで足りる。
3. 制約はどう書けるか
   「予算内」「各地域から最低 1 つ」のような制約は線形式で書けることが多く、 その場合は整数計画が使える。 線形で書けない制約があるなら、 メタヒューリスティクスに寄せる。
4. 解の安定性を確かめたか
   入力をわずかに変えても解が大きく変わるなら、 その解を根拠に意思決定するのは危うい。 感度分析を行い、 上位いくつかの解を並べて示す。

組合せ最適化はまず「候補が何通りあるか」を数えるところから。 数え上げで済む規模に問題を切り直せるなら、 それが最も確実で説明もしやすい。