変数変換と次数下げ

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-1}\) を新しく発行し、\(n\) を多項式

\[ a_0 q_0 + a_1 q_1 + \cdots + a_{k-1} q_{k-1} + l \]

に変換します。このとき、この多項式の取りうる範囲が \(l\) 以上 \(u\) 以下のすべての整数の集合と一致するように整数列 \(a_0, a_1, \ldots, a_{k-1}\) を決定します。

変数の数 \(k\) および多項式の係数列 \(a_0, a_1, \ldots, a_{k-1}\) を決めるために 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} = 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, k, m)\) と割り当てます。 \(k\) は \(1 + 2 + 3 + \cdots + k \leq u - l\) となるような最大の整数で、\(m\) は端数です。

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 + \cdots + 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\) が最も少なくなる方法を採用します。

注釈

Linear と Binary において、 端数 \(m\), \(m_1\), \(m_2\) が \(0\) になる場合は対応する補助変数の発行は省略されます。

実数変数からバイナリ変数への変換

下限が \(l\)、上限が \(u\) の実数変数 \(x\) に対し、いくつかのバイナリ変数 \(q_0, q_1, ..., q_{k-1}\) を新しく発行し、\(x\) を多項式

\[ a_0 q_0 + a_1 q_1 + \cdots + a_{k-1} q_{k-1} + l \]

に変換して表現します。このとき、係数列 \(a_0, a_1, \ldots, a_{k-1}\) は \(a_0 + a_1 + \cdots a_{k-1} = u - l\) を満たす正の実数列で構成されます。

多項式の係数列 \(a_0, a_1, \ldots, a_{k-1}\) を決めるために、いくつかのアルゴリズムが実装されています。

例として、次のように -10 以上 10 以下の実数を取る実数変数 x を目的関数として持つモデルをバイナリ変数で構成する場合に、実数変数 x がどのようなバイナリ変数の多項式に変換されるかを確認します。

gen = VariableGenerator()
x = gen.scalar("Real", bounds=(-10, 10))

model = Model(x)

bq = AcceptableDegrees(objective={"Binary": "Quadratic"})

実数変数からバイナリ変数への変換アルゴリズムは、to_intermediate_model() メソッド及び solve() 関数の real_encoding_method キーワード引数に指定します。デフォルトは Random16 です。

Random

\((a_0, a_1, a_2, a_3, \ldots, a_{k-1})\) を一様乱数で与えます。 バイナリ変数の数 \(k\) は変換アルゴリズムの末尾の数字によって (4, 8, 16, 32) のうちいずれかを設定します。以下は \(k = 16\) の場合の例です。

amplify.set_seed(0)
im, mapping = model.to_intermediate_model(bq, real_encoding_method="Random16")

>>> print(mapping[x])
1.99333941505556 q_0 + 1.05184485013684 q_1 + 1.18505654902564 q_2 + 1.49764241671521 q_3 + 1.76252706549575 q_4 + 0.841695701394766 q_5 + 0.21960146400976 q_6 + 0.635503335788004 q_7 + 1.80253453941945 q_8 + 0.173438994097798 q_9 + 2.04763527252344 q_{10} + 0.611762636976138 q_{11} + 1.95487069012893 q_{12} + 1.62228108547751 q_{13} + 1.9691590736731 q_{14} + 0.631106910082103 q_{15} - 10

注釈

set_seed() 関数で変数変換に利用する乱数のシードを固定できます。

注釈

Poly では数式処理の数値誤差への対処として、係数が 1e-10 を下回る項は無視されます。
そのため、上限と下限の差 \(u - l\) が非常に小さい場合において、変換されたバイナリ変数の項のうちいくつかが消失する可能性があります。

イジング変数からバイナリ変数への変換

