🗺️ このノートは 第3章「整数計画と組合せ最適化」のハブ です。
第3章 ── 整数計画と組合せ最適化
変数が整数になった瞬間、最適化は質的に難しくなる。微分が使えず、選択肢が指数的に増える。この章では、整数計画を LP 緩和で近似し、分枝限定と 切除平面で厳密に攻める枠組みを学ぶ。代表的な組合せ問題と、何が本質的に難しいか（NP 困難）の地図も描く。
トピック一覧
- 整数計画とは・LP緩和 — 整数制約・緩和・整数ギャップ（標準）
- 分枝限定法 — 分枝・限定（バウンド）・枝刈り（標準）
- 切除平面法 — Gomory カット・有効不等式（発展）
- 代表的な組合せ問題 — ナップサック・集合被覆・割当（標準）
- 計算複雑性とNP困難の地図 — P/NP・近似・難しさの地図（標準）
- 動的計画法とベルマンの原理 — 最適性原理・状態/段階・厳密解法の第3の柱（標準）
この章の位置づけ
- LP 緩和（整数計画とは・LP緩和）が第2章 線形計画 章目次 と離散最適化の橋
- 分枝限定（分枝限定法）・切除平面（切除平面法）・動的計画法（動的計画法とベルマンの原理）が厳密解法の3つの柱、現代の MILP ソルバーは分枝とカットを融合
- 厳密が困難なときはメタヒューリスティクス（メタヒューリスティクス 章目次）へ繋ぐ
- 適用（スケジューリング・配送）は operations へ wikilink（スケジューリング・配送のモデル化）
関連章
- 前章：線形計画 章目次 次章：非線形最適化 章目次
- 全体ハブ：数理最適化・OR 全体目次