代表的な組合せ問題

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：整数計画とは・LP緩和　|　関連：計算複雑性とNP困難の地図・割当問題（ハンガリアン法）

要点（BLUF）

組合せ最適化の多くは、少数の 典型問題の定式化に帰着できる。
ナップサック・集合被覆・割当・TSP は「選ぶ／割り当てる／並べる」の代表例。
同じ離散でも難しさは別物：割当・最短路は 多項式時間、ナップサック・集合被覆・TSP は NP 困難（計算複雑性とNP困難の地図）。

概念 ── 典型問題のカタログ

実務の離散最適化は、見た目が違っても定式化すると典型問題に落ちることが多い。代表例を 0/1 変数で書けるようにしておくと、モデリング（モデリングの作法）の引き出しになる。

問題	やること	難しさ
ナップサック	容量内で価値最大の品目選択	NP 困難（弱・擬多項式 DP 可）
集合被覆	全要素を覆う最小コストの集合選択	NP 困難
割当	作業者と仕事の1対1対応で総コスト最小	多項式時間（割当問題（ハンガリアン法））
最短路	2点間の最小コスト経路	多項式時間（最短経路問題（ダイクストラ・ベルマンフォード））
巡回セールスマン（TSP）	全都市を1度ずつ回る最短巡回	NP 困難

定式化のテンプレート

0/1 ナップサック（価値 $v_i$ 、重さ $w_i$ 、容量 $W$ ）：

\max \sum_i v_i x_i \quad \text{s.t.}\quad \sum_i w_i x_i \le W,\ x_i \in \{0,1\}

集合被覆（要素 $U$ 、集合 $S_j$ 、コスト $c_j$ ）：

\min \sum_j c_j x_j \quad \text{s.t.}\quad \sum_{j: e \in S_j} x_j \ge 1\ (\forall e \in U),\ x_j \in \{0,1\}

割当（コスト $c_{ij}$ 、 $n$ 人 $n$ 仕事）：

\min \sum_{i,j} c_{ij} x_{ij} \quad \text{s.t.}\quad \sum_j x_{ij}=1\ (\forall i),\ \sum_i x_{ij}=1\ (\forall j),\ x_{ij}\in\{0,1\}

割当の制約行列は 全ユニモジュラなので、LP 緩和の頂点が自動で 0/1 になる ── だから整数性を課さなくても整数解が出る（整数計画とは・LP緩和のギャップ0）。これが「割当が易しい」理由。

Pythonで割当問題を解く

割当を 0/1 整数計画として PuLP で解く。コスト行列の最小総コストと、誰がどの仕事に就くかを求める。

import pulp
import numpy as np

cost = np.array([[9, 2, 7],
                 [6, 4, 3],
                 [5, 8, 1]])   # cost[i][j] = 作業者iが仕事jをやるコスト
n = 3

prob = pulp.LpProblem("assignment", pulp.LpMinimize)
a = {(i, j): pulp.LpVariable(f"a_{i}_{j}", cat="Binary")
     for i in range(n) for j in range(n)}
prob += pulp.lpSum(cost[i, j] * a[i, j] for i in range(n) for j in range(n))
for i in range(n):                                   # 各作業者は1つの仕事
    prob += pulp.lpSum(a[i, j] for j in range(n)) == 1
for j in range(n):                                   # 各仕事は1人に割当
    prob += pulp.lpSum(a[i, j] for i in range(n)) == 1
prob.solve(pulp.PULP_CBC_CMD(msg=0))

pairs = [(i, j) for i in range(n) for j in range(n) if a[i, j].value() > 0.5]
print(f"最小総コスト = {pulp.value(prob.objective):.0f}")
print(f"割当 (作業者->仕事) = {pairs}")

実行結果：

最小総コスト = 9
割当 (作業者->仕事) = [(0, 1), (1, 0), (2, 2)]

作業者0→仕事1（コスト2）、作業者1→仕事0（コスト6）、作業者2→仕事2（コスト1）で総コスト 9。各行・各列がちょうど1つ選ばれる（1対1対応）。この問題は専用の ハンガリアン法（割当問題（ハンガリアン法））で $O(n^3)$ で解け、整数計画にせずとも厳密に解ける。

易しい離散と難しい離散

同じ「0/1 変数」でも、構造で難易度が分かれる：

易しい（多項式時間）：割当・最短路・最大流・最小費用流。制約行列の 全ユニモジュラ性や、貪欲・動的計画が効く構造を持つ（ネットワーク最適化章目次）。
難しい（NP 困難）：TSP・集合被覆・一般のナップサック・グラフ彩色。緩和ギャップが構造的に残り、分枝限定（分枝限定法）やメタヒューリスティクス（メタヒューリスティクス章目次）が要る。

数式の直観的意味

組合せ最適化の難しさは「制約行列の幾何」に宿る。割当・流れ問題は制約行列が全ユニモジュラで、LP 緩和の凸多面体の頂点が最初から整数 ── つまり連続問題が勝手に離散解を返す（整数計画とは・LP緩和）。一方 TSP やナップサックは整数多面体が複雑（面が指数的）で、LP 緩和と整数解の間にギャップが残る。だから典型問題を見たら「これは全ユニモジュラ系か、それとも本質的に難しい系か」をまず見極める ── それが解法（多項式アルゴリズムか、分枝＋カットか、ヒューリスティックか）の選択を決める。

⚠️ よくある誤解・落とし穴

「離散だから全部 NP 困難」ではない。割当・最短路は多項式時間。構造を見極める。
ナップサックは「弱 NP 困難」：擬多項式時間の動的計画法（容量に比例）で解ける。容量が小さければ実用的。
集合被覆の貪欲法は $\ln n$ 近似：厳密は難しいが、良い近似アルゴリズムが知られる（計算複雑性とNP困難の地図）。
定式化が同じでも、対称性（同等な解が大量）があると分枝限定が遅くなる。対称性除去が要る。