CPLEXでSOS2を指定する

CPLEXで特殊順序集合 (SOS)のType2を使って制約を作成してみます。docplexを使います。

SOS タイプ 2 は、最大で 2 つの変数がゼロ以外の変数の集合です。 2 つの変数がゼロ以外の場合、それらは集合内で隣接していなければなりません。

# 問題
300人の子供が動物園にいくバスを手配します。
30人乗りのバスは400ポンド
40人乗りのバスは500ポンド
50人乗りのバスは550ポンド

50人乗りのバスは1台手配することが決まっています。

のそれぞれのバスを何台手配するのが一番安いでしょうか。

# SOSなしでの求解

まずはSOSなしで求解してみます。
```python:
from docplex.mp.model import Model

mdl = Model(name='buses')
mdl.context.solver.log_output = True
nbbus30 = mdl.integer_var(name='nbBus30')
nbbus40 = mdl.integer_var(name='nbBus40')
nbbus50 = mdl.integer_var(name='nbBus50')

cost = mdl.continuous_var(name='cost')


mdl.add_constraint(nbbus50*50+nbbus40*40 + nbbus30*30 >= 300, 'kids')

mdl.add_constraint(cost==nbbus40*500 + nbbus30*400+nbbus50*550)
#50人乗りは1台固定
mdl.add_constraint(nbbus50==1)

mdl.minimize(cost)
                
mdl.solve()

for v in mdl.iter_integer_vars():
    print(v," = ",v.solution_value)

print("The minimum cost is ",cost.solution_value);    
```

結果は以下のようになりました。
50人乗りのバスは1台手配することが決まっていた（mdl.add_constraint(nbbus50==1)
）ので、残りの250人を、30人乗り3台と40人乗り4台で分けました。

nbBus30  =  3.0
nbBus40  =  4.0
nbBus50  =  1.0
The minimum cost is  3750.0

# SOS2を使った解

続いて、30人乗りのバス、40人乗りのバス、50人乗りのバスの「順序」の中で隣り合う最大2台までが利用できるという制約を以下のようにSOS2をつかって定義します。
mdl.add_sos2([nbbus30,nbbus40,nbbus50])

先ほどの解のように30人乗り、40人乗り、50人乗りの全てのバスを利用することはできません。いずれか2台まで（1台だけは可能）です。
かつ「30人乗りと50人乗り」という隣り合っていないバスを選ぶことはできないとします（ここが特殊順序集合の意味です）。

```python:
print("and then with sos2   nbbus30,nbbus40,nbbus50")


#隣り合う高々2台までの種類のバスを選択する
mdl.add_sos2([nbbus30,nbbus40,nbbus50])

mdl.minimize(cost)
                
mdl.solve( )

for v in mdl.iter_integer_vars():
    print(v," = ",v.solution_value)

print("The minimum cost is ",cost.solution_value);
```

結果は以下のようになりました。
50人乗りのバスは1台手配することが決まっていた（mdl.add_constraint(nbbus50==1)
）ことに加えて、隣り合う2つまでしか選べませんので、残りは40人乗りだけから選ぶ必要があり、7台で分けました。

nbBus30  =  0
nbBus40  =  7.0
nbBus50  =  1.0
The minimum cost is  4050.0

# SOS2を使った求解。制約を変更
50人乗りのバスは1台手配することが決まっていると、30人乗りのバスは絶対に選択されません。ですので今度は問題をかえて、「50人乗りのバスは1台手配する」という制約「mdl.add_constraint(nbbus50==1)」の代わりに、「30人乗りのバスは1台以上手配する」という制約「mdl.add_constraint(nbbus30>=1)」をいれます。


```python:
mdl = Model(name='buses')
mdl.context.solver.log_output = True
nbbus30 = mdl.integer_var(name='nbBus30')
nbbus40 = mdl.integer_var(name='nbBus40')
nbbus50 = mdl.integer_var(name='nbBus50')

cost = mdl.continuous_var(name='cost')


mdl.add_constraint(nbbus50*50+nbbus40*40 + nbbus30*30 >= 300, 'kids')

mdl.add_constraint(cost==nbbus40*500 + nbbus30*400+nbbus50*550)


#30人乗りを1台以上
mdl.add_constraint(nbbus30>=1)
#隣り合う高々2台までの種類のバスを選択する
mdl.add_sos2([nbbus30,nbbus40,nbbus50])

mdl.minimize(cost)
                
mdl.solve()

for v in mdl.iter_integer_vars():
    print(v," = ",v.solution_value)

print("The minimum cost is ",cost.solution_value);    
```

結果は以下のようになりました。
30人乗りのバスは1台以上手配することが決まっていた「mdl.add_constraint(nbbus30>=1)」
）ことに加えて、隣り合う2つまでしか選べませんので、50人乗りは選べません。残りは30人乗りと40人乗りの２つから選ぶ必要があり、それぞれ2台と6台で分けました。

nbBus30  =  2.0
nbBus40  =  6.0
nbBus50  =  0
The minimum cost is  3800.0

# 参考
#### zoodocplex/zoosos2.py at master · AlexFleischerParis/zoodocplex · GitHub 

https://github.com/AlexFleischerParis/zoodocplex/blob/master/zoosos2.py

#### 特殊順序集合 (SOS) とは - IBM Documentation 

https://www.ibm.com/docs/ja/icos/20.1.0?topic=sos-what-is-special-ordered-set


#### add_sos2  — DOcplex.MP: Mathematical Programming Modeling for Python V2.25 documentation 

https://ibmdecisionoptimization.github.io/docplex-doc/mp/docplex.mp.model.html?highlight=add_sos2#docplex.mp.model.Model.add_sos2