組合せ最適化への挑戦録（勤務スケジューリング）3.条件の改良

これまでの踏跡

前回までの成果

プログラム暫定品

import pulp

Member = ["1", "2", "3", "4", "5", "6", "7", "8"] 
Day = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"] 
Action = ["昼勤", "夜勤"] 

#問題の宣言
ShiftScheduling = pulp.LpProblem("ShiftScheduling", pulp.LpMinimize)

#変数宣言
x = {}
for m in Member:
    for d in Day:
        for a in Action:
            x[m, d, a] = pulp.LpVariable("x({:},{:},{:})".format(m,d,a), 0, 1, pulp.LpInteger)

#目的関数：新人8番を最小限に抑える
ShiftScheduling += sum(x['8', d, a] for d in Day for a in Action),"Target"

#制約条件1
for d in Day:
    for a in Action:
        ShiftScheduling += pulp.lpSum(x[m, d, a] for m in Member) == 2, "Constraint_{:}_{:}".format(d,a)

#制約条件2
NG = [['1','Tue','昼勤'],['2','Wed','夜勤']]
for m, d, a in NG:
    ShiftScheduling += x[m, d, a] == 0, "Constraint_NG_{:}_{:}_{:}".format(m,d,a)

#出力　計算が成立しているか否か
results = ShiftScheduling.solve()
print("optimality = {:}, target value = {:}".format(pulp.LpStatus[results], pulp.value(ShiftScheduling.objective)))

#出力　シフト表の中身
for v in ShiftScheduling.variables():
  print(f"{v} = {pulp.value(v)}")

「＃制約条件」について

条件自体は参考サイト1から完全に流用

参考サイト1：https://tech.unifa-e.com/entry/2019/06/21/064243

制約条件1

for d in Day:
    for a in Action:
        ShiftScheduling += pulp.lpSum(x[m, d, a] for m in Member) == 2, "Constraint_{:}_{:}".format(d,a)

for文でd,aを指定したあとで、問題文に制約条件を入れているのでd,aを固定した状態での全てのmの総和を取って
制約条件にしていることになる。
今回の場合はx(1,"MON","昼)からx(8,"MON","昼")の総和==2、x(1,"MON","夜")からx(8,"MON","夜")の総和==2・・・以下略。
これの意味するところは「シフトごとの参加人数は二人」である。以上、以下、の条件はまだ付けていない。

"Constraint_d_a"は制約条件名になる。
"Constraint_Mon_昼"の値を見れば、月曜昼に何人の勤務者が参加しているかが分かる事になる

今回は先に数式があって、それを言語化しているが、これを逆に言語から数式に落とし込むのは結構苦労しそうである。

制約条件2

NG = [['1','Tue','昼勤'],['2','Wed','夜勤']]
for m, d, a in NG:
    ShiftScheduling += x[m, d, a] == 0, "Constraint_NG_{:}_{:}_{:}".format(m,d,a)

制約条件2はNG指定である。
簡略化して2つだけにしてあるが、勤務者1は火曜日の昼を、勤務者2は水曜日の夜を忌避していることになる。
基本的には制約条件1と全く同じで、m,d,aに指定の値を放り込み、それがゼロになるようにすることで制約条件を作っている。

「#シフト表の出力」について

シフト表の出力

for v in ShiftScheduling.variables():
  print(f"{v} = {pulp.value(v)}")

参考サイト2:https://yoo-s.com/topic/detail/815

上記参考サイト2の出力を切り貼りしたら動いた。
前回苦労したシフト表の出力。x(m,d,a)の中身を出力している。

動作的には、まず変数xは辞書型である。辞書の中身はキー[m,d,a]に対して値が関数x(m,d,a)である。
関数x(m,d,a)に入っている値は、.solveを掛けた後、問題.varibales()で引き出すことが可能・・・という仕組みになっている、はず。

シフト表の出力の流れとしては、まず1行目で変数vに「問題が所有するすべての変数」をぶちこむ。
2行目でf文字列を使って変数名＝変数の値をプリントする。という形式。
f文字列については初見だったがf" "で閉じられた文字列の内、{ }内の部分は変数ないし関数として値を自動変換する、というものらしい。(参考サイト3を参照）
なので、今回の場合は f""内の=はそのまま文字列で出力、{ }内のvやpulp.value(v)についてはプログラム上で保持する値を代入した結果を出力すると言う処置になる。

参考サイト3：https://qiita.com/ksato9700/items/44caf7bf0329fb987499

矛盾する制約条件の場合の挙動

さて、ひとまず参考サイト1にある通りの仕様は実装でき、動作も確認した。
シフト表もこのままでは見づらいが出力はできている。
今後は挑戦録1.に書いた仮仕様に寄せていくことになるが、先に「制約条件を満たせない場合の挙動」を確認することにする。
今回の場合、制約条件1,2は絶対条件(==2,あるいは==0を満たせないと駄目）となっているので、目的関数と矛盾する制約条件に変えてプログラムを動かしてみる。

矛盾する制約条件

for m in ["1","2","3","4","5","6","7"]:
    for d in Day:
          NG = [[m,d,'昼勤']]
          for m, d, a in NG:
            ShiftScheduling += x[m, d, a] == 0, "Constraint_NG_{:}_{:}_{:}".format(m,d,a)

この制約条件は要するに「8番以外の全員が昼勤NGとした」ということである。
当然ながら制約条件1の「昼勤は2人」と矛盾する。これを解いてみると、

矛盾する場合の出力

optimality = Infeasible, target value = 14.0

Infeasible：実行不可能、かつ、目的関数の値（新人8が昼勤に入る回数）が14回、と出る
7回の昼勤で14回出勤という矛盾になるということらしい。
.varibales()で変数の中身を見ると、x(8,Mon,昼勤) = 2.0 と出る。
変数定義の0以上1以下の整数、というルールが破られているようだ。
元から矛盾しているから気にすることではないかもしれないが、制約条件と変数定義が矛盾を起こすと、
「ひとまず変数定義に逆らってもいいから解を出す」という挙動が起きるらしい。

考察

挑戦録4.からは、自前の条件を数式化していく必要があるが、先に全体設計をもう少し詰めたほうが良さそうである。

＜全体設計＞
1.エクセルを取り込んで入力データを取得する
2.各種定数(今回プログラム中のm,d,aに当たる部分）をdataframeからリスト化する
3.問題の定義
4.変数と目的関数、制約条件の設定
5.solve()で解く
6.変数とその中身をシフト表に変換する
7.エクセルデータとして保存する

まず1.からして厄介で、これまでのような完全流用ではないので、「どのような入力データが良いか」「実際にはどのような入力データが有るのか」のすり合わせが必要となる。まずは仮データを使うことになるだろう。

6.についてもx(m,d,a)=1というデータをばらし、少なくとも下表のようにする必要があり、前途多難である。

　　　　　月曜昼勤　月曜夜勤
勤務者1　　　○
勤務者2　　　　　　　　○

まあ、やるしかないのでやるだけである。形になるといいなあ。