4. 制約条件の構築¶

制約条件 とは、組合せ最適化問題において決定変数の値がみたすべき条件のことです。Amplify SDK では、各変数がとりうる範囲の制約と、多項式がとりうる範囲に関する制約をそれぞれ設定することができます。

このページでは、決定変数への制約の設定方法と、多項式を用いた制約条件オブジェクトの構築を説明します。

4.1. 変数の値を固定する¶

定式化において一部の決定変数の値が事前に決まっている場合など、決定変数の値を固定しておきたいことがあります。以下のように事前に変数配列の一部を数値で置き換えることで、実質的に変数の値を固定することができます。

from amplify import VariableGenerator

gen = VariableGenerator()
q = gen.array("Binary", shape=(3, 3))

q[0, :] = 0
q[:, 0] = 0
q[0, 0] = 1

Alternative

上記の q に数値を代入する部分は以下のように書いても同じ効果があります。ただし、上記の書き方のほうが一般に高速です。

for i in range(3):
    q[i, 0] = 0
for j in range(3):
    q[0, j] = 0
q[0, 0] = 1

>>> print(q)
[[      1,       0,       0],
 [      0, q_{1,1}, q_{1,2}],
 [      0, q_{2,1}, q_{2,2}]]

その後、q を用いて多項式を組み立てることで、固定された変数の値を含む多項式を作成できます。

>>> p = q.sum()
>>> print(p)
q_{1,1} + q_{1,2} + q_{2,1} + q_{2,2} + 1

ある変数が別の変数を用いた多項式で表されるという制約も、変数配列を多項式で置き換えることで実現できます。たとえば、\(q_{1, 1} = q_{2, 2}\) という制約を表現したい場合、以下のようにします。

>>> q[2, 2] = q[1, 1]
>>> print(q)
[[      1,       0,       0],
 [      0, q_{1,1}, q_{1,2}],
 [      0, q_{2,1}, q_{1,1}]]

Tip

書き換え前の変数配列 q を再利用する場合はコピーしておくと良いでしょう。

gen = VariableGenerator()
q_org = gen.array("Binary", shape=(3, 3))
q = q_org.copy()

q[0, :] = 0
q[:, 0] = 0
q[0, 0] = 1

>>> print(q_org)
[[q_{0,0}, q_{0,1}, q_{0,2}],
 [q_{1,0}, q_{1,1}, q_{1,2}],
 [q_{2,0}, q_{2,1}, q_{2,2}]]

4.2. 変数の値の範囲を設定する¶

整数変数と実数変数では、変数の値の取りうる範囲を float または None で設定できます。None が指定された場合、非有界であることを表します。

変数を発行する際にまとめて範囲を設定するには、scalar(), array(), matrix() の各メソッドの bounds パラメータに変数の値の取りうる範囲を設定します。

>>> n = gen.array("Integer", shape=(5,), bounds=(1, 3))
>>> print(n[0].as_variable())
{name: n_0, id: 9, type: Integer, lower_bound: 1, upper_bound: 3}

個別の変数に範囲を指定する場合は、lower_bound, upper_bound アトリビュートに指定します。

>>> n[0].lower_bound = 0
>>> n[0].upper_bound = None
>>> print(n[0].as_variable())
{name: n_0, id: 9, type: Integer, lower_bound: 0, upper_bound: inf}

4.3. 多項式の値を制約する¶

Amplify SDK では多項式の値がとりうる範囲の制約を表す等式・不等式などを Constraint クラスの制約条件オブジェクトとして管理します。制約条件オブジェクトを利用することで、マシンやソルバーの実行結果から制約条件を満たす解を抽出したり、制約条件を満たさない場合にはどの制約条件が守れなかったのかを判定できます。

また、制約条件オブジェクトは、 QUBO ソルバーのような制約条件を直接扱えないソルバー向けに、ペナルティ関数を生成する機能も備えています。ペナルティ関数とは、制約条件を持つ組合せ最適化問題をペナルティ法という方法を用いて制約条件のない問題に変換するときに、それぞれの制約条件に対して計算される多項式のことです。

