制約条件 Constraint

JijModelingで制約条件を記述するにはConstraintクラスを用います.

例えばよく用いられる単体制約

$$\sum_i x_i = 1$$

は以下のように記述されます。

import jijmodeling as jm

n = jm.Placeholder("n")
x = jm.Binary("x", shape=(n, ))

problem = jm.Problem("sample")
# 単体制約 (One-hot制約) 
problem += jm.Constraint('one-hot', x[:] == 1)

不等式制約

Constraintクラスでは不等式制約も扱うことができますが、制約条件は以下を満たす必要があります。

• 扱えるのは<=または<のみ。>=と>は使えません。
• 左辺値には決定変数が含まれる必要がある。
• 右辺値に決定変数が含まれない。

つまり以下のような制約条件は記述できません。

import jijmodeling as jm

n = jm.Placeholder("n")
K = jm.Placeholder("K")
x = jm.Binary("x", shape=(n, ))
y = jm.Binary("y", shape=(n, ))

jm.Constraint("invaild", x[:] <= y[:] + K)
jm.Constraint("invaild", x[:] - y[:] >= K)

上記のような制約条件は右辺を左辺に移行するまたはマイナスを両辺にかけて不等号を逆転させるようにしましょう。以下の形は実装できます。

jm.Constraint("vaild", x[:] - y[:] <= K)
jm.Constraint("vaild", - x[:] + y[:] <= K)

forall 引数

多くの制約条件は上記のように1本ではなく、添字に対して$`n`$本存在する場合があります。例えば次の形です。

$$\sum_{j=0}^{n-1} x_{i, j} = 1~~\forall i \in \{0, \cdots,n-1\}$$

このような制約はConstraint()のforall引数で記述することができます。

import jijmodeling as jm

n = jm.Placeholder("n")
x = jm.Binary("x", shape=(n, n))
i = jm.Element("i", n)

problem = jm.Problem("sample")
# 単体制約 (One-hot制約) 
problem += jm.Constraint('one-hot', x[i, :] == 1, forall=i)

forall引数にはSum関数の第一引数引数と同様にElementクラスまたは辞書型による糖衣構文{添字の名前: 添字の値の集合}という記述をすることができます(参考: 2. 総和演算 Sum)。 この記述を用いると次のようになります。

i = jm.Element("i", n)
problem += jm.Constraint('one-hot', x[i, :] == 1, forall={i: n})

複数のforallを書きたい場合

\forall $`\forall`$ に続く添字が複数ある場合の記述方法を紹介します。例えば

$$\sum_j x_{i, j, k-1} = 1~~\forall i \in \{0, \cdots, n-1\}, k \in \{1, \cdots ,n-1\}$$

という制約条件を表してみます。
このような複数の添字はlistを使って表現します。

import jijmodeling as jm

n = jm.Placeholder("n")
x = jm.Binary("x", shape=(n, n, n))
k = jm.Element("k", (1, n))
i = jm.Element("i", n)

problem = jm.Problem("sample")
# 単体制約 (One-hot制約) 
problem += jm.Constraint('one-hot', x[i, :, k-1] == 1, forall=[i, k])

forallに条件をつけたい場合

これまでに紹介した forall 以外にもにも以下のような添字に条件をつけた制約条件

$$\sum_i x_{i, j+1, k} = C_k ~\forall j, k~|~0 \leq j < k$$

を記述する方法を紹介します。

import jijmodeling as jm

C = jm.Placeholder("C", dim=1)
n = C.shape[0]
x = jm.Binary("x", shape=(n, n, n))
j = jm.Element("i", (0, n))
j = jm.Element("j", (0, n))
k = jm.Element("k", (0, n))

problem = jm.Problem("sample")
# 制約条件 
problem += jm.Constraint('one-hot', jm.Sum(i, x[i, j+1, k]) == C[k], forall=[k, (j, j < k)])

このようにタプルを用いることで条件を追加することができます。またこのように複数の添字に対しての条件を用いる場合はその順序に気をつける必要があります。上記のforall引数を

