0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@doiken_(土井 健)
in

【まとめ】線形計画から整数計画まで18記事でおさらい

0
Posted at

この記事について

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

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

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

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

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

全体の地図

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

全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が速い理由」を理解するには結局①まで遡る必要がある、というのが個人的に一番大切なことかと思います。

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

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

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?