変数変換と次数下げ#
Amplify SDK では、実数変数や整数変数を含むモデルや、任意の次数の多項式を含むモデルを作成できます。一方で、組み合わせ最適化ソルバーは一般に扱える変数の種類や次数に制限があります。解きたいモデルをソルバーの扱える変数の種類や多項式の次数に合わせるために Amplify SDK の実装している変数変換と次数下げの方法を説明します。
中間モデルの取得#
モデルに対して to_intermediate_model() メソッドを用いると、指定された変数の種類や多項式の次数に合わせて変換された中間モデルが返却されます。このメソッドは solve() 関数の内部で中間モデルの構築時に使用されるため、Amplify SDK がどのように変数変換と次数下げを行っているのかを確認するのに便利です。
注意
通常は to_intermediate_model() メソッドを呼び出す必要はありません。Amplify SDK が solve() 関数の内部でどのように変数変換と次数下げを行っているのかを確認するために使用してください。
中間モデルの持つ変数の種類や多項式の次数は to_intermediate_model() メソッドの第一引数に指定します。ソルバークライアントに合わせたい場合には、次のようにして acceptable_degrees プロパティを与えます。
from amplify import VariableGenerator, Model, FixstarsClient, AcceptableDegrees
gen = VariableGenerator()
q = gen.array("Binary", 3)
model = Model(q[0] * q[1] * q[2])
client = FixstarsClient()
client.parameters.timeout = 1000
im, mapping = model.to_intermediate_model(client.acceptable_degrees)
to_intermediate_model() メソッドは中間モデルと、入力モデルから中間モデルへの変数変換マップを返します。
例えば FixstarsClient は 「中間モデルの構築」で見たように、目的関数としてバイナリ変数の二次多項式を扱うことができます。上記では、入力モデルとしてバイナリ変数の三次多項式を与えていますが、to_intermediate_model() メソッドによって、中間モデルの目的関数はバイナリ変数の二次多項式に変換されています。
>>> print(im)
minimize:
q_0 q_1 + q_0 q_2 - q_0 q'_0 + q_1 q_2 - q_1 q'_0 - q_2 q'_0 + q'_0
注釈
中間モデルに含まれる変数は、入力した変数とは使用している VariableGenerator が異なることに注意してください。つまり、入力モデルの変数と中間モデルに含まれる変数同士を演算することはできません。
to_intermediate_model() メソッドには AcceptableDegrees クラスのインスタンスを与えることで、変換先の変数の種類と次数を自由に指定することもできます。
bq = AcceptableDegrees(objective={"Binary": "Quadratic"})
im, mapping = model.to_intermediate_model(bq)
また、to_intermediate_model() メソッドには変数の種類と次数を指定する他に、変数変換や次数下げのアルゴリズムを指定が可能です。以下では to_intermediate_model() メソッドの結果を見ながら、Amplify に実装されている変数変換と次数下げの方法について説明します。
変数変換#
変数変換は入力モデルに含まれる変数を別の変数の種類に変換する処理です。これにより、ソルバーが扱える変数の種類を持った中間モデルに変換することができます。
現在、次の変数変換が実装されています。
整数変数からバイナリ変数への変換
バイナリ変数からイジング変数への変換とその逆
整数変数からバイナリ変数への変換#
下限が \(l\)、上限が \(u\) の整数変数 \(n\) に対し、いくつかのバイナリ変数 \(q_0, q_1, ..., q_k\) を新しく発行し、\(n\) を多項式
に変換します。このとき、この多項式の取りうる範囲が \(l\) 以上 \(u\) 以下のすべての整数の集合と一致するように整数列 \(a_0, a_1, \ldots, a_k\) を決定します。
変数の数 \(k\) および多項式の係数列 \(a_0, a_1, \ldots, a_k\) を決めるために 4 種類のアルゴリズムが実装されています。
例として、次のように -10 以上 -10 以下の整数を取る整数変数 n を目的関数として持つモデルに対して中間モデルをバイナリ変数で構成する場合に、それぞれのアルゴリズムにおいて整数変数 n がどのようなバイナリ変数の多項式に変換されるかを確認します。
gen = VariableGenerator()
n = gen.scalar("Integer", bounds=(-10, 10)) # 整数変数を発行
model = Model(n)
bq = AcceptableDegrees(objective={"Binary": "Quadratic"})
整数変数からバイナリ変数への変換アルゴリズムは、to_intermediate_model() メソッド及び solve() 関数の integer_encoding_method キーワード引数で指定します。デフォルトは Default です。
Unary変数の数 \(k\) を \(u - l\) とし、\(a_0 = a_1 = \cdots = a_k = 1\) とします。
im, mapping = model.to_intermediate_model(bq, integer_encoding_method="Unary")
>>> print(mapping[n]) q_0 + q_1 + q_2 + q_3 + q_4 + q_5 + q_6 + q_7 + q_8 + q_9 + q_{10} + q_{11} + q_{12} + q_{13} + q_{14} + q_{15} + q_{16} + q_{17} + q_{18} + q_{19} - 10
Linear\((a_0, a_1, a_2, \ldots, a_{k-2}, a_{k-1}, a_k) = (1, 2, 3, \ldots, k-1, m_1, m_2)\) と割り当てます。 \(k\) は \(1 + 2 + 3 + ... + (k - 1) \leq u - l\) となるような最大の整数で、\(m_1\) と \(m_2\) は端数です。
im, mapping = model.to_intermediate_model(bq, integer_encoding_method="Linear")
>>> print(mapping[n]) q_0 + 2 q_1 + 3 q_2 + 4 q_3 + 5 q_4 + 5 q_5 - 10
Binary\((a_0, a_1, a_2, a_3, \ldots, a_{k-1}, a_k) = (1, 2, 4, 8, \ldots, 2^{k-1}, m)\) と割り当てます。 \(k\) は \(1 + 2 + 4 + ... + 2^{k-1} \leq u - l\) となるような最大の整数で、\(m\) は端数です。
im, mapping = model.to_intermediate_model(bq, integer_encoding_method="Binary")
>>> print(mapping[n]) q_0 + 2 q_1 + 4 q_2 + 8 q_3 + 5 q_4 - 10
Default(Default)上記の 3 つのアルゴリズムのうち、使用する変数の数 \(k\) が最も少なくなる方法を採用します。
イジング変数からバイナリ変数への変換#
イジング変数 \(s\) に対し、新しくバイナリ変数 \(q\) を発行し、\(s\) を \(2 q - 1\) に変換します。
gen = VariableGenerator()
s = gen.scalar("Ising")
model = Model(s)
bq = AcceptableDegrees(objective={"Binary": "Quadratic"})
im, mapping = model.to_intermediate_model(bq)
>>> print(mapping[s])
2 q_0 - 1
バイナリ変数からイジング変数への変換#
バイナリ変数 \(q\) に対し、新しくイジング変数 \(s\) を発行し、\(q\) を \((s + 1) / 2\) に変換します。
gen = VariableGenerator()
q = gen.scalar("Binary")
model = Model(q)
iq = AcceptableDegrees(objective={"Ising": "Quadratic"})
im, mapping = model.to_intermediate_model(iq)
>>> print(mapping[q])
0.5 s_0 + 0.5
バイナリ変数多項式の次数下げ#
Amplify SDK は、3 次以上のバイナリ変数多項式を 2 次のバイナリ変数多項式に変換する機能を実装しています。 変数変換と次数下げを両方適用することで、整数変数やイジング変数を含む 3 次以上の多項式もバイナリ変数の 2 次多項式に変換されます。
次数下げのアルゴリズム#
IshikawaKZFD と Substitute の 2 通りのアルゴリズムが実装されています。
次数下げのアルゴリズムは、solve() 関数 及び to_intermediate_model() メソッドの quadratization_method キーワード引数で指定できます。デフォルトは IshikawaKZFD です。
それぞれのアルゴリズムにおいて、次数下げが行われた場合にどのような中間モデルが構築されるかを確認するために、次のような 3 次のバイナリ変数多項式を目的関数として持つモデルを作成しておきます。また、中間モデルは目的関数がバイナリ 2 次で制約条件なしとなるように指定します。
gen = VariableGenerator()
q = gen.array("Binary", 4)
model = Model(q[0] * q[1] * q[2] - q[0] * q[1] * q[3])
bq = AcceptableDegrees(objective={"Binary": "Quadratic"})
IshikawaKZFD(Default)多項式の高次の項ごとに補助変数を発行して、補助変数が最適な値を取る場合に値が変化しないように、高次の項を 2 次多項式に変換します。具体的には 3 次以上の項 \(k q_1 q_2 \cdots q_n\) に対して以下の変換を行います。
項の係数 \(k\) が負の場合、補助変数 \(x\) を 1 つ発行して、項 \(k q_1 q_2 \cdots q_n\) を
\[ kx (q_1 + q_2 + \cdots + q_n + 1 - n) \]に変換します。
項の係数 \(k\) が正で次数 \(n\) が偶数の場合、\((n-2)/2\) 個の補助変数 \(x_1, x_2, \ldots, x_{\left(n-2 \right)/2}\) を発行して、 項 \(k q_1 q_2 \cdots q_n\) を
\[\begin{split} \begin{align*} & k \biggl(\frac{1}{2} S(S-1) - \sum_{i = 1}^{\frac{n-2}{2}} x_i (2 (S - 2i) + 1) \biggr) \\ & \text{where} \quad S = q_1 + q_2 + \cdots + q_n \end{align*} \end{split}\]に変換します。
項の係数 \(k\) が正で次数 \(n\) が奇数の場合、\((n-1)/2\) 個の補助変数 \(x_1, x_2, \ldots, x_{\left(n-1\right)/2}\) を発行して、 項 \(k q_1 q_2 \cdots q_n\) を
\[\begin{split} \begin{align*} & k \biggl(\frac{1}{2} S(S-1) - \sum_{i = 1}^{\frac{n-1}{2}} x_i (2 (S - 2i) + 1) + x_{\frac{n-1}{2}} (2 (S - n + 1) + 1)\biggr) \\ & \text{where} \quad S = q_1 + q_2 + \cdots + q_n \end{align*} \end{split}\]に変換します。
im, mapping = model.to_intermediate_model( bq, quadratization_method="IshikawaKZFD" )
>>> print(im) minimize: q_0 q_1 + q_0 q_2 - q_0 q'_0 - q_0 q'_1 + q_1 q_2 - q_1 q'_0 - q_1 q'_1 - q_2 q'_0 - q_3 q'_1 + q'_0 + 2 q'_1
ここで、
q'_0とq'_1は各項それぞれで発行された補助変数です。注意
IshikawaKZFDアルゴリズムでは、制約条件式を次数下げすることはできません。 3 次の制約条件式を持つ制約条件を 2 次の制約条件式を受け取れるソルバーに渡したい場合は、下記のSubstituteアルゴリズムを使用してください。
Substitute3次以上のバイナリ変数の積に現れる 2 つのバイナリ変数の積 \(q_a q_b\) に対して、補助変数 \(x\) を発行し、多項式の各項に含まれる \(q_a q_b\) をすべて \(x\) に置換します。このとき中間モデルには以下の制約条件が追加されます。
\[\begin{split} \begin{align*} \text{subject to:} \quad & q_a q_b = x \\ \text{penalty function:} \quad & q_a q_b - 2 q_a x - 2 q_b x + 3 x \end{align*} \end{split}\]以上の操作を多項式が 2 次になるまで繰り返します。
im, mapping = model.to_intermediate_model( bq, quadratization_method="Substitute" )
>>> print(im) minimize: q_2 q'_0 - q_3 q'_0 subject to: q_0 q_1 - q'_0 == 0 (weight: 2)
上記では、
q_0 q_1が補助変数q'_0で置き換えられたことがわかります。次数下げで追加される制約条件のペナルティ関数の重みは、置換が発生した項の係数の絶対値の和を初期値として設定されます。これは目的関数に対して十分に大きな値を重みに与える必要があるためです。 この重みの初期値は時に大きすぎる場合があるため、
substitution_multiplierキーワード引数で重みの初期値に対する係数を指定することができます。im, mapping = model.to_intermediate_model(bq, quadratization_method="Substitute", substitution_multiplier=0.5 )
>>> print(im) minimize: q_2 q'_0 - q_3 q'_0 subject to: q_0 q_1 - q'_0 == 0 (weight: 1)
注釈
制約条件の重みの調整に関しては「ペナルティ関数の重み」を参照してください。
Tip
次数下げの各アルゴリズムには次のような特徴があります。どのアルゴリズムを使用するかでモデルによっては中間モデルの変数の数が大きく変わることがあり、ソルバーの実行可否や結果に影響が現れることがあります。
アルゴリズム |
長所 |
短所 |
|---|---|---|
補助変数の数が高次の項の次数の多くとも半分の数で済む (係数が負なら 1 つ) |
補助変数の数が高次の項の数に比例するため、多くの補助変数が必要になることがある |
|
項をまたいだ置換が有効に働く場合、補助変数の数を少なく出来ることがある |
チューニングのために制約条件のペナルティ関数の重みの調整が必要なことがある |
ソルバーの実行結果と中間モデル#
solve() 関数の実行結果から、中間モデルと中間モデルに対する求解結果の情報を取得することもできます。この情報は、Result クラスの intermediate アトリビュート (ModelConversion クラス) から取得できます。
ModelConversion クラスは以下のアトリビュートを持ちます。
アトリビュート |
データ型 |
詳細 |
|---|---|---|
中間モデル |
||
入力モデルの変数から中間モデルの変数への変数変換マップ |
||
中間モデルの目的関数と制約条件 (ペナルティ関数が生成された場合はそれを含む) で使用されている変数の数 |
||
中間モデルの求解結果 |
例として、目的関数に整数変数を持つ次のモデルに対して FixstarsClient を用いて solve() を実行します。
from amplify import VariableGenerator, Model, FixstarsClient, solve
gen = VariableGenerator()
n = gen.scalar("Integer", bounds=(1, 3)) # 整数変数を発行
model = Model(n)
client = FixstarsClient()
client.parameters.timeout = 1000
result = solve(model, client)
実行結果の intermediate アトリビュートから中間モデルに関する情報が取得できます。
>>> print(result.intermediate.model)
minimize:
q_0 + q_1 + 1
整数変数 n がどのように変数変換されたかは、次のように mapping で確認できます。
>>> print(result.intermediate.mapping[n])
q_0 + q_1 + 1
中間モデルの解は values_list で確認できます。values_list には複数の解が含まれていることがあるので、ここでは最初の解を取得します。
>>> result.intermediate.values_list[0]
Values({Poly(q_0): 0, Poly(q_1): 0})
入力モデルの解は、中間モデルの解に対して mapping を用いた変換を行って得られるものとなります。 少し複雑ですが、次のようにして全ての中間モデルの解を入力モデルの解に変換できます。
>>> im = result.intermediate
>>> {
... var: im_mapped.evaluate(im_values)
... for im_values in im.values_list
... for var, im_mapped in im.mapping.items()
... }
{Poly(n_0): 1.0}