problem += jm.Constraint('one-hot', jm.Sum(i, x[i, j+1, k]) == C[k], forall=[(j, j < k), k])

という形で記述できないことに注意してください。

---

自明な制約条件による変数の固定化

自明な制約条件を課すことで変数を固定化することができます。 例えば $`x_i`$ の中の$`x_0`$だけ1に固定したい場合は

problem += jm.Constraint('fix', x[0] == 1)

と記述すると$`x_0=1`$と固定化されます。このような自明な制約条件を加えた場合 $`x_0`$ はソルバーに決定変数として渡されず 1 で固定されたインスタンスに翻訳されます。
ここでいう自明な制約条件は

• 等式制約
• 左辺が決定変数のみ (Sumや他演算を含まない)
• 右辺に決定変数を含まない

を満たす制約条件のことです。

to_pyqubo メソッドなどのfixed_variable引数との比較

to_pyquboメソッドの fixed_variable 引数でも変数を固定化することができるのでそちらと比較してみます。

制約条件による変数の固定

import jijmodeling as jm

n = jm.Placeholder("n")
x = jm.Binary("x", shape=(n, n))
i = jm.Element("i", n)

problem = jm.Problem("sample")
# ダミーのコスト関数
problem += x[:, :]
# 自明な制約条件による変数の固定化
problem += jm.Constraint("fix", x[0, i] == 1, forall={i: n})

# PyQUBOへ変換
pyq_obj = problem.to_pyqubo(ph_value={'n': 4})
qubo, const = pyq_obj.compile().to_qubo()

# 変数が固定化されているのでquboにx[0, *] は含まれない
assert ('x[0][0]', 'x[0][0]') not in qubo

# 固定していない変数は含まれる
assert ('x[1][0]', 'x[1][0]') in qubo

上記と同じ変数を固定する別の方法として to_pyquboする際に変数を固定する場合を紹介します。

import jijmodeling as jm

n = jm.Placeholder("n")
x = jm.Binary("x", shape=(n, n))

problem = jm.Problem("sample")
# ダミーのコスト関数
problem += x[:, :]
# 制約条件は入れない

# インスタンスデータを用意
ins_data = {'n': 4}
# 固定する変数のデータを用意
fixed_var = {'x': {}}
for i in range(ins_data['n']):
    fixed_var['x'][0, i] = 1

# PyQUBOへ変換
pyq_obj = problem.to_pyqubo(ph_value=ins_data, fixed_variables=fixed_var)
qubo, const = pyq_obj.compile().to_qubo()

# 変数が固定化されているのでquboにx[0, *] は含まれない
assert ('x[0][0]', 'x[0][0]') not in qubo

# 固定していない変数は含まれる
assert ('x[1][0]', 'x[1][0]') in qubo

どちらの方法でも変数を固定することができます。どのようなインスタンスでも固定する変数が決まっている場合は前者（自明な制約条件）を使い、インスタンスによって固定したい変数を柔軟に変更したい場合は後者（インスタンスを流し込む時のfixed_variables引数）という使い分けが可能です。

---

QUBOへの変換

PyQUBOに変換される際には"線形"な制約条件は自動的に罰金項に変換されます。2次以上の場合は自動変換は行われません。詳細はこのセクションの後半の自動変換を行わないを参照してください。
デフォルトでは以下の変換が行われています。

等式制約

制約条件

$$f_i(x) = C_i~\forall i$$

罰金項

$$\lambda \sum_i \left(f_i(x) - C_i\right)^2$$

ここで$`\lambda`$は罰金項の強さを表す未定乗数です。デフォルトでは自動で掛けられます。また未定乗数には制約と同じ名前が割り当てられます。

不等式制約

制約条件

$$f_i(x) \leq C_i~\forall i$$

不等式制約はスラック変数という補助的な決定変数を導入して等式制約に変形した後に罰金項に変換されます。
スラック変数 $`S_i \geq 0`$ を用いた等式制約は

