この記事について

ここ2ヶ月ほど、線形計画（LP）から整数計画（MIP）までの理論を、1テーマ1記事のペースで書いてきました。「どれがどれだっけ．．．。」という感じでもあるので、この記事で全体を整理します笑

書き始めた動機はシンプルで、最近興味を持ってくれてる人も増えてきて、その中で都度説明するにも自分自身でもなかなか整理がついてない という状態を解消したかったからです。ソルバーに問題を投げると答えが返ってくるのはありがたいのですが、

なぜこの問題はすぐ解けて、あの問題は一晩回しても終わらないのか
Method とか MIPGap とか、結局どれを触ればいいのか
shadow price って何を意味しているのか

みたいなところが、使っているだけだとどうしても曖昧なままなんですよね。。。

なので「ソルバーの中身を、手で追える粒度まで分解する」という方針で書いてきました。この記事は各テーマの概要とリンクをまとめた目次的な位置づけなので、気になるところから拾い読みしてもらえると幸いです。

全体の地図

18記事は大きく4つのブロックに分かれます。

① 線形計画と単体法（4本）        LPの構造とアルゴリズム
        ↓  「最適値の上界はどう求める？」
② 双対問題（4本）                LPのもう一つの顔・感度分析
        ↓  「整数条件を入れたい」
③ 整数計画のモデリング（6本）    離散的な世界を線形式で書く
        ↓  「で、どうやって解くの？」
④ 整数計画の解法（4本）          分枝限定法・切除平面法・ソルバー

①②が「連続の世界（LP）」、③④が「離散の世界（MIP）」です。①→④の順に読むと一本道でつながるように書いたつもりですが、③のモデリングだけは独立して読めるので、実務で定式化に困っている方はそこから入るのもアリかと思います。

① 線形計画と単体法 ─ LPの構造とアルゴリズム

まずは連続の世界から。「LPの実行可能領域は凸多面体で、最適解はその頂点にある」 という幾何的な事実を出発点に、頂点を辿るアルゴリズムである単体法を、手計算 → 行列形式 → 実用上の課題、という順で掘り下げていきます。

単体法は「辞書形式」という表現を使うと四則演算だけで手で回せるので、実際に紙とペンで追ってみるとソルバーの気持ちがかなり分かるようになります。最後は内点法との比較まで行って、「Gurobiの Method パラメータ、結局どれ？」という疑問に答えます。

線形計画問題とは？標準形・実行可能領域・凸多面体の頂点 ─ 標準形・実行可能領域・凸多面体の頂点。頂点全列挙が計算量的に無理ゲーなことを確認します（★☆☆）
単体法を手で解いてみた ─ 辞書形式と隣接頂点の移動 ─ 辞書形式・基底変数・最小比テスト。3ステップの手計算で頂点を渡り歩きます（★★☆）
単体法の数学的原理 ─ 基底解・シンプレックス乗数・被約費用 ─ 基底分割 $A=(B,N)$・シンプレックス乗数・被約費用。非有界の判定とBlandの規則まで（★★★）
2段階単体法と内点法 ─ 初期解の見つけ方とLPソルバーの選び方 ─ 初期実行可能解を補助問題で作る話と、境界を歩く単体法 vs 内部を突っ切る内点法の使い分け（★★☆）

② 双対問題 ─ 最適値の上界と、その実用的なご利益

「最適解が分からなくても、最適値の上界だけなら作れないか？」という素朴な問いから出発すると、双対問題が自然に出てきます。天下り的に「双対とはこう定義される」と言われるより、この順番の方がずっと腹落ちするかと思います。

同じ双対問題がラグランジュ緩和からも導けること、弱双対・強双対・相補性条件という3つの定理、そして感度分析・潜在価格（Shadow Price）・双対単体法という実用面まで扱います。「双対変数って結局なに？」に対する答えが「資源の潜在価格」 だと分かると、感度分析が一気に実務の道具になります。

線形計画の双対問題とは？最適値の上界を算出 ─ 制約の非負1次結合で上界を作る発想から双対問題を導出。主問題と双対問題の対応表つき（★☆☆）
ラグランジュ緩和から双対問題を導く ─ 緩和問題という統一的な視点。制約をペナルティとして目的関数に押し込むと、また同じ双対問題に行き着きます（★★☆）
弱双対定理・強双対定理・相補性条件 ─ 線形計画における3つの重要定理 ─ 3定理の証明のスケッチと、実行可能／非有界／実行不能の組み合わせ表（★★★）
双対問題が役立つ実例 ─ 感度分析・潜在価格・双対単体法 ─ 生産の例で「どの資源を増やすのが一番お得か」を双対変数で評価。列生成法と双対単体法のさわりも（★★☆）

③ 整数計画のモデリング ─ 離散的な世界を線形式で書く

ここから離散の世界です。整数計画は「変数に整数条件を付けただけのLP」というより、離散的な状態をモデル化するための記法だと捉えると見通しが良くなります。

「高々k個」「iまたはj」「iならばj」といった論理制約、固定費用、Big-Mによる離接制約、非線形関数の区分線形近似、2値変数の積の線形化（QUBO ↔ MIP）…と、実務の定式化でそのまま使える道具を並べています。後半は「LP緩和を解くだけで勝手に整数解が出てくる」という完全単模行列（TU行列）の話と、TSPの部分巡回路除去制約まで取り上げています。

