3.8.9. 連続稼働時間制約の書き方#
数理最適化によく登場する 0-1 整数変数を用いたテクニックを紹介します． 0-1 整数変数は「状態の on/off」を表現するのに使われることも多く，通常 1 を on 状態として扱います． PySIMPLE では 0-1 整数変数の宣言に専用のキーワード 0-1 整数変数クラス BinaryVariable が用意されています．:
>>> i = Element(value=[1, 2, 3], name='i')
>>> z = BinaryVariable(index=i, name='z')
>>> z
z:
z[1]
z[2]
z[3]
3.8.9.1. 最低連続稼働時間制約#
運転計画問題やスケジューリング問題でよくみられる起動・停止を表現してみましょう． まずは準備として，各時刻での機器の稼働状態を表す変数 z と，停止→起動となった時刻を検知する変数 zs を用意します． 挙動の確認のため，時刻 3, 4 に稼働しているとしてみましょう．:
t = Element(value=range(1, 6)) # 時刻
z = BinaryVariable(index=t) # 稼働フラグ(時刻 t に稼働していたら 1)
zs = BinaryVariable(index=t) # 起動フラグ(時刻 t に起動するときに 1)
p = Problem()
p += z[3] == 1 # 時刻 3, 4 は稼働
p += z[4] == 1 # p += z[t<(3, 4)] == 1 とも書ける
p += z[1] == zs[1] # 時刻 1 は個別
t1 = t>1
p += z[t1] - z[t1-1] <= zs[t1], 'z と zs の関係定義'
p += Sum(z[t] + zs[t]) # 稼働時間と起動回数は少なく
p.solve(silent=True)
Printf('{}: z={}, zs={}', t, z[t].val, zs[t].val)
この出力は以下となります．:
1: z=0, zs=0
2: z=0, zs=0
3: z=1, zs=1
4: z=1, zs=0
5: z=0, zs=0
zs[3] が 1 になっており，時刻 2 → 3 の起動時刻を表現できています． 例えば，起動コストを表現したい場合は「起動コスト*zs[t]」とすればよいことになります． 停止状態の表現も同様です．
今度は機器の最低連続稼働時間を表現してみましょう． スケジューリング問題の場合は最低連勤務働時間となります．:
t = Element(value=range(1, 11)) # 時刻
i = Element(set=t.set)
k = Parameter(value=5) # 最低連続稼働時間
z = BinaryVariable(index=t) # 稼働フラグ(時刻 t に稼働していたら 1)
zs = BinaryVariable(index=t) # 起動フラグ(時刻 t に起動するときに 1)
p = Problem()
p += z[2] == 1 # 時刻 2, 9 は稼働
p += z[9] == 1 # p += z[t<(2, 9)] == 1 とも書ける
#p += z[1] <= zs[1] # 時刻 1 は個別
#t1 = t>1
#p += z[t1] - z[t1-1] <= zs[t1], 'z と zs の関係定義'
p += z[t] - z.get(t-1) <= zs[t], 'z と zs の関係定義'
it = Condition((i,t), (t-k+1<=i, i<=t))
p += Sum(zs[it(0)], it(0)) <= z[it(1)], '最低連続稼働時間制約'
#p += Sum(zs[t]) <= 1 # 起動は 1 度まで
p += Sum(z[t])
p.solve(silent=True)
Printf('{:2}: z={}, zs={}', t, z[t].val, zs[t].val)
この出力は以下となります．:
1: z=0, zs=0
2: z=1, zs=1
3: z=1, zs=0
4: z=1, zs=0
5: z=1, zs=0
6: z=1, zs=0
7: z=0, zs=0
8: z=0, zs=0
9: z=1, zs=1
10: z=1, zs=0
機器が時刻 2 から 6 まで稼働しており，最低連続稼働時間を満たしていることがわかります． 最低連続稼働時間制約は「時刻 t-k+1 から t までの間に起動したならば時刻 t は稼働していなければならない」 ことを表現しています． 最低連続稼働時間制約は他にも類似ケースが考えられます．
開始時における累積稼働時間が与えられている
時刻 1 と最終時刻が繋がっている
最低連続停止時間
いずれも同様に定式化が可能ですので考えてみてください．
3.8.9.2. 最大連続稼働時間制約#
最大連続稼働時間制約は最低連続稼働時間制約に比べると単純です． 機器が連続して稼働するのは最大 k 時間まで，という制約は，任意の「連続する k+1 区間ですべて稼働」 を除外すれば OK です．:
t = Element(value=range(T)) # 時刻．0, .., T-1
tt = Element(value=range(T-k)) # 0, .., T-k-1
i = Element(value=range(k+1)) # 0, .., k
z = BinaryVariable(index=t) # 0: 稼働しない，1: 稼働する
Sum(z[tt+i], i) <= k # 最大連続稼働時間制約
応用として次のケースを考えてみましょう．
機器の稼働は時刻 0, .., T-1 の範囲外でも発生し，稼働状況は不明
この状態での最大連続稼働時間制約を考えてみます．T=4, k=2 のときは 以下のようなイメージです．
時刻 |
-2 |
-1 |
0 |
1 |
2 |
3 |
4 |
5 |
|---|---|---|---|---|---|---|---|---|
ケース 1 |
？ |
？ |
○ |
？ |
？ |
|||
ケース 2 |
？ |
？ |
○ |
○ |
？ |
？ |
||
ケース 3 |
？ |
？ |
○ |
○ |
？ |
？ |
||
ケース 4 |
？ |
？ |
○ |
○ |
？ |
？ |
||
ケース 5 |
？ |
？ |
○ |
？ |
？ |
ここで時刻 -2, -1, 4, 5 の稼働状態は不明のため，最大連続稼働時間が k=2 を超える可能性のあるケースを 除外すると，ケース 3 のみが許容されることになります． 最悪ケースとして「？」部分が稼働していると考えると，愚直な定式化は次のようになります．:
t = Element(value=range(T)) # 0, .., T-1
z = BinaryVariable(index=t)
1 + 1 + z[0] <= 2
1 + z[0] + z[1] <= 2
z[0] + z[1] + z[2] <= 2
z[1] + z[2] + z[3] <= 2
z[2] + z[3] + 1 <= 2
z[3] + 1 + 1 <= 2
さて，この定式化を汎用的に記述するにはどうすればよいでしょうか．
初期条件やフロー保存則の記述テクニック を使って Sum(z.get(t+i), i) <= k
のように記述できそうですが，デフォルト値の 1 を表現することができません．
そこで，少し面倒ですが，デフォルト値用のパラメータ default を用意することで，
以下のように記述することができます．:
t1 = Element(value=range(-k, 0)) # -k, ,,. -1
t = Element(value=range(T)) # 0, .., T-1
t2 = Element(value=range(T, T+k)) # T, .., T+k-1
tall = Element(set=t1.set | t.set) # -k, .., T-1
i = Element(value=range(k+1)) # 0, .., k
z = BinaryVariable(index=t)
default = Parameter(index=t1.set | t2.set, value=1)
Sum(z.get(tall+i) + default.get(tall+i), i) <= k # 最大連続稼働時間制約
# Sum(z.get(tall+i, default=1), i) <= k # こう書きたい
少し手間になってはしまうのですが，汎用的な記述ができました． get メソッドは辞書のそれのようにデフォルト値をとれると便利なのですが，実は実装の都合で提供できておりません． 最小・最大連続稼働時間制約は運転計画問題以外でもスケジューリング問題で頻出の制約です． 今回のように応用のバリエーションも豊富なため，しっかりと押さえておきましょう．