内容

AddBoolOrメソッドによる制約条件の実装の例を紹介しています。OR-Toolsのサンプルコードとして紹介されている、シフトスケジュール問題を解くプログラムを題材としています。
備忘のため、Googleの数理最適化ツールOR-Toolsの、cp_modelモジュールのCpModelクラスのAddBoolOrメソッドの使い方を、簡単にまとめてみました。
OR-Toolsのエキスパートの方には少々退屈な内容かもしれません。初心者の方であれば、参考になるかもしれません。

注意事項

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

シフトスケジュール問題

OR-Toolsのサンプルコードとして紹介されている、シフトスケジュール問題を解くプログラムを題材とする。
シフトスケジュール問題では、以下のような問題を解いている。
- 8人の従業員の、3週間分の、シフトスケジュールを作る。1日の勤務は、午前／午後／夜間の3交代勤務を想定。
- シフトスケジュールには、以下の制約条件を反映する。
  1. 1日1シフトのみ(午前／午後／夜間のいずれか)の勤務とする(H)。
  2. あらかじめ指定した従業員のシフトは固定する(H)。
  3. なるべく、従業員のシフトの希望を反映する(S)。
  4. 連続する休暇は、1-2日間とする(H)。
  5. 連続する夜間の勤務は、1-4日間とする(H)。なるべく、2-3日間とする(S)。
  6. 一週間の休暇は、1-3日間とする(H)。なるべく、2日間とする(S)。
  7. 一週間の夜間勤務は、0-4日間とする(H)。なるべく、1-4日間とする(S)。
  8. なるべく、午後->翌日の夜間の勤務はしない(S)。
  9. 夜間->翌日の午前の勤務はしない(H)。
  10. なるべく、曜日／シフト毎に必要となる従業員数を確保する(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の勤務に従事することとなる。

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]の組合わせを反転したリストを作るようにしている。

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)のソースコードより引用)

制約条件を加える。

model.AddBoolOr(transition)

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

　制約条件「8. なるべく、午後->翌日の夜間の勤務はしない(S)。」の実装の方法

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

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]の組合わせを反転したリストを作るようにしている。

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日目の、シフトスケジュールが制約条件を満たしていないことになる。

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を加える。

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

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の中に、両者に対応する係数が含まれている。)。この目的関数を最小化することで、可能な限り、制約条件を満たすシフトスケジュールを作れるようにしている。

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)。」を実装した箇所のサンプルコードの抜粋。
- パラメータを設定している箇所

    # 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),
    ]

制約条件を実装している箇所

    # 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)より引用)