制約条件の構築には制約条件の種類ごとに提供されるヘルパー関数を用いると便利です。自動で制約条件式を解析し、最適化されたペナルティ関数が生成されます。

注釈

ペナルティ関数の生成が必要ない場合についても、ヘルパー関数を使うことによるデメリットはありませんので、ヘルパー関数をお使いください。

参考

生成されるペナルティ関数の詳細や重みの調整に関しては「制約条件とペナルティ関数」を参照してください。また、ヘルパー関数を使わずに自身でペナルティ関数を指定する方法は「ペナルティ関数の指定」を参照してください。

4.3.1. 等式制約¶

等式を表す制約条件オブジェクトの作成には、次のヘルパー関数が利用できます。

ヘルパー関数	効果
`equal_to()`	多項式が右辺と等しいことを制約する
`one_hot()`	多項式が 1 と等しいことを制約する

与えられた多項式を等式で制約するには、equal_to() 関数を用います。次の例では、二次元の変数配列 \(q\) に対して、\(q_{0,0} + q_{1,1} + q_{2,2} = 1\) を満たすような制約条件オブジェクトを作成しています。

from amplify import VariableGenerator, equal_to, one_hot

gen = VariableGenerator()
q = gen.array("Binary", shape=(3, 3))
c = equal_to(q[0, 0] + q[1, 1] + q[2, 2], 1)

>>> print(c)
q_{0,0} + q_{1,1} + q_{2,2} == 1 (weight: 1)

制約条件にはラベルを付けることができます。ラベルを付けておくと後に制約条件の評価結果を確認する際の識別に役立ちます。後から変更することも可能です。

>>> c = equal_to(q[0, 0] + q[1, 1] + q[2, 2], 1, label="diagonal sum")
>>> print(c)
diagonal sum: q_{0,0} + q_{1,1} + q_{2,2} == 1 (weight: 1)
>>> c.label = "diagonal sum (I should give a long name to this!)"
>>> print(c)
diagonal sum (I should give a long name to this!): q_{0,0} + q_{1,1} + q_{2,2} == 1 (weight: 1)

ヘルパー関数に多項式配列 PolyArray を渡すことで、配列要素の和が制約されます。

>>> c = equal_to(q[0], 1, label="1st row sum")
>>> print(c)
1st row sum: q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 1)

これは以下と等価です。

c = equal_to(q[0].sum(), 1, label="1st row sum")

one_hot() 関数は右辺が 1 の等式制約を作成します。それ以外は equal_to() 関数と同じです。

>>> c = one_hot(q[0], label="1st row one-hot")
>>> print(c)
1st row one-hot: q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 1)

これは以下と等価です。

c = equal_to(q[0], 1, label="1st row one-hot")

注釈

実数変数や実数係数を含む多項式に対する等式制約は数値誤差の影響を受け、充足判定を誤る可能性があります。

特に、QUBO ソルバーなど実数変数を扱えないソルバーでは、実数変数を少数のバイナリ変数に変換するために、本質的に正しく等式制約を表現できないことがあります (実数変数からバイナリ変数への変換については「実数変数からバイナリ変数への変換」を参照してください)。

このような場合、等式制約の代わりに、許容できる誤差を与えて不等式制約で表現することを検討してください。

4.3.2. 不等式制約¶

不等式を表す制約条件オブジェクトの作成には、次のヘルパー関数が利用できます。

ヘルパー関数	効果
`less_equal()`	多項式が右辺より小さいか等しいことを制約する
`greater_equal()`	多項式が右辺より大きいか等しいことを制約する
`clamp()`	多項式が範囲に含まれることを制約する

less_equal() と greater_equal() は equal_to() と同様に、第一引数には多項式または多項式配列を与え、第二引数には右辺を与えます。

from amplify import less_equal, greater_equal

