3.8.6. スラック変数とソフト制約関数#
スラック変数の ソフト制約関数 SoftConstraint による書き換えについて紹介します． 一日分のシフトを決めるとしましょう．:
m = Element(value='ABCDE') # Man
s = Element(value=['Day','Ngt','Off']) # Shift
work = Parameter(index=s, value={'Day': 8, 'Ngt': 6}) # 勤務時間
require = Parameter(index=s, value={'Day': 2, 'Ngt': 2}) # 必要人数
x = BinaryVariable(index=(m,s)) # 人 m にシフト s を割り当てるか
シフトごとに勤務時間と一日分の必要人数が与えられています． ここで value で与えられていないシフト Off(=休み)はともに 0 であることに注意しましょう．
今回の目標は勤務時間の平準化制約を記述することです． 平準化制約は全員の勤務時間をできるだけ同じにしたい，という要望なので， 厳密な等式制約としては書けなさそうです． 必要人数を満たすことを前提とすると，勤務時間の平均値を目指せばよさそうです．:
workave = Sum(require[s]*work[s])/len(m.set) # 勤務時間平均値
記述方法の 1 つとしてスラック変数を用いた方法があります． スラック変数は違反量(>0)を変数に押し付けますが，平準化制約の場合， 正側にも負側にも違反する可能性があるため，両辺にスラック変数が必要になります．:
slack1 = Variable(index=m, lb=0) # 勤務時間平均値からの違反量(-)
slack2 = Variable(index=m, lb=0) # 勤務時間平均値からの違反量(+)
p = Problem()
p += Selection(x[m,s], s), '人 m のシフトは一つ'
p += Sum(x[m,s], m) >= require[s], 'シフト s の必要人数を満たす'
p += Sum(work[s]*x[m,s], s) + slack1[m] == workave + slack2[m], '勤務時間平準化'
p += Sum(slack1[m] + slack2[m]), 'slack'
p.solve(silent=True)
print(p.result.method, p.status, p.objective.val)
# simplex NuoptStatus.OPTIMAL slack.val=6.0000000000000036
スラック変数を目的関数に組み入れることで，勤務時間をできるだけ平均値に近づけることができます． スラック変数を用いた記述は基本となる考え方であり，多くのモデリング言語でも同様の記述ができます．
ソフト制約関数 SoftConstraint を用いると，平準化制約をスラック変数を用意することなく書き換えることができます．:
p = Problem()
p += Selection(x[m,s], s), '人 m のシフトは一つ'
p += Sum(x[m,s], m) >= require[s], 'シフト s の必要人数を満たす'
p += Sum(work[s]*x[m,s], s) == workave, SoftConstraint(1), '勤務時間平準化'
p.options.method = Options.Method.WLS
p.solve(silent=True)
print(p.result.method, p.status, p.result.softPenalty)
# wls NuoptStatus.FEASIBLE 6.000000000000002
このような書き換えは一般に可能ですが，正側にも負側にも違反する等式制約の書き換えとは相性がよいです． また，スラック変数を用いた記述では目的関数に追加する必要があり，変数のスコープが大きくなる点も解消されています．
ソフト制約は求解アルゴリズム MILP/WCSP/WLS のいずれでも使用可能ですが，WCSP の場合， アルゴリズムの特性上，小数部分が切り捨てられ，結果が変わることがあるのでご注意ください． また，上記の制約のみでは勤務時間平準化を優先すべく，必要人数を超えた出勤が発生してしまいます． こちらは別に回避する仕組みが必要でしょう．
スラック変数を用いた記述は基本となる考え方ですが，制約式や目的関数に混在することで煩雑になりがちです． ソフト制約関数を用いることで，制約と違反量を分離した記述が可能になります．