組合せ最適化への挑戦録（勤務スケジューリング）2.動作の理解

これまでの踏跡

今回の取り組み

前回、まずは仮仕様の作成と、完コピしたプログラムの動作確認が終わった。
今回は動作の理解に踏み込むこととする

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 += pulp.lpSum(x['8', d, a] for d in Day for a in Action), "Target"
#出力
results = ShiftScheduling.solve()
print("optimality = {:}, target value = {:}".format(pulp.LpStatus[results], pulp.value(ShiftScheduling.objective)))

「#問題の宣言」について

これは要するに、変数ShiftSchedulingに対して、pulp.Lpproblemというソルバーを適用しますよ、ということで良いと思う。

下記参考サイト1によると、
pulp.LpProblem：線形計画問題のオブジェクトを定義します。引数には問題の名前と目的関数を最小化するか最大化するかを書きます。（最小化するときは、pulp.LpMinimize、最大化するときは、pulp.LpMaximize）

との事なので、"ShiftScheduling"が問題の名前となる。

ただ、ShiftSchedulingと"Shiftscheduling"になっているところが良く分からない。
""囲みということは文字列のはずだが、文字列と変数は違うものじゃなかったか？と思い、参考サイト2を当たったところ、
"ShiftScheduling"というのはlpファイル出力という出力を行った時に使うファイル名になるものらしい。
よって、変数名と問題の名前は別であったとしても問題はない（実際に"test"としても問題なくプログラムは動いた）

ShiftSchheduling :　問題
"ShiftScheduling"　：　問題の名前

ということになる。

参考サイト1：　https://techacademy.jp/magazine/32426
参考サイト2：　https://www.coin-or.org/PuLP/pulp.html

「#変数宣言」について

for文でm,d,aをくっつけて、xの添字にしている。

pulp.LpVariableは変数を生成するコマンドのようなので、
「x_勤務者1_月曜_昼勤」というような変数を全パターン生成していると思われる。

パターン数は勤務者8人×7日×2交代なので、112個の変数だ。
今回の仮仕様だと7日目の夜勤は存在しないので、8個多く作ってしまっている事になる・・・が、これの修正はひとまず後回し。

Lpvaribaleの引数を全て書くと、参考サイト2から下記のようになる。

LpVariable （name、lowBound = None、upBound = None、cat = 'Continuous'、e = None ）

プログラムの引数は下記の4つに見える
・"x({:},{:},{:})".format(m,d,a)
　→これはnameに当たるものであろう。lp出力時に使う名前となるので、変数「x_勤務者1_月曜昼勤」をlp出力すると、
　ファイル名が「x勤務者1_月曜_昼勤」で表示されるようになっているらしい。
　つまり、lpファイルは変数別に出力することも可能な仕組みということか。
・0
　→lowBoundに該当すると思われる。定義はThe lower bound on this variable’s range.
　つまり、変数の範囲の下限を示すということなので、x[m,d,a]の最小値は0となる。
・1
　→upBoundに該当すると思われる。lowboundの逆なので、x[m,d,a]の最大値は1となる。
・pulp.LpInteger
　→catに該当する・・・？多分。LpIntegerは整数変数で、デフォルトは連続変数とのことなので、
　今回はx[m,d,a]の値を0,1で判断できるようにしたいと考えたのでこのような指定になったということなのだろう。
　残りの引数eについては全然分からんが、今回はデフォルトのまま進んでるようなので無視する。

これらをまとめるとx[m,d,a]は、
「lpファイル出力するときはx[m,d,a]というファイル名になり」、「最小値0、最大値1の範囲を取る」、「整数変数」ということになる。
x[m,d,a]は全112個あるので、112個の0,1が入る変数を作りました、という事だろう。

「#目的関数」について

ShiftScheduling += pulp.lpSum(x['8', d, a] for d in Day for a in Action), "Target"

「+=」の使い方に馴染みがなかったが、下記参考サイト3に書いてあった。
参考サイト3：https://docs.pyq.jp/python/math_opt/pulp.html

m + = 式について
PuLPで最も間違えやすいと思われるのが、この式でしょう。 「モデルに式を足す」表現で「モデルに目的関数を設定する」ことを意味します。 追加ではなく設定です。

ShiftSchedulingは「#問題の宣言」で書いたとおり問題である。
pulpにおいては、問題の名前と最小最大をまず定義し、目的を後で入れ込む形で問題を作る、と考えれば良さそう。

次にpulp.lpSumは普通の加算処理とのこと。プログラムをpulp.lpSumではなくsumにしても同様に動くことを確認。
ただし、参考サイト3によると計算効率がpulp.lpSumの方が良いとのことなので、変数の数が増えた時を見越してpulp.lpSumにするほうが良いと思われる。
今は8人7日2勤務で112個だが、人と日が増えると指数関数的に変数が増えるため。

sumの中身がx['8', d, a] for d in Day for a in Actionなので、
dにMon~Sun,aに昼夜を入れたときの総和（変数[8,Mon,昼]~[8,Sun,夜]）が目的関数として設定されていることになる
「#問題の宣言」で最小化を指定したので、この総和が最小になるようソルバーを動かしますよ、という意味であろう。

