Model Building in Mathematical Programming: 9.3 〜 9.4

9.3 Special ordered sets of variables

ここでは、special ordered sets type 1 (SOS1) と special oredered sets type 2 (SOS2) という特殊な変数の組について解説している。SOS

SOS2 は、まさに区分線形近似ででてきたもの。つまり、MIPの範囲まで広げれば、非凸な関数も区分線形近似できる。

SOSの使用例としては、施設配置問題（候補のうち1つだけが値を持つ）、Capacity Extension (容量拡張？ある量を超えると追加のコストがかかるような場合に、追加コストの状況を選択する）、非線形関数（区分線形近似）などがある。ちなみに区分線形近似は、非連続な関数に対しても使える。

LPに追加の条件が課せられた場合に、MIPとして定式化できることがある。ここでは、いくつかの例を紹介している

Disjunctive constraints
- いわゆる or 条件。前述の通り、 indicator variables によって、複雑な論理条件を記述できる
Non-convex regions
- or を表現できるので、下図のような非凸な領域も表現できる。
  非凸な例
Limitting the number of variables in a solution
- 以下のような制約を課せば、正となる変数の個数に制限をつけられる
  $\displaystyle \delta _ 1 + \delta _ 2 + \dots + \delta _ n \leq k.$
Sequentially dependent decisions
- 前期の状態によって今期の判断に制限がかかるような条件は、前期の状態を表す変数と今期の判断を表す変数の組合せで表現できる
Economies of scale
- コストが上にサチるような状況では、（コストを下げたいという意味で）目的関数が非凸だが、MIPであれば区分線形近似できる
Discrete capacity extensions
- 容量が段階的に増えるような条件も、indicator variable をつかって表現できる
Maximax objectives
- minimax と違い、 maximax はLPでは表現できないが、MIPであればor条件を使って表現できる。