OR-Toolsのシフトスケジュール問題のサンプルコードを解読してみた！！(その1：サンプルコードの概要)

# 内容
- Googleの数理最適化ツール[OR-Tools](https://developers.google.com/optimization)のサンプルコードとして公開されている、[シフトスケジュール問題を解くプログラム](https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)に、解説がついていなかったため、勉強がてら、解読してみました。
- その1では、「[シフトスケジュール問題を解くプログラム](https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)の概要」をまとめています。目次は、以下の通りです。
    - シフトスケジュール問題の概要
    - シフトの表現
    - 目的関数
    - 制約条件
        - ハード制約条件
        - ソフト制約条件
- 別途、制約条件をいくつか抜粋して、実装の仕方の例を紹介する予定です。
- OR-Toolsのエキスパートの方には少々退屈な内容かもしれません。初心者の方であれば、参考になるかもしれません。


# 注意事項
- 当方、OR-Toolsの初心者です。おおむね理解したつもりで書いていますが、もしかしたら間違っているところがあるかもしれません。ご容赦下さい。


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


# (2) シフトの表現
- ブール変数work[e, s, d]で、従業員eの、d日目の、シフトsの勤務の状態を表している。
    - シフトsは、0:休暇／1:午前勤務／2:午後勤務／3:夜間勤務のいずれかを示す値。
        - 休暇もシフトの1つとして取扱うようにしている。
    - work[e, s, d]=True(=1)となったら、従業員eが、d日目の、シフトsの勤務に割り当てられたことになる。


# (3) 目的関数
- ブール変数obj_bool_vars[i]や整数の変数obj_bool_int_vars[i]に、係数を掛けて、足し合わせた値を目的関数としている。この目的関数の値を最小化することにより、種々の制約条件を満たすシフトスケジュールを作るようにしている。

```math
\sum_{i}{obj\_bool\_vars[i]*obj\_bool\_coeffs[i]} + \sum_{j}{obj\_int\_vars[j] * obj\_int\_coeffs[j]}
```

- ブール変数obj_bool_vars[i]の項には、ブール変数workに、係数wを掛けて、足し合わせた値も含まれている。

```math
\sum_{e}\sum_{d}\sum_{s}{work[e, s, d] * w}
```

- 取扱う制約条件によって、ブール変数obj_bool_vars[i]の項と整数の変数obj_bool_int_vars[j]の項を使い分けている。
    - ブール変数obj_bool_vars[i]の項
        - ハード制約条件や(S1)のソフト制約条件を実装するのに用いる。
    - 整数の変数obj_bool_vars[j]の項
        - (S2)のソフト制約条件を実装するのに用いる。


# (4) 制約条件
## (4.1) ハード制約条件
- ハード制約条件は、基本的には、ブール変数work[e, s, d]の値に、直接制約を課すことにより、実装している。

#### 　(例) あらかじめ指定した従業員のシフトを固定する(H)。
- 従業員eを、d日目の、シフトsに割り当てたい場合は、以下の通り、ブール変数work[e, s, d]をTrue(=1)に固定する制約を加える。

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


## (4.2) ソフト制約条件
- ソフト制約条件は、基本的には、ブール変数obj_bool_vars[i]の値に、ペナルティを表す係数を掛けた値を、目的関数に加え、それを最小化することにより、実装している。

### 　(例) なるべく、従業員のシフトの希望を反映する(S)。
- なるべく、従業員eを、d日目の、シフトsに割り当てたい場合は、以下の通り、ブール変数work[e, s, d]の値に、ペナルティwを掛けた値を、目的関数に加える。
- 目的関数を最小化するので、ペナルティwに、負の値を設定しておくと、指定したシフトに、優先的に、割り当てることができる。

```python
    # Employee requests
    for e, s, d, w in requests:
        obj_bool_vars.append(work[e, s, d])
        obj_bool_coeffs.append(w)
```
([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)

### シフトの組合せに応じて、反映される度合いを変えたい場合は
- シフトの組合せに応じて、反映される度合いが変わる制約条件の場合は、ブール変数obj_bool_vars[i]の項の代わりに、整数の変数obj_int_vars[i]の項を用いる。整数の変数obj_int_vars[i]の値に、ペナルティを表す係数を掛けた値を、目的関数に加え、それを最小化する。
    - 例：なるべく、曜日／シフト毎に必要となる最小の従業員数を確保する(S2)。必要以上の従業員数とせざるを得ない場合は、なるべく人数を減らす(S2)。
        - なるべく、曜日／シフト毎の従業員数が、必要最小の従業員数に近くなるようにしたい場合は、両者の差異excessを、整数の変数obj_int_vars[j]の値に設定し、そこにペナルティover_penaltyを掛けた値を、目的関数に加える。
        - 目的関数を最小化するので、ペナルティover_penaltyに、正の値を設定しておくと、曜日／シフト毎の従業員数が必要最小の従業員数を超える、シフトの組合せには、なりにくくなる。excessが大きくなるほど、その度合いが強くなる。

```python
    # Cover constraints
    for s in range(1, num_shifts):
        for w in range(num_weeks):
            for d in range(7):
                works = [work[e, s, w * 7 + d] for e in range(num_employees)]
                # Ignore Off shift.
                min_demand = weekly_cover_demands[d][s - 1]
                worked = model.NewIntVar(min_demand, num_employees, '')
                model.Add(worked == sum(works))
                over_penalty = excess_cover_penalties[s - 1]
                if over_penalty > 0:
                    name = 'excess_demand(shift=%i, week=%i, day=%i)' % (s, w,
                                                                         d)
                    excess = model.NewIntVar(0, num_employees - min_demand,
                                             name)
                    model.Add(excess == worked - min_demand)
                    obj_int_vars.append(excess)
                    obj_int_coeffs.append(over_penalty)
```
([シフトスケジュール問題を解くプログラム]
(https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py)のソースコードより引用)


# 参考資料

- [OR-Toolsのインストール](https://developers.google.com/optimization/install)
- [OR-ToolsのGet Started Guides](https://developers.google.com/optimization/introduction/python)
- [Employee Schedulingのサンプルコード](https://developers.google.com/optimization/scheduling/employee_scheduling)(解説付き、ここで紹介しているものとは別のサンプルコード)