Constraint

このセクションでは制約条件を表すクラスについて説明します。

制約条件の構築

制約条件クラスは、多項式クラスや行列クラスに対して変数間に働く制約条件を表します。

多項式クラス・行列クラスとの対応関係は次の通りです。

多項式クラス

行列クラス

制約条件クラス

BinaryPoly

BinaryMatrix

BinaryConstraint

IsingPoly

IsingMatrix

N/A

BinaryIntPoly

BinaryIntMatrix

BinaryIntConstraint

IsingIntPoly

IsingIntPoly

N/A

これに基づき、制約条件クラスは対応する多項式クラスを用いて構築されます。

Note

イジング多項式・行列クラスに対する制約条件オブジェクトの構築は現在未実装です。

制約条件クラスの構築は、コンストラクタから直接構築するのではなく、次のヘルパー関数によって生成します。

制約

生成関数

使用可能条件

\(f\left( \mathbf{q} \right) = 0\)

penalty()

\(\min_{\mathbf{q}} f\left( \mathbf{q} \right) = 0\)

\(f \left( \mathbf{q} \right) = c\)

equal_to()

\(f \left( \mathbf{q} \right) \le c\)

less_equal()

\(f\left( \mathbf{q} \right) \in \mathbb{N}\) かつ \(f\left( \mathbf{q} \right) \ge 0\)

penalty() はいわゆるペナルティ関数を表す基本的なオブジェクトです。取り得る全ての値に対して多項式 \(f\) が最小値 \(0\) の時に、\(f = 0\) を取るように制約します。

equal_to() は与えられた多項式 \(f\) が値 \(c\) になるように制約します。penalty() と似ていますが、\(f\) の値域に制限はありません。定式化の複雑度の観点から、penalty() 関数でも表現可能な場合には penalty() を使うことを推奨します。

less_equal() は与えられた多項式 \(f\) が値 \(c\) 以下になるように制約します。ただし \(f\) は正の整数値のみを取る多項式である必要があります。

生成された制約条件オブジェクトは、BinaryQuadraticModel 等に与えることで論理模型に変換できるほか、多項式クラスや行列クラスと組み合わせることで、与えられた多項式・行列オブジェクトに対する付加的な制約条件として扱われます。

下記に具体的な制約条件を用いた例を示します。

制約条件の具体例

One-hot 制約

代表的な制約条件として One-hot 制約があげられます。複数のビット変数セットに対し、一つだけ \(1\) になり他は \(0\) になる制約です。

例えば \(n\) 変数のバイナリ多項式について \(\sum_{i = 0}^{n-1} q_i = 1\) の時のみ制約を満たします。

これを制約条件オブジェクトとして構築するには equal_to() を使用します。

from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 4)
f = equal_to(sum_poly(q), 1)
>>> f
q_0 + q_1 + q_2 + q_3 == 1.000000

上記では equal_to(sum_poly(q), 2) にて第一引数を制約対象となる多項式オブジェクトを、第二引数に定数値を設定します。 次のようにして、クライアントを設定し制約条件オブジェクトから論理模型を構築することで、実行結果を確認できます。

from amplify import BinaryQuadraticModel, Solver, decode_solution
from amplify.client import FixstarsClient

client = FixstarsClient()
client.url = "http://xxx.xxx.xxx.xxx"
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000
client.parameters.outputs.duplicate = True  # エネルギー値が同一の解を重複して出力する
client.parameters.outputs.num_outputs = 0

model = BinaryQuadraticModel(f)
solver = Solver(client)
result = solver.solve(model)
>>> for solution in result.solutions:
>>>     values = solution.values
>>>     print(decode_solution(q, values))
[1, 0, 0, 0]
[0, 1, 0, 0]
[0, 0, 1, 0]
[0, 0, 0, 1]

対象となる変数配列 q について、一つだけ \(1\) をとりその他は \(0\) となる解が四通り全て得られました。

等式制約

任意のバイナリ多項式を \(f \left( \mathbf{q} \right) = c\) に制約します。

One-hot 制約と同様に equal_to() を使用します。

from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 4)
f = 3 * q[0] - q[1] - 2 * q[2] + q[3]
g = equal_to(f, 2)
>>> g
3.000000 q_0 - q_1 - 2.000000 q_2 + q_3 == 2.000000

上記では equal_to(f, 2) にて第一引数を制約対象となる多項式オブジェクトを、第二引数に定数値を設定します。 次のようにして、クライアントを設定し制約条件オブジェクトから論理模型を構築することで、実行結果を確認できます。

from amplify import BinaryQuadraticModel, Solver, decode_solution
from amplify.client import FixstarsClient

client = FixstarsClient()
client.url = "http://xxx.xxx.xxx.xxx"
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000
client.parameters.outputs.duplicate = True  # エネルギー値が同一の解を重複して出力する
client.parameters.outputs.num_outputs = 0

model = BinaryQuadraticModel(g)
solver = Solver(client)
result = solver.solve(model)
>>> for solution in result.solutions:
>>>     values = solution.values
>>>     print(decode_solution(q, values))
[1, 1, 0, 0]
[1, 0, 1, 1]