なお4本目のTU行列の記事で「奇閉路があるとTUでなくなる」と書いたところ、ちょっとわかりにくいかなという感じもしたので、$K_3$ だけを取り出して行列式を計算する短い記事を番外編として挟んでいます。

④ 整数計画の解法 ─ ソルバーの中身を覗く

最後は「で、ソルバーはこれをどう解いているのか」です。基本戦略は①②と地続きで、LP緩和で下界を作り、暫定解で上界を作り、両側から最適値を挟み込むというもの。

その挟み込みを実行する手段が分枝限定法（問題を分割する）と切除平面法（実行可能領域を削る）で、この2つを組み合わせたものが実際のソルバーが使っている分枝カット法です。最終記事では Gurobi のログの読み方、収束曲線の可視化、そして「計算が終わらないときどうするか」という原因別の対処法をまとめています。

整数計画問題の解き方 ― LP緩和と上界・下界の考え方 ─ なぜ整数条件が入ると難しいのか。LP緩和・暫定値・下界値という共通言語を整理します（★☆☆）
分枝限定法を手で実践 ─ ナップサック問題で探索木を体感 ─ 分枝操作と限定操作。探索木を1ノードずつ育てながら、枝刈りの瞬間を追いかけます（★★☆）
切除平面法とGomoryカット ─ LP実行可能領域を整数解まで削り込む ─ 妥当不等式とGomoryカットの導出。整数解の凸包という考え方（★★★）
分枝カット法と整数計画ソルバーの仕組み ─ なぜGurobiは速いのか ─ 分枝限定法＋切除平面法の統合、Gurobiのログの読み方、MIPギャップでの早期終了（★★☆）

難易度と読む順のおすすめ

全18記事を難易度つきで一覧にすると以下のようになります。

ブロック	記事	キーワード	難易度
①	線形計画問題とは？	標準形・実行可能領域・頂点	★☆☆
①	単体法を手で解いてみた	辞書形式・隣接頂点移動	★★☆
①	単体法の数学的原理	基底解・被約費用・Blandの規則	★★★
①	2段階単体法と内点法	補助問題・内点法・ソルバー選択	★★☆
②	双対問題とは？	上界・1次結合・主問題と双対問題	★☆☆
②	ラグランジュ緩和から双対問題を導く	緩和問題・ラグランジュ乗数	★★☆
②	双対の3定理	弱双対・強双対・相補性条件	★★★
②	双対問題が役立つ実例	感度分析・潜在価格・双対単体法	★★☆
③	整数計画のモデリング基本	2値変数・論理制約・固定費用	★☆☆
③	Big-M法と離接制約	Big-M・スケジューリング・詰込み	★★☆
③	非線形・2次の線形化	区分線形近似・2値積・QUBO	★★★
③	完全単模行列	TU行列・最短路・割当	★★★
③	（番外編）K₃とTU性	行列式・奇閉路	★★☆
③	グラフ問題の定式化	最小全域木・TSP・MTZ	★★★
④	LP緩和と上界・下界	LP緩和・暫定値・下界値	★☆☆
④	分枝限定法	分枝操作・限定操作・探索木	★★☆
④	切除平面法とGomoryカット	妥当不等式・Gomoryカット	★★★
④	分枝カット法とソルバー実践	MIPギャップ・実務Tips	★★☆

目的別のおすすめルートはこんな感じです。

こういう人	おすすめの読み方
一通り理解したい	①→②→③→④を順番に。★★★の3本は最初は飛ばしてもOK
定式化で困っている	③だけ読む（①②を知らなくても大丈夫です）
計算が終わらなくて困っている	④の1本目 → 4本目。特に「原因と対処」のセクション
ソルバーの中身が知りたい	①の2本目（単体法の手計算）→ ④の2本目（分枝限定法の手計算）
感度分析を使いたい	②の4本目だけでも読めます

まとめ

18記事を読んでみると、線形計画から整数計画までは想像以上に一本の線でつながっているなと感じるかと思います。

LPの最適解が頂点にあるから 単体法 が生まれ
上界を求めたいという動機から 双対問題 が生まれ
双対から 感度分析・双対単体法・列生成法 が生まれ
LP緩和が下界を与えるから 分枝限定法 が回り
整数解の凸包に近づけたいから 切除平面法 が生まれ
その2つを合わせたものが 今のソルバー

という感じで、それぞれ独立した技術のように見えて、実は前の話が次の話の部品になっています。「Gurobiが速い理由」を理解するには結局①まで遡る必要がある、というのが個人的に一番大切なことかと思います。

もちろん自分の理解整理を兼ねて書いているので、間違っているところもあるかと思います。お気づきの点があれば優しくご指摘いただけると嬉しいです笑

数理最適化まわりでは他にも以下のシリーズを書いているので、あわせて読んでもらえると幸いです。

【配送最適化入門】配送最適化とは？⓪ ─ TSP・VRPをヒューリスティクスで解くシリーズ（全9本）
【多目的最適化入門】多目的最適化とは？① ─ NSGA-II・MOEA/Dなど多目的最適化シリーズ（全4本）
【最適化ソルバー入門】どのソルバーを選ぶべきか？主要ツール比較まとめ ─ PuLP・Gurobi・HiGHSなどの比較