Quadratic Model

このセクションでは二次多項式模型 (論理模型) クラスとその周辺関数について説明します。

論理模型オブジェクトの構築

多項式や行列で表される目的関数と、変数間に課せられる制約条件を、二次多項式の「論理模型」として抽象化します。

入力模型クラスと論理模型クラスの対応関係は次の通りです。

論理模型クラス

入力模型クラス

BinaryQuadraticModel

BinaryPoly BinaryMatrix BinaryConstraint BinaryConstraints

BinaryIntPolyBinaryIntMatrix BinaryIntConstraint BinaryIntConstraints

BinaryIntQuadraticModel

BinaryIntPolyBinaryIntMatrix BinaryIntConstraint BinaryIntConstraints

IsingQuadraticModel

IsingPoly IsingMatrix

IsingIntPolyIsingIntMatrix

IsingIntQuadraticModel

IsingIntPoly IsingIntMatrix

論理模型クラスの構築には下記を与えることが可能です。

Note

論理模型の構築方法の具体例については問題の定式化と密接に関係するため EXAMPLES を参照してください。

(高次) 多項式

バイナリ変数またはイジング変数の多項式オブジェクトを論理模型に変換します。三次以上の高次多項式についても扱うことが出来ます。

from amplify import BinaryPoly

f = BinaryPoly({(0, 1, 2): 2, (0, 1): 1, (0): 1, (1): 1, (2): 1}, -1)
model = BinaryQuadraticModel(f)

input_poly プロパティにて入力模型を多項式形式で確認できます。

>>> f
2.000000 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1.000000
>>> model.input_poly
2.000000 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1.000000

行列

行列オブジェクトを論理模型に変換します。

from amplify import BinaryPoly, BinaryQuadraticModel

m = BinaryMatrix(3)
m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
model = BinaryQuadraticModel(m)

input_matrix プロパティにて入力模型を行列形式で確認できます。

>>> m
[[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]]
>>> model.input_matrix
([[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]], 0.0)

制約条件

単体の制約条件

制約条件オブジェクトを論理模型に変換します。

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

q = gen_symbols(BinaryPoly, 4)
c1 = equal_to(sum_poly(q[:3]), 1)   # q_0 + q_1 + q_2 == 1
model = BinaryQuadraticModel(c1)

input_constraints プロパティにて制約条件を確認できます。

>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1)]

複数の制約条件

複数の制約条件オブジェクトを論理模型に変換します。

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

q = gen_symbols(BinaryPoly, 4)
c1 = equal_to(sum_poly(q[:3]), 1)   # q_0 + q_1 + q_2 == 1
c2 = equal_to(sum_poly(q[1:]), 1)   # q_1 + q_2 + q_3 == 1
model = BinaryQuadraticModel(c1 + c2)
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1), (q_1 + q_2 + q_3 == 1.000000, 1)]

多項式と制約条件

多項式に対して制約条件を課すという形で論理模型オブジェクトを構築します。

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

q = gen_symbols(BinaryPoly, 4)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c1 = equal_to(sum_poly(q[:3]), 1)   # q_0 + q_1 + q_2 == 1
c2 = equal_to(sum_poly(q[1:]), 1)   # q_1 + q_2 + q_3 == 1
model = BinaryQuadraticModel(f, c1 + c2)
>>> model.input_poly
2.000000 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1.000000
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1), (q_1 + q_2 + q_3 == 1.000000, 1)]

多項式オブジェクトに制約条件を加算することで、論理模型オブジェクトを生成することも出来ます。詳細は「制約条件クラスの加算演算子」を参照してください。

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

q = gen_symbols(BinaryPoly, 4)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c1 = equal_to(sum_poly(q[:3]), 1)   # q_0 + q_1 + q_2 == 1
c2 = equal_to(sum_poly(q[1:]), 1)   # q_1 + q_2 + q_3 == 1
model = f + c1 + c2
>>> model.input_poly
2.000000 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1.000000
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1), (q_1 + q_2 + q_3 == 1.000000, 1)]

行列と制約条件

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

q = gen_symbols(BinaryPoly, 4)
m = BinaryMatrix(3)
m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
c1 = equal_to(sum_poly(q[:3]), 1)
c2 = equal_to(sum_poly(q[1:]), 1)
model = BinaryQuadraticModel(m, c1 + c2)
>>> model.input_matrix
([[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]], 0.0)
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1), (q_1 + q_2 + q_3 == 1.000000, 1)]

行列に対して制約条件を課す形で論理模型オブジェクトを構築します。

論理模型クラスの演算子

論理模型オブジェクトに対し制約条件オブジェクトや制約条件コンテナを加算すると制約条件が追加されます。詳細は「制約条件クラスの加算演算子」を参照してください。

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

q = gen_symbols(BinaryPoly, 4)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
model = BinaryQuadraticModel(f)
>>> model.input_poly
2.000000 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1.000000
>>> len(model.input_constraints)
0
c1 = equal_to(sum_poly(q[:3]), 1)
c2 = equal_to(sum_poly(q[1:]), 1)
model += c1 + c2
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1), (q_1 + q_2 + q_3 == 1.000000, 1)]

論理模型クラスの内部

論理模型クラスは入力模型オブジェクトに対して、イジングマシンが扱える二次多項式への変換と変数インデックスのマッピングを行います。

ここでは論理模型の内部情報である入力モデルからの変換情報とマッピングの取得方法について記述します。

Note

基本的に Solver クラスを用いる限り論理模型に対する構築後の操作の必要はありません。下記は内部情報に関する記述であり今後インタフェースが変更される可能性があります。