c_le = less_equal(q[0], 2)
c_ge = greater_equal(q[0], 2)

>>> print(c_le)
q_{0,0} + q_{0,1} + q_{0,2} <= 2 (weight: 1)
>>> print(c_ge)
q_{0,0} + q_{0,1} + q_{0,2} >= 2 (weight: 1)

clamp() は多項式が範囲に含まれることを制約します。範囲は tuple で指定します。

from amplify import clamp

c_bw = clamp(q[0], (1, 2))

>>> print(c_bw)
1 <= q_{0,0} + q_{0,1} + q_{0,2} <= 2 (weight: 1)

範囲の下限と上限が等しい場合は等式制約として扱われます。

>>> c_bw = clamp(q[0], (2, 2))
>>> print(c_bw)
q_{0,0} + q_{0,1} + q_{0,2} == 2 (weight: 1)

これは以下と等価です。

c_bw = equal_to(q[0], 2)

下限または上限が None の場合はそれぞれ less_equal() と greater_equal() と等価です。

>>> c_le = clamp(q[0], (None, 2))
>>> print(c_le)
q_{0,0} + q_{0,1} + q_{0,2} <= 2 (weight: 1)

>>> c_ge = clamp(q[0], (2, None))
>>> print(c_ge)
q_{0,0} + q_{0,1} + q_{0,2} >= 2 (weight: 1)

注意

QUBO ソルバーにおける不等式制約のペナルティ関数の生成には補助変数が必要となるため、非効率なことや厳密な定式化が出来ないことがあります。詳細は「制約条件とペナルティ関数 - 不等式制約」を参照してください。

4.3.3. 制約条件リスト¶

複数の制約条件を扱いたい場合、制約条件リスト ConstraintList を用います。制約条件オブジェクト Constraint 同士を加算することで、制約条件リストにすることができます。

from amplify import VariableGenerator, equal_to

gen = VariableGenerator()
q = gen.array("Binary", shape=(3, 3))

>>> c0 = equal_to(q[0], 1)
>>> c1 = equal_to(q[1], 1)
>>> clist = c0 + c1
>>> print(clist)
[q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 1),
 q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 1)]

また、ConstraintList を作成した後に、+ または += 演算子で制約条件オブジェクトを追加することもできます。

>>> clist += equal_to(q[2], 1)
>>> print(clist)
[q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 1),
 q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 1),
 q_{2,0} + q_{2,1} + q_{2,2} == 1 (weight: 1)]

多項式の配列に対して、複数の制約条件オブジェクトを一気に作成することもできます。ヘルパー関数に axis パラメータを与えると、多項式配列の軸に沿った和が計算され、各計算結果に対して制約条件オブジェクトを作成します。

次の例は各行の和がそれぞれ 1 であるような制約条件リスト ConstraintList を作成しています。ラベルが指定された場合、指定された文字列の後ろに自動で数字がつきます。

>>> clist = equal_to(q, 1, axis=1, label="row sum")
>>> print(clist)
[row sum0: q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 1),
 row sum1: q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 1),
 row sum2: q_{2,0} + q_{2,1} + q_{2,2} == 1 (weight: 1)]

ヒント

可能な限り axis パラメータを用いた制約条件の一括作成を行うと効率的です。

4.3.4. 制約条件の重みを設定する¶

equal_to() 関数や less_equal() 関数などを用いて作成した制約条件オブジェクト Constraint には、重みを設定することができます。これは主に QUBO ソルバーまたはイジングソルバーで有効なパラメータで、重みが強ければ強いほど制約条件を満たす解が見つかりやすくなります。ただし、制約条件の重みが強すぎる場合、目的関数の値が小さな解を見つけにくくなる傾向があります。

参考

制約条件の重みの設定は、ペナルティ関数を用いて制約条件を表現するソルバーを用いる場合に必要です。ペナルティ関数と重みの調整方法に関してはペナルティ関数の重みを参照してください。

制約条件の重みは、weight プロパティにより取得・設定できます。デフォルト値は 1 です。