$$f_i (x) ＋ S_i = C_i$$

のように表されます。スラック(slack)という単語が弛みなどを意味することからわかるようにスラック変数は不等式制約による$`f_i(x)`$の上限値までの余裕を表す変数です。

罰金項
不等式制約の罰金項は上記のスラック変数を導入した等式制約を罰金項として表現するのですが、QUBOにする際には以下の制限があります。

• スラック変数に上限が必要（言い換えると不等式の左辺に下限が設定される）
• スラック変数はデフォルトでは整数値

つまり罰金項は以下の形になります。

$$\lambda\sum_i \left(f_i(x) + S_i - C_i\right)^2 ~, 0\leq S_i \leq C_i,~S_i \in \mathbb{Z},~\forall i$$

この場合、JijModelingでの実装は以下となります。

import jijmodeling as jm

C = jm.Placeholder("C", dim=1)
n = C.shape[0]
x = jm.Binary("x", shape=(n, n))
i = jm.Element("i", n)

problem = jm.Problem("sample")

# 不等式制約
problem += jm.Constraint("inq", x[i, :] <= C[i], left_lower=0, forall={i: n})

ここではleft_lower引数に左辺値の上限を設定しました。スラック変数の上限値はこのleft_lowerを使って"右辺値+left_lower"に調整されます。

またデフォルトでは下限値は0となるので上記のコードはleft_lower引数を省略して

i = jm.Element("i", n)
problem += jm.Constraint("inq", x[i, :] <= C[i], forall={i: n})

と記述しても良いです。

自動変換を行わない

制約条件がQUBOの罰金項として機能するように自動変換される方法を紹介しました。
しかし上記のような自動変換をしてほしくない場合もあります。
その場合は auto_qubo引数をFalseに設定します。

auto_qubo=Falseに設定した場合、条件式の右辺を左辺に移項した項がペナルティとしてQUBOに追加されます。

例えば

import jijmodeling as jm
n = jm.Placeholder("n")
x = jm.Binary("x", shape=(n, n))
i = jm.Element("i", n)

problem = jm.Problem("sample")
problem += x[:, :]
problem += jm.Constraint("A", x[:, i] <= 2, forall={i: n}, auto_qubo=False)

と記述すると内部のQUBOは

$$\sum_{i, j} x_{i, j} + \lambda_{\mathrm{A}}\sum_j\left(\sum_i x_{i,j} - 2\right)$$

という形になります。

また決定変数に関して2次以上の項が含まれる場合、auto_qubo引数は強制的にFalseになります。 よって

import jijmodeling as jm
n = jm.Placeholder("n")
x = jm.Binary("x", shape=(n, n))
i = jm.Element("i", n)
problem = jm.Problem("sample")
problem += x[:, :]
problem += jm.Constraint("A", jm.Sum(i, (x[:, i] - 1)**2), forall=i)

と実装した場合、そのまま

$$\sum_{i, j} x_{i, j} + \lambda_{\mathrm{A}}\sum_j\left(\sum_i x_{i,j} - 1\right)^2$$

というQUBOとして解釈されます。

未定乗数の有無

QUBOとして表現される際の罰金項の強さを表す未定乗数ですが、Constraintコンストラクタの引数で with_multiplier=Falseとすることで自動で掛け算されないようにすることができます。

罰金項として付与しない

問題を解いたときに制約条件が守られているかの検証を行うために制約条件は入れたいが、QUBOに罰金項としては入れたくない場合があります（詳細は高度な制約条件についてを参照してください）。

そのような場合は Constraintコンストラクタの引数で with_penalty=False とすることで解のデコード・検証の際に制約条件が満たされているか確認しはしますが、QUBOに罰金項は追加しません。

!!! note "JijZeptでのQUBOへの自動変換" JijZeptでイジングマシンを使う場合、多くは上記の変換によって出力されたQUBOを解きますが、必ずしもそうではなく、より効率の良い変換が行われることもあります。ローカルでPyQUBOを用いて変換される場合は常に上記の変換が行われます。