イジング変数 \(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 次 (または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[2] * q[3] - q[1] * q[2] * q[3])

bq = AcceptableDegrees(objective={"Binary": "Quadratic"})

IshikawaKZFD (Default)

多項式の高次の項ごとに補助変数を発行して、補助変数が最適な値を取る場合に値が変化しないように、高次の項の次数を下げます。

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 \left(\frac{1}{2} S\left(S-1\right) - \sum_{i = 1}^{\frac{n-2}{2}} x_i \left(2 \left(S - 2i\right) + 1\right) \right) \\ & \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 \left(\frac{1}{2} S\left(S-1\right) - \sum_{i = 1}^{\frac{n-1}{2} - 1} x_i \left(2 \left(S - 2i\right) + 1\right) - x_{\frac{n-1}{2}} \left(S - n + 2\right) \right) \\ & \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_2 + q_0 q_3 - q_0 q'_0 - q_1 q'_1 + q_2 q_3 
    - q_2 q'_0 - q_2 q'_1 - q_3 q'_0 - q_3 q'_1 + q'_0 + 2 q'_1

ここで、q'_0 と q'_1 は各項それぞれで発行された補助変数です。

注意

IshikawaKZFD アルゴリズムでは、制約条件式を次数下げすることはできません。 3 次の制約条件式を持つ制約条件を 2 次の制約条件式を受け取れるソルバーに渡したい場合は Substitute アルゴリズムを使用してください。

イジング変数の場合

3 次以上のイジング変数の項 \(k s_1 s_2 \cdots s_n\) に対して以下の変換を行います。

• 項の係数 \(k\) が正で次数 \(n\) が奇数の場合、または項の係数 \(k\) が負で次数 \(n\) が偶数の場合:
  \(\mathrm{floor} \left( n / 2 \right)\) 個の補助変数 \(x_1, x_2, \ldots, x_{\mathrm{floor} \left( n / 2 \right)}\) を発行して、 項 \(k s_1 s_2 \cdots s_n\) を

  \[\begin{split} \begin{align*} & \left| k \right| \left( 2 S^2 - 8 \sum_{i = 1}^{\mathrm{floor} \left( n / 2 \right)}{ \left( \frac{x_i + 1}{2} \right) \left( S - 2 i + 1 \right) } - 1 \right) \\ & \text{where} \quad S = \sum_{i =1}^{n}{\frac{s_i + 1}{2}} \end{align*} \end{split}\]

  に変換します。

• 項の係数 \(k\) が正で次数 \(n\) が偶数の場合、または項の係数 \(k\) が負で次数 \(n\) が奇数の場合:
  \(\mathrm{floor} \left( \left(n-1\right) / 2 \right)\) 個の補助変数 \(x_1, x_2, \ldots, x_{\mathrm{floor} \left( \left(n-1\right) / 2 \right)}\) を発行して、 項 \(k s_1 s_2 \cdots s_n\) を

  \[\begin{split} \begin{align*} & \left| k \right| \left( 2 \left(S-1\right)^2 - 8 \sum_{i = 1}^{\mathrm{floor} \left( \left(n-1\right) / 2 \right)}{ \left( \frac{x_i + 1}{2} \right) \left( S - 2 i \right) } - 1 \right) \\ & \text{where} \quad S = \sum_{i =1}^{n}{\frac{s_i + 1}{2}} \end{align*} \end{split}\]

  に変換します。

Substitute

3次以上のバイナリ変数の積に現れる 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_0 q'_0 - q_1 q'_0
subject to:
  q_2 q_3 - 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_0 q'_0 - q_1 q'_0
subject to:
  q_2 q_3 - q'_0 == 0 (weight: 1)

注釈

制約条件の重みの調整に関しては「ペナルティ関数の重み」を参照してください。

Tip

次数下げの各アルゴリズムには次のような特徴があります。どのアルゴリズムを使用するかでモデルによっては中間モデルの変数の数が大きく変わることがあり、ソルバーの実行可否や結果に影響が現れることがあります。

アルゴリズム	長所	短所
IshikawaKZFD	補助変数の数が高次の項の次数の多くとも半分の数で済む (係数が負なら 1 つ)	補助変数の数が高次の項の数に比例するため、多くの補助変数が必要になることがある
Substitute	項をまたいだ置換が有効に働く場合、補助変数の数を少なく出来ることがある	チューニングのために制約条件のペナルティ関数の重みの調整が必要なことがある

ソルバーの実行結果と中間モデル

solve() 関数の実行結果から、中間モデルと中間モデルに対する求解結果の情報を取得することもできます。この情報は、Result クラスの intermediate アトリビュート (ModelConversion クラス) から取得できます。

ModelConversion クラスは以下のアトリビュートを持ちます。

アトリビュート	データ型	詳細
model	Model	中間モデル
mapping	IntermediateMapping	入力モデルの変数から中間モデルの変数への変数変換マップ
num_variables	int	中間モデルの目的関数と制約条件 (ペナルティ関数が生成された場合はそれを含む) で使用されている変数の数
values_list	ValuesList	中間モデルの求解結果

例として、目的関数に整数変数を持つ次のモデルに対して 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}

これは solve() の出力結果である solutions と一致することが確認できます。