次の表は論理模型クラスの内部表現を返却する読み込み専用プロパティの一覧です。

入力模型

論理式

論理模型

多項式オブジェクト

input_poly

logical_poly

logical_model_poly

行列オブジェクト

input_matrix

logical_matrix

logical_model_matrix

制約条件オブジェクト

input_constraints

input_constraints/penalty

N/A

入力模型はまず論理式に変換されます。論理式は便宜上の呼称で、入力模型から二次多項式への次数下げとインデックスの再割り当てを行った結果を意味します。入力インデックスと論理インデックスの関係は logical_mapping プロパティにて辞書として取得されます。この辞書はキーを入力インデックス、値を論理インデックスとします。

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

q = gen_symbols(BinaryPoly, 4)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
model = BinaryQuadraticModel(f)
>>> model.input_poly
2.000000 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1.000000
>>> model.logical_poly
3.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 + 2.000000 q_3 - 1.000000
>>> model.logical_mapping
{2: 2, 1: 0, 0: 1}

その後論理式と制約条件を加算することで論理模型が構築されます。

c1 = equal_to(sum_poly(q[:3]), 1)
c2 = equal_to(sum_poly(q[1:]), 1)
model += c1 + c2
>>> model.logical_model_poly
5.000000 q_0 q_1 + 6.000000 q_0 q_2 - 2.000000 q_0 q_3 + 2.000000 q_0 q_4 + 4.000000 q_1 q_2 - 2.000000 q_1 q_3 - 2.000000 q_2 q_3 + 2.000000 q_2 q_4 - q_0 - q_2 + 2.000000 q_3 - q_4 + 1.000000

上記は多項式として論理式・論理模型を取得していますが、行列形式でも同様に取得可能です。

論理模型クラスのメソッド

入力変数の数の取得

入力模型に含まれる変数の数を取得します。

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

q = gen_symbols(BinaryPoly, 3)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c = equal_to(sum_poly(q), 1)   # q_0 + q_1 + q_2 == 1
model = BinaryQuadraticModel(f, c)

多項式 f に現れる変数の数が返却されます。

>>> model.num_input_vars
3

論理変数の数の取得

論理模型の内部表現である二次多項式に含まれる変数の数を取得します。

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

q = gen_symbols(BinaryPoly, 3)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c = equal_to(sum_poly(q), 1)   # q_0 + q_1 + q_2 == 1
model = BinaryQuadraticModel(f, c)

必ずしも入力模型の変数の数に一致しないことに注意して下さい。上記の例では、多項式 f は高次多項式なので、補助変数を用いて二次多項式に変換されます。そのため、論理模型の変数の数は、入力模型の変数に加えて必要に応じて補助変数を合わせた数となります。次のようにして論理模型とその変数の数が確認できます。

>>> model.logical_model_poly
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 + 2.000000 q_3 - 1.000000
>>> model.num_logical_vars
4

制約条件オブジェクトの取得

制約条件オブジェクトのコンテナを取得します。

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

q = gen_symbols(BinaryPoly, 3)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c = equal_to(sum_poly(q), 1)   # q_0 + q_1 + q_2 == 1
model = BinaryQuadraticModel(f, c)
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1)]
>>> model.logical_model_poly
4.000000 q_0 q_1 + 4.000000 q_0 q_2 - 2.000000 q_0 q_3 + 4.000000 q_1 q_2 - 2.000000 q_1 q_3 - 2.000000 q_2 q_3 + 2.000000 q_3

強さの係数値については変更が可能です。変更後は論理模型が変化します。

>>> model.input_constraints[0][1] = 2
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 2)]
>>> model.logical_model_poly
6.000000 q_0 q_1 + 6.000000 q_0 q_2 - 2.000000 q_0 q_3 + 6.000000 q_1 q_2 - 2.000000 q_1 q_3 - 2.000000 q_2 q_3 - q_0 - q_1 - q_2 + 2.000000 q_3 + 1.000000

制約条件の充足検査

論理模型に含まれる制約条件オブジェクトについて check_constraints() にて一括で制約を充たすかを検査します。与えることの出来る引数の形式は is_satisfied() と同様です。詳しくは こちら を参照してください。

この関数は得られた出力解について、どの制約条件を満たしているか、またはどの制約条件を満たさなかったのかを調査するために用いられます。またその時の論理模型における制約条件の強さの係数値についても、制約条件オブジェクトの取得 と同様に取得・変更が可能です。

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

q = gen_symbols(BinaryPoly, 3)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c1 = equal_to(q[0] + q[2], 1)  # q_0 + q_2 == 1
c2 = less_equal(q[0] + q[1], 1)  # q_0 + q_1 <= 1
model = f + c1 + c2
checked = model.check_constraints([1, 1, 0])  # q[0] = q[1] = 1, q[2] = 0
>>> checked
[((q_0 + q_2 == 1.000000, 1), True),
 ((q_0 + q_1 <= 1, 1), False)]

出力は制約条件オブジェクトと結果のペアのコンテナで返されます。上記では q = [1, 1, 0] が制約条件を満たすかをチェックし、その結果として q_0 + q_2 == 1 は充たすが q_0 + q_1 <= 1 は充たさないことを意味します。

これを利用すると例えば、制約条件を満たさなかった場合に、その制約条件オブジェクトに対して強さの係数値を変更するという操作が可能です。

for c in checked:
    if c[1] is False:
        c[0][1] *= 2
>>> model.input_constraints
[(q_0 + q_2 == 1.000000, 1),
 (q_0 + q_1 <= 1, 2)]