Quadratic Model

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

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

イジングマシンへの入力として、多変数多項式や行列・制約条件をイジングマシンが取り扱うことが可能な「論理模型」として抽象化します。

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

Note

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

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

論理模型クラス

入力模型クラス

BinaryQuadraticModel

BinaryPoly BinaryMatrix BinaryConstraint BinaryConstraints

BinaryIntPolyBinaryIntMatrix BinaryIntConstraint BinaryIntConstraints

BinaryIntQuadraticModel

BinaryIntPolyBinaryIntMatrix BinaryIntConstraint BinaryIntConstraints

IsingQuadraticModel

IsingPoly IsingMatrix

IsingIntPolyIsingIntMatrix

IsingIntQuadraticModel

IsingIntPoly IsingIntMatrix

多変数多項式

二値多変数多項式オブジェクトを論理模型に変換します。三次以上の多項式についても扱うことが出来ます。

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_poly プロパティにて入力模型を行列形式で確認できます。

>>> 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.num_logical_vars
4
>>> 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

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

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

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