3.3.8. 制約式種¶
全ての制約式は次の 3 つの種類に分類されます．
ハード制約式(通常)
セミハード制約式
ソフト制約式
ハード制約式とは，最も優先して満たすべき制約式（必ず満たさなければならない制約式）のことです． 制約式種を指定しない場合はハード制約となります．
セミハード制約式とは，ハード制約式の次に優先して満たすべき制約式のことです． 通常，必ず満たさなければならない制約式の一部をセミハード制約式とし，実行不可能性の原因をセミハード制約に 押し付けるという使い方をします．
セミハード制約は wcsp のみで有効です． 他のアルゴリズムにおいてはセミハード制約はエラーあるいはハード制約として解釈されます．
ソフト制約式は，優先度がもっとも低く，必ずしも満たす必要はないが，できるだけ満たして欲しい制約式のことです． その際，ソフト制約式は，各制約式の違反量からペナルティ量を計算し，その総ペナルティ量が最も小さくなることをもって できるだけ制約式を満たしたと解釈します(計算方法は後述)．
ソフト制約は wcsp/wls/simplex/asqp のみで有効です． 他のアルゴリズムにおいてはソフト制約はハード制約として解釈されます．
問題クラス・解法と制約種の対応は次のようになります．
制約式種 |
wcsp |
wls |
wcsp/wls 以外 |
|---|---|---|---|
ハード制約 |
〇 |
〇 |
〇 |
セミハード制約 |
〇 |
〇※1 |
△※1※2 |
ソフト制約 |
〇 |
〇 |
△※2 |
※1 HardConstraint 扱い ※2 一部の解法のみ
3.3.8.1. ハード制約関数 HardConstraint¶
制約がハード制約式であることを指定するには制約に続いてカンマで区切って HardConstraint 関数を用います．:
problem += z[i] >= 1, HardConstraint()
制約式種を指定しない場合，ハード制約と認識されるため，以下の表現はいずれも同様の意味を持ちます．:
problem += z[i] >= 1
problem += z[i] >= 1, HardConstraint()
problem += z[i] >= 1, SoftConstraint(-1) # 後述
また，制約式に名前を付ける場合，制約式種と名前の順序は任意です．以下の表現はいずれも同様の意味を持ちます．:
problem += z[i] >= 1, 'cons'
problem += z[i] >= 1, HardConstraint(), 'cons'
problem += z[i] >= 1, 'cons', HardConstraint()
3.3.8.2. セミハード制約関数 SemiHardConstraint¶
制約がセミハード制約式であることを指定するには制約に続いてカンマで区切って SemiHardConstraint 関数を用います．:
problem += z[i] >= 1, SemiHardConstraint()
problem += z[i] >= 1, SoftConstraint(-2) # 同じ．後述
3.3.8.3. ソフト制約関数 SoftConstraint¶
制約がソフト制約式であることを指定するには制約に続いてカンマで区切って SoftConstraint 関数を用います．:
problem += z[i] >= 1, SoftConstraint(1)
SoftConstraint 関数は引数により制約式の違反量の計算パラメータの設定もできます．:
def SoftConstraint(weight: int, quad=None: float, linear=None: float):
- weight: 重みの基本となる値．非負整数または -1 または -2．
-1, -2 はそれぞれ HardConstraint, SemiHardConstraint を表す
quad: 重みの二次の係数．非負値．
linear: 重みの一次の係数．非負値．
制約式 cons が制約を満たしていない(cons.violation>0) の場合，ソフト制約のペナルティ penalty は以下で定義されます．:
v = cons.violation
penalty = (quad*v**2 + linear*v) * weight # wcsp
penalty = v * weight # wcsp 以外
また，SoftConstraint 関数の第 2 引数と第 3 引数は省略することができ，次のような規則により解釈されます．:
# 第 2, 3 引数の省略
SoftConstraint(weight) == SoftConstraint(weight, 0, 1) # penalty = v*weightと等価
# 第 3 引数の省略
SoftConstraint(weight, quad) == SoftConstraint(weight, quad, 0) # penalty = quad*v**2 * weightと等価
このペナルティ値は weight 属性と violation 属性の積で計算できます．:
z = BinaryVariable()
problem = Problem()
problem += z >= 1, 'cons1', SoftConstraint(3) # penalty = 1 * 3
problem += z >= 1, 'cons2', SoftConstraint(3, 2) # penalty = 2*1**2 * 3
problem += z >= 1, 'cons3', SoftConstraint(3, 2, 1) # penalty = (2*1**2 + 1*1) * 3
for cons in problem.constraints.values():
print(cons.weight*cons.violation)