残った問題は”Target"である。
名前をつけているのは間違いないと思うのだが、詳細が見当たらない・・・
違うパッケージだが、参考サイト4の下記に示すような処理をしているのか？

問題に対し，+= 制約式 を行うと制約式の追加と見做されます．:
problem += 2*x >= 0
カンマで区切って文字列を与えることにより制約式に名前をつけることもできます．:
problem += 2*x >= 0, '制約式1'
問題の制約式は 問題[制約式名] でアクセスすることができます．:
print(problem['制約式1'])}

同様に試しても、pulpでは問題の成約式にはアクセスできなかったが・・・lp出力が分かれば解決するのかもしれないので、
ひとまず保留にしておく。"Target"をプログラムから外しても問題なく動作することは確認済み。

「#出力」について

.solveというのは、問題を作ったのであとは勝手に解いてね、という指定らしいので、特に気にすることはない。
.solveにおいてどういう計算がされたか、という中身の部分については良く分からないが、これぐらいの変数量なら普通に
行列式を解くか総当りで当たれそうな気もする。量が増えたときに対応するために色々工夫も在るのだろうが、外からは見えない部分であろう。

printの中身は、"optimality"にpulp.LpStatus[results]、
"target value"にpulp.value(ShiftScheduling.objective)がそれぞれ代入されている。

参考サイト3から、pulp.LpStatus[results]は「最適解が得られたかどうか」を出力するもの。
今回はpulp.LpStatus[results]=Optimalなので成功と分かる。

pulp.value(問題.objective)は問題の目的変数の値、ということ。
今回は0なので、新人8の出番は0になった（＝最小化できた）、ということになる。

動作は掴めたので、シフト表を出力してみよう

長々と書いたが、要するに必要なデータはすべてx[m,d,a]の中に入っていることがわかる。
よって、print(x)で全てが明らかになるのではないか？

#print(x)の結果
{('1', 'Mon', '昼勤'): x(1,Mon,昼勤), ('1', 'Mon', '夜勤'): x(1,Mon,夜勤)・・・・・以下略

駄目だった。solveしたからと言って、元の変数に値が入れられる訳ではないらしい。Replace=Falseと言う感じか。
ただ、ちょっと想像と違ったのが辞書型になっていることだ。
これを見る限り、('1', 'Mon', '昼勤')というキーに対する値がx(1,Mon,昼勤)になっている・・・0,1じゃないの？？？
辞書型ならばxの中に('1', 'Mon', '昼勤')などのキーが112個あって、それぞれに0,1の値が入っていると思ってたのだが・・・。

また、pythonでは（　）の中身というのは基本的に「関数の引数」か「タプル」のどちらかを表すはずだが、これはどっちだ・・・？
タプルは変数の直後にはつかない気がする。
しかし、関数の引数と捉える場合、xという関数に対する引数になるのだが、それだと循環参照になる気がする

x(8,Fri,昼勤）はxに3つの引数を渡すことだが、xは辞書なので8,Fri,昼勤はキーだ。キーを渡すと当然値が返ってくるが、
その値もまたx(8,Fri,昼勤）なのだ・・・・・・・・？？？？　ちょっとよく分からんな。

問題の中身も見てみよう

#print(ShiftScheduling)の結果
ShiftScheduling:
MINIMIZE
1*x(8,Fri,夜勤) + 1*x(8,Fri,昼勤) + 1*x(8,Mon,夜勤) + 1*x(8,Mon,昼勤) + 1*x(8,Sat,夜勤) 
    + 1*x(8,Sat,昼勤) + 1*x(8,Sun,夜勤) + 1*x(8,Sun,昼勤) + 1*x(8,Thu,夜勤) + 1*x(8,Thu,昼勤)
    +  + 1*x(8,Tue,夜勤) + 1*x(8,Tue,昼勤) + 1*x(8,Wed,夜勤) + 1*x(8,Wed,昼勤) + 0
VARIABLES
0 <= x(8,Fri,夜勤) <= 1 Integer
0 <= x(8,Fri,昼勤) <= 1 Integer ・・・以下略

問題を見ると、x(8,d,a)は0か1の整数と定義されているし、0+Σx(8,d,a)が最小化されるように解く、というのも書いてある。

で、現状の課題は「じゃあ具体的にx(8,Mon,昼勤）には0が入ったの？1が入ったの？」ということを確認できないことである。
今回は必須事項を入力していないので全部0で自明なのだが・・・これが出せないと、スケジュール表が出力できない。
いったい、どうやって引っ張り出せばいいのだ・・・？

縦に長くなったのでひとまずここまで。後は明日の自分の頑張りに託す事とする。

追記

出力に成功した。制約条件を適当に載せた後、下記のプログラムを足したら動いた。

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

input

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

output

x(1,Fri,夜勤) = 0.0
x(1,Fri,昼勤) = 1.0
x(1,Mon,夜勤) = 1.0
x(1,Mon,昼勤) = 0.0
#以下略

0が休み、1が出勤となるはず。
これ以上の考察は3.で行うものとする。