from amplify import VariableGenerator, equal_to

gen = VariableGenerator()
q = gen.array("Binary", shape=(3, 3))
c = equal_to(q[0, 0] + q[1, 1] + q[2, 2], 1)

>>> c.weight
1.0
>>> c.weight = 3
>>> c.weight
3.0

制約条件オブジェクトに数値を掛けると、weight に乗算されます。

>>> c.weight
3.0
>>> c *= 2
>>> c.weight
6.0

制約条件リスト ConstraintList オブジェクトに対しても数値との乗算が定義されています。

c1 = equal_to(q[0], 1)
c2 = equal_to(q[1], 1)
clist = c1 + c2

>>> print(clist)
[q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 1),
 q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 1)]
>>> clist *= 2
>>> print(clist)
[q_{0,0} + q_{0,1} + q_{0,2} == 1 (weight: 2),
 q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 2)]

4.3.5. ドメインウォール制約¶

Amplify SDK では一部の特殊な制約条件の作成をヘルパー関数でサポートしています。

注釈

多くの場合、定式化には上記で解説した等式・不等式制約を作成する機能を使用すれば十分です。以下で解説する機能は、特殊な制約条件の定式化が必要な人が利用してください。

ドメインウォール制約は、一次元のバイナリ変数またはイジング変数の変数配列に対して、左から 0 (イジング変数の場合は -1) が 0 個以上続いたあと 1 が 0 個以上続くように制約します。例えば、バイナリ変数配列 q = [q_0, q_1, q_2, q_3] に対して、q = [0, 0, 0, 0] や q = [0, 1, 1, 1] は制約を満たしますが、q = [0, 1, 1, 0] は制約を満たしません。

ドメインウォール制約を作成するには、domain_wall() 関数に変数配列を渡します。

from amplify import domain_wall

gen = VariableGenerator()
q = gen.array("Binary", 4)
dw = domain_wall(q)

変数配列がバイナリ変数の場合、ドメインウォール制約の制約条件式は、

\[\sum_{i=0}^{n-2} q_i - q_i q_{i+1} = 0\]

となります。これは、隣り合う変数の間で \(1 \rightarrow 0\) と変化する変数の個数が 0 となる制約と解釈できるからです。プログラムコード上では以下のようにして確認できます。

>>> print(dw)
- q_0 q_1 - q_1 q_2 - q_2 q_3 + q_0 + q_1 + q_2 == 0 (weight: 1)

注釈

ドメインウォール制約の制約条件式は等式で表されますが、equal_to() 関数にこの制約条件式の両辺を与えて構築される制約条件と domain_wall() 関数を用いて構築される制約条件は等価ではありません。これは、制約条件が生成するペナルティ関数が異なるためであり、domain_wall() 関数を用いて構築された制約条件の方が効率的です。ペナルティ関数の詳細については、制約条件とペナルティ関数を参照してください。

イジング変数配列の場合、隣り合う変数の間で \(+1 \rightarrow -1\) と変化する変数の個数が 0 となる制約が生成されます。

gen = VariableGenerator()
s = gen.array("Ising", 4)
dw = domain_wall(s)

制約条件式は、

\[\frac{1}{4} \sum_{i=0}^{n-2} s_i - s_{i + 1} - s_i s_{i+1} = 0\]

となります。これは次の通り確認されます。

>>> print(dw)
- 0.25 s_0 s_1 - 0.25 s_1 s_2 - 0.25 s_2 s_3 + 0.25 s_0 - 0.25 s_3 + 0.75 == 0 (weight: 1)

Tip

値の変化の方向を逆にするには domain_wall() 関数の ascending パラメータに False を設定します。この場合は、バイナリ変数配列 q = [q_0, q_1, q_2, q_3] に対して、q = [0, 0, 0, 0] や q = [1, 1, 1, 0] は制約を満たしますが、q = [0, 0, 1, 1] は制約を満たさないことになります。