OR-ToolsのAddBoolOrの使い方(シフトスケジュール問題の制約条件の実装)

# 内容
- AddBoolOrメソッドによる制約条件の実装の例を紹介しています。OR-Toolsのサンプルコードとして紹介されている、[シフトスケジュール問題を解くプログラム](https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)を題材としています。
- 備忘のため、Googleの数理最適化ツール[OR-Tools](https://developers.google.com/optimization)の、cp_modelモジュールのCpModelクラスの[AddBoolOrメソッド](https://developers.google.com/optimization/reference/python/sat/python/cp_model#addboolor)の使い方を、簡単にまとめてみました。
- OR-Toolsのエキスパートの方には少々退屈な内容かもしれません。初心者の方であれば、参考になるかもしれません。


# 注意事項
- 当方、OR-Toolsの初心者です。おおむね理解したつもりで書いていますが、もしかしたら間違っているところがあるかもしれません。ご容赦下さい。
- 制約条件の実装の仕方は、シフトスケジュールの表現の仕方や目的関数の設定の仕方によって、大きく変わってきます。ここで記載されたソースコードを流用する場合は、適宜変更した上で、ご利用下さい。　　


# シフトスケジュール問題
- OR-Toolsのサンプルコードとして紹介されている、[シフトスケジュール問題を解くプログラム](https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)を題材とする。
- シフトスケジュール問題では、以下のような問題を解いている。
    - 8人の従業員の、3週間分の、シフトスケジュールを作る。1日の勤務は、午前／午後／夜間の3交代勤務を想定。
    - シフトスケジュールには、以下の制約条件を反映する。
        1. 1日1シフトのみ(午前／午後／夜間のいずれか)の勤務とする(H)。
        1. あらかじめ指定した従業員のシフトは固定する(H)。
        1. なるべく、従業員のシフトの希望を反映する(S)。
        1. 連続する休暇は、1-2日間とする(H)。
        1. 連続する夜間の勤務は、1-4日間とする(H)。なるべく、2-3日間とする(S)。
        1. 一週間の休暇は、1-3日間とする(H)。なるべく、2日間とする(S)。
        1. 一週間の夜間勤務は、0-4日間とする(H)。なるべく、1-4日間とする(S)。
        1. なるべく、午後->翌日の夜間の勤務はしない(S)。
        1. 夜間->翌日の午前の勤務はしない(H)。
        1. なるべく、曜日／シフト毎に必要となる従業員数を確保する(S)。
    - (H)の項目は、必ず満たさなければならない条件(ハード制約条件)を示している。(S)の項目は、必ずしも満たさなくても良いが満たした方が良い条件(ソフト制約条件)を示している。


# AddBoolOrメソッドによる制約条件の実装の例
- 上記の制約条件の一部は、AddBoorOrメソッドを使って実装されている。以降では、いくつか簡単なものを抜粋して、制約条件の実装の例を示す。いずれも必要なモジュールのインポートやクラスオブジェクトの生成等 制約条件の実装と直接関係しない事前準備の手順は、省いて記載するようにしている。


## 　制約条件「9. 夜間->翌日の午前の勤務はしない(H)。」の実装の方法
- 最適化したい変数(ブール変数)を定義する。
- 変数Work[e, s, d]で、「従業員eの、d日目の、シフトs(休暇(=0)／午前(=1)／午後(=2)／夜間(=3) のいずれか)」の勤務の有無を表す。work[e, s, d]=True(=1)なら、従業員eは、d日目の、シフトsの勤務に従事することとなる。

```python
work[e, s, d] = model.NewBoolVar('work%i_%i_%i' % (e, s, d))
```
([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

- 禁止したいシフトの組合せを反転したリストを作る。
- ここでは、「従業員eの、d日目の、夜間の勤務」と「翌日の、午前の勤務」が続くのを禁止するため、変数Work[e, previous_shift(=夜間(=3)), d]とWork[e, next_shift(=午前(=1)), d + 1]の組合わせを反転したリストを作るようにしている。

```python
transition = [work[e, previous_shift, d].Not(), work[e, next_shift, d + 1].Not()]
```
([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

- 制約条件を加える。

```python
model.AddBoolOr(transition)
```
([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)


## 　制約条件「8. なるべく、午後->翌日の夜間の勤務はしない(S)。」の実装の方法
- 最適化したい変数(ブール変数)を定義する。上記の、制約条件「9. 夜間->翌日の午前の勤務はしない(H)。」の実装と同じ。

```python
work[e, s, d] = model.NewBoolVar('work%i_%i_%i' % (e, s, d))
```
([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

- なるべく禁止したいシフトの組合せを反転したリストを作る。上記の、制約条件「9. 夜間->翌日の午前の勤務はしない(H)。」の実装と同じ。
- ここでは、「従業員eの、d日目の、午後の勤務」と「翌日の、夜間の勤務」が続くのを禁止するため、変数Work[e, previous_shift(=午後(=2)), d]とWork[e, next_shift(=夜間(=3)), d + 1]の組合わせを反転したリストを作るようにしている。

```python
transition = [work[e, previous_shift, d].Not(), work[e, next_shift, d + 1].Not()]
```
([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

- 制約条件「8. なるべく、午後->翌日の夜間の勤務はしない(S)。」を加えるための新たな変数(ブール変数)を定義する。
- 変数trans_varで、「従業員eの、d日目の、シフトスケジュールの、制約条件の逸脱」の有無を表す。trans_var=True(=1)なら、従業員eは、d日目の、シフトスケジュールが制約条件を満たしていないことになる。

```python
trans_var = model.NewBoolVar('transition (employee=%i, day=%i)' % (e, d))
```
([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

- 制約条件「8. なるべく、午後->翌日の夜間の勤務はしない(S)。」を逸脱した場合に、目的関数にペナルティを加えられるようにするため、transitionに、trans_varを加える。

```python
transition.append(trans_var)
```
([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

- 制約条件を加える。上記の、制約条件「9. 夜間->翌日の午前の勤務はしない(H)。」の実装と同じ。ただし、transitionに、trans_varが加えられているため、動作が若干異なる。
- transition = [work[e, previous_shift, d].Not(), work[e, next_shift, d + 1].Not(), trans_var]の組合せを指定しているため、[work[e, previous_shift, d]=True(=1), work[e, next_shift, d + 1]=True(=1), trans_var=False(=0)]の組合せが禁止される。この場合、なるべく禁止したいシフトの組合せ[work[e, previous_shift, d]=True(=1)、work[e, next_shift, d + 1]=True(=1)]は、禁止されないことになる。その代わり、該当の組合せになった場合は、必ずtrans_var=True(=1)となるようになる。他の組合わせの場合は、trans_varの値だけが異なる組合せが2つ存在することになるため、単純に、trans_var

```python
model.AddBoolOr(transition)
```
([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

- 目的関数に、trans_varを加える。併せて、制約条件を逸脱した場合のペナルティcost(>0の整数)を加える。
- 目的関数は、以下の通り、work[e, s, d]やtrans_var等の変数に、ペナルティを加味するための係数を乗じて、積算した値となっている(変数obj_bool_varsの中にwork[e, s, d]やtrans_varが含まれている。また、変数obj_bool_coeffsの中に、両者に対応する係数が含まれている。)。この目的関数を最小化することで、可能な限り、制約条件を満たすシフトスケジュールを作れるようにしている。

```python
obj_bool_vars.append(trans_var)
obj_bool_coeffs.append(cost)
```
([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)


## 　サンプルコード
- 上記の制約条件「9. 夜間->翌日の午前の勤務はしない(H)。」と制約条件「8. なるべく、午後->翌日の夜間の勤務はしない(S)。」を実装した箇所のサンプルコードの抜粋。

    - パラメータを設定している箇所

```python
    # Penalized transitions:
    #     (previous_shift, next_shift, penalty (0 means forbidden))
    penalized_transitions = [
        # Afternoon to night has a penalty of 4.
        (2, 3, 4),
        # Night to morning is forbidden.
        (3, 1, 0),
    ]
```

   - 制約条件を実装している箇所
 
```python
    # Penalized transitions
    for previous_shift, next_shift, cost in penalized_transitions:
        for e in range(num_employees):
            for d in range(num_days - 1):
                transition = [
                    work[e, previous_shift, d].Not(), work[e, next_shift,
                                                           d + 1].Not()
                ]
                if cost == 0:
                    model.AddBoolOr(transition)
                else:
                    trans_var = model.NewBoolVar(
                        'transition (employee=%i, day=%i)' % (e, d))
                    transition.append(trans_var)
                    model.AddBoolOr(transition)
                    obj_bool_vars.append(trans_var)
                    obj_bool_coeffs.append(cost)
```
([シフトスケジュール問題を解くプログラムのソースコード]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)より引用)