多項式 f について、f = 2 を満たす変数配列 q が得られました。

Note

equal_to() はバイナリ多項式 \(f\) に対して以下のペナルティ関数 \(g\) を生成しています。

\[g = \left(f - c \right)^2\]

この式は \(f = c\) の時のみ \(g = 0\) となり、それ以外の時は \(g > 0\) となります。

不等式制約

正の整数値をとるバイナリ多項式を \(f \left( \mathbf{q} \right) \le c\) に制約するには、less_equal() を用います。

from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import less_equal

q = gen_symbols(BinaryPoly, 4)
f = 4 * q[0] + 3 * q[1] + 2 * q[2] + q[3]
g = less_equal(f, 3)
>>> g
4.000000 q_0 + 3.000000 q_1 + 2.000000 q_2 + q_3 <= 3

上記では less_equal(f, 2) にて第一引数を制約対象となる多項式オブジェクトを、第二引数に定数値を設定します。 次のようにして、クライアントを設定し制約条件オブジェクトから論理模型を構築することで、実行結果を確認できます。

from amplify import BinaryQuadraticModel, Solver, decode_solution
from amplify.client import FixstarsClient

client = FixstarsClient()
client.url = "http://xxx.xxx.xxx.xxx"
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000
client.parameters.outputs.duplicate = True  # エネルギー値が同一の解を重複して出力する
client.parameters.outputs.num_outputs = 0

model = BinaryQuadraticModel(g)
solver = Solver(client)
result = solver.solve(model)
>>> for solution in result.solutions:
>>>     values = solution.values
>>>     print(decode_solution(q, values))
[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 1, 0, 0]

多項式 f について、f <= 3 を満たす変数配列 q が得られました。

論理式による制約

次のような例を考えます。ある2変数 \(q_0, q_1\) について、両方同時に \(1\) にならないような制約を考えます。これは、両方 \(1\) のとき False その他の時 True と考えると、 NAND 演算に相当します。

この例について論理式クラスを用いて制約条件オブジェクトを生成します。論理式クラスについては Logical Expression を参照してください。

次のように NOT AND を表す論理式を構築します。

from amplify import LogicPoly

x = gen_symbols(LogicPoly, 2)
p = ~(x[0] & x[1])
>>> p
- x_0 x_1 + 1

論理式 p をバイナリ多項式に変換します。最適化(最小化)問題としては True\(1\)False\(0\) の関係が逆転しているので、変換前に NOT 演算を行います。

from amplify.constraint import penalty

f = (~p).to_Poly()
g = penalty(f)
>>> g
q_0 q_1 == 0

これにより、True の場合に \(0\)False の場合に \(1\) となる最小化問題に変換できました。このように最適値かつ最小値が \(0\) になるような制約条件は penalty() 関数を用いて制約条件オブジェクトを生成できます。

from amplify import (
    BinaryQuadraticModel,
    decode_solution,
    gen_symbols,
    LogicPoly,
    Solver,
)
from amplify.client import FixstarsClient

client = FixstarsClient()
client.url = "http://xxx.xxx.xxx.xxx"
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000
client.parameters.outputs.duplicate = True
client.parameters.outputs.num_outputs = 0

model = BinaryQuadraticModel(g)
solver = Solver(client)
result = solver.solve(model)

g = penalty(f) にて制約条件オブジェクトを生成し、論理模型を構築することで実行結果を確認できます。

>>> for solution in result.solutions:
>>>     values = solution.values
>>>     print(decode_solution(x, values))
[1, 0]
[0, 1]
[0, 0]

上記のように、NAND 条件を満たす解を全て得ることが出来ました。

制約条件クラスの演算子とメソッド

制約条件を満たすか調べる

制約条件オブジェクトに変数値を与えることで制約条件を満たしているかを返します。変数値は、辞書・リスト・関数オブジェクトとして与えることが出来ますが、制約条件に含まれる変数のインデックス全てに対して解決可能でなければなりません。

from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 4)
f = equal_to(sum_poly(q), 1)
>>> f.is_satisfied({0: 1, 1: 0, 2: 0, 3: 0})
True
>>> f.is_satisfied([0, 1, 0, 0])
True
>>> f.is_satisfied(lambda i: 1 if i == 0 else 0)
True
>>> f.is_satisfied({0: 1, 1: 0, 2: 0, 3: 1})
False
>>> f.is_satisfied([1, 1, 1, 1])
False
>>> f.is_satisfied(lambda i: 0)
False

ペナルティ関数の取得

制約条件オブジェクトの内部表現であるペナルティ関数を取得します。

from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to, less_equal

q = gen_symbols(BinaryPoly, 4)
f1 = equal_to(sum_poly(q), 1)
f2 = less_equal(sum_poly(q), 2)
>>> f1.penalty
2.000000 q_0 q_1 + 2.000000 q_0 q_2 + 2.000000 q_0 q_3 + 2.000000 q_1 q_2 + 2.000000 q_1 q_3 + 2.000000 q_2 q_3 - q_0 - q_1 - q_2 - q_3 + 1.000000

高次多項式を与えた場合や不等式制約など、ペナルティ関数の構築に補助変数が必要な場合はそのままでは取得できません。これは補助変数のインデックスが未確定なためです。

>>> f2.penalty
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: Function to publish ancillary variables is not given

この場合は BinaryQuadraticModel 等に与え論理模型に変換した後で、ペナルティ関数が確認出来ます。ただし論理模型に変換されているため、入力変数のインデックスと論理変数のインデックスの間に変数変換が行われている可能性があることに注意が必要です。

>>> m = BinaryQuadraticModel(f2)
>>> m.input_constraints
[(q_0 + q_1 + q_2 + q_3 <= 2, 1)]
>>> m.input_constraints[0][0].penalty
2.000000 q_0 q_1 + 2.000000 q_0 q_2 + 2.000000 q_0 q_3 - 2.000000 q_0 q_4 - 2.000000 q_0 q_5 + 2.000000 q_1 q_2 + 2.000000 q_1 q_3 - 2.000000 q_1 q_4 - 2.000000 q_1 q_5 + 2.000000 q_2 q_3 - 2.000000 q_2 q_4 - 2.000000 q_2 q_5 - 2.000000 q_3 q_4 - 2.000000 q_3 q_5 + 2.000000 q_4 q_5 + q_0 + q_1 + q_2 + q_3 + q_4 + q_5

制約条件の強さの設定

制約条件オブジェクトは、BinaryQuadraticModel 等の論理模型に与えることを前提としていますが、この際に「強さ」を設定することも出来ます。「強さ」は制約条件オブジェクト単体では実質意味を持ちませんが、論理模型に変換されるときに、多項式オブジェクトや行列クラス、その他の制約条件オブジェクトに対する相対的な強さとして扱われます。

from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 4)
f = 1 * equal_to(sum_poly(q), 1)
>>> f
(q_0 + q_1 + q_2 + q_3 == 1.000000, 1)

強さが設定された制約条件オブジェクトは制約条件と強さのペアで表現されます。強さの係数値は後から変更することも可能です。

>>> f[1] = 2
>>> f
(q_0 + q_1 + q_2 + q_3 == 1.000000, 2)

Note

第ゼロ要素の制約条件オブジェクトは変更できません。

制約条件のコンテナ化

BinaryQuadraticModel 等の論理模型に与える時に、複数の制約条件オブジェクトをまとめ上げることが可能です。

from amplify import BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 4)
f1 = equal_to(q[0] + q[1], 1)
f2 = 2 * equal_to(q[2] + q[3], 1)
g = f1 + f2
>>> g
[(q_0 + q_1 == 1.000000, 1), (q_2 + q_3 == 1.000000, 2)]

強さが設定されている場合もされていない場合も、区別無く加算してコンテナ化することが出来ます。この時、強さが設定されていない制約条件オブジェクトはデフォルト値として 1 が与えられているとします。

下記の様にして制約条件オブジェクトコンテナ全体に強さを乗算・除算することが出来ます。

>>> g *= 2
>>> g
[(q_0 + q_1 == 1.000000, 2), (q_2 + q_3 == 1.000000, 4)]

Note

具体的な制約条件のコンテナ化や強さの設定例については EXAMPLES の 制約の強さの調整 を参照してください。

乗算・除算演算子

制約条件オブジェクトに対する乗算と除算は制約の強さの係数値を変更します。

乗算・除算対象と返却値の関係は次の通りです。

係数型

乗算・除算対象クラス

返却クラス

int

BinaryConstraint BinaryConstraintTerm

BinaryConstraintTerm

BinaryIntConstraint BinaryIntConstraintTerm

BinaryIntConstraintTerm

BinaryConstraints

BinaryConstraints

BinaryIntConstraints

BinaryIntConstraints

float

BinaryConstraint BinaryConstraintTerm

BinaryConstraintTerm

BinaryIntConstraint BinaryIntConstraintTerm

BinaryConstraints

BinaryConstraints

BinaryIntConstraints

加算演算子

制約条件オブジェクトに対する加算は、加算対象によって振る舞いを変えます。対象が多項式オブジェクトや行列オブジェクトの場合には論理模型を構築します。一方、対象が制約条件オブジェクトの場合には制約条件コンテナを構築します。

加算対象と返却値の関係は次の通りです。

制約条件クラス

加算対象クラス

返却クラス

BinaryConstraint BinaryConstraintTerm

BinaryConstraint BinaryConstraintTerm

BinaryConstraints

BinaryIntConstraint BinaryIntConstraintTerm

BinaryPoly

BinaryQuadraticModel

BinaryMatrix

BinaryIntPoly

BinaryIntMatrix

BinaryIntConstraint BinaryIntConstraintTerm

BinaryConstraint BinaryConstraintTerm

BinaryConstraints

BinaryIntConstraint BinaryIntConstraintTerm

BinaryIntConstraints

BinaryPoly

BinaryQuadraticModel

BinaryMatrix

BinaryIntPoly

BinaryIntQuadraticModel

BinaryIntMatrix