Model Building in Mathematical Programming: 9.5 Special kinds of integer programming

Optimization Night で H. Paul Williams, Model Building in Mathematical Programming, 5th Edition, Wiley, 2013. の輪読会をしているので、そのメモです。

Chapter 9 Building Integer programming model I

9.5 Special kinds of integer programming models

ここでは、MIPとしてよく知られている問題と定式化方法を紹介している

集合被覆問題: Set covering problems
- 部分集合の組が与えらえられたときに、最小の数ですべての要素をカバーしなさい、という問題
- 各部分集合を使うか否かを表す変数 $\delta _ i $ を使って、各要素がいずれかに含まれていなさい、という制約を課す
- 応用例には航空スタッフのスケジューリングなど
- 基本的にときやすい問題で、難易度はその構造ではなく問題サイズに依存する
集合パッキング問題: Set packing problems
- 部分集合の組が与えられたときに、要素の重複を許さず、どれだけ多くの部分集合を詰め込めるか、という問題
- 各部分集合を使うか否かを表す変数 $\delta _ i $ を使って、各要素の重複を許さない、という制約を課す
- 線形緩和問題の双対がちょうど集合被覆の緩和問題になる
- 応用例にはマッチング問題など
集合分割問題
- 部分集合の組が与えられたときに、要素の重複を許さず、すべての部分集合をカバーする、という問題
- 応用例としては、一票の重みの差を最小にして選挙区の設定など
- slack変数を使って表現した集合パッキングと同じ
ナップサック問題
- ナップサックにどれだけ多く荷物を積み込めるか
- 応用例にはプロジェクト選択問題などもあるが、別の問題の部分問題（列生成法の子問題?）として現れることが多い
巡回セールスマン問題
- すべての都市を1回ずつ巡回するときに最短経路を求める問題
- 都市 $i$ から都市 $j$ へ（直接）進むかどうかを表す変数 $\delta _ {ij} $ を使って表現する
- 部分巡回路の除去が重要
  - シンプルなのは、一度部分巡回路制約なしで解いてしまって、最適解に部分巡回路が含まれていたら、その部分巡回路を明示的に除去する制約を追加する（これを繰り返す）方法。他にもいろいろある
配送計画問題
- 巡回セールスマン問題の拡張。容量制約のある車両が複数台で顧客を回る
- 定式化できるが、現実的なサイズの問題は難しい。列生成法を使う方法もある
2次割当問題
- 2つの集合 $S$ と $T$ が与えられたときに、 $S$ の要素と $T$ の要素を１対１対応させながらコストを最小化する問題で、コストは組合せで決まる（$i$ と$j$ が対応して、かつ $k$ と $l$ が対応した場合にコスト $C_{ijkl}$ かかる）ような問題
- 例えば2点間の距離を最小化するような問題は、2次割当問題として定式化できるし、巡回セールスマン問題もこの形で定式化できる
- 目的関数が2次なので、一次式に変換してから解く必要がある