モデルの変換

Amplify SDK では、実数変数や整数変数を含むモデルや、任意の次数の多項式を含むモデルを作成できます。一方で、組み合わせ最適化ソルバーは一般に扱える変数の種類や次数、制約条件の種類や入力の可否に制限があり、また、特定の構造を持った二次の多項式しか受け取れない場合もあります。

Amplify SDK は、 solve() 関数にソルバーが直接扱えないモデルを入力されたときに、ソルバーが扱える形への変換処理を可能な限り自動で行います。具体的には、変数変換や次数下げなどモデルを変換する処理と、グラフ埋め込みと呼ばれる 2 次の多項式をソルバーが受け取れる形に変換する処理が行われ、その後ソルバーの実行が行われます。

変換処理の概要

まず、Amplify SDK はソルバーが対応できる変数の種類や目的関数・制約条件の次数に応じて変数変換や次数下げを行います。変数変換や次数下げを行ったあとのモデルを中間モデル (Intermediate Model) とよびます。中間モデルがソルバーに入力できる形になっているならば、ソルバーに中間モデルを求解させます。ソルバーから返ってきた解に対して、入力モデルに行った変数変換の逆変換を行い、入力モデルの解を計算します。

_images/conversion_intermediate_light.drawio.svg _images/conversion_intermediate_dark.drawio.svg

ソルバーの種類によっては、中間モデルをそのままソルバーに入力できない場合があります。変数の種類と次数の制限以外に、与えられる 2 次の項の制限があるためです。この場合、Amplify SDK はさらにグラフ埋め込み とよばれる操作を行い、中間モデルをソルバーに入力できる形式に変換します。ソルバーから返ってきた解に対して、中間モデルに行ったグラフ埋め込みの逆変換をかけることで中間モデルの解が計算できます。さらに中間モデルの解に対して、入力モデルに行った変数変換の逆変換をかけることで、入力モデルの解となります。

_images/conversion_embedding_light.drawio.svg _images/conversion_embedding_dark.drawio.svg

中間モデルの構築

変換処理の準備として、ソルバークライアントから次の情報を取得してソルバーの扱える問題の種類を取得し、出力する中間モデルの持つ目的関数と制約条件の次数を決定します。

  • 目的関数として扱える変数の種類とそれぞれの次数

  • 等式制約として扱える変数の種類とそれぞれの次数

  • 不等式制約として扱える変数の種類とそれぞれの次数

ソルバーの扱える最大の次数は変数の種類ごとに与えられます。以下は FixstarsClient の例です。

from amplify import FixstarsClient

client = FixstarsClient()

>>> client.acceptable_degrees.objective  # 目的関数の次数
{VariableType.Binary: Degree.Quadratic, VariableType.Ising: Degree.Zero, VariableType.Integer: Degree.Zero, VariableType.Real: Degree.Zero}
>>> client.acceptable_degrees.equality_constraints # 等式制約の次数
{VariableType.Binary: Degree.Zero, VariableType.Ising: Degree.Zero, VariableType.Integer: Degree.Zero, VariableType.Real: Degree.Zero}
>>> client.acceptable_degrees.inequality_constraints # 不等式制約の次数
{VariableType.Binary: Degree.Zero, VariableType.Ising: Degree.Zero, VariableType.Integer: Degree.Zero, VariableType.Real: Degree.Zero}

FixstarsClient では、目的関数はバイナリ変数の2次までで、等式制約と不等式制約は直接扱えないことがわかります。

注釈

扱える次数はクライアントごとに異なりソルバークライアントの設定によっても変化します。詳しくは クライアントの詳細 を参照してください。

その後、Amplify SDK は次のようにして中間モデルへの変換を行います。

中間モデル構築の処理手順

  1. 変数変換と次数下げを行うことで、目的関数をソルバーが扱える形に変換可能か確認する

  2. 変数変換と次数下げを行うことで、等式・不等式制約をソルバーが扱える形に変換可能か確認する

  3. ソルバーが扱えない制約条件が存在するならばそのペナルティ関数を計算し、ペナルティ関数が変数変換と次数下げで目的関数と同条件に変換可能か確認する

  4. 目的関数と全ての制約条件が変換可能なら、変数変換と次数下げを実行する

  5. 使用していない変数を削除して変数とモデルを再構築する

  6. 入力モデルと中間モデルの間の変数変換マップを作成する

グラフ埋め込み

グラフ埋め込みが必要なソルバーの場合、中間モデルへの変換に加えてグラフ埋め込みを行います。 グラフ埋め込みが必要かどうかはソルバーごとに決まっており、グラフ埋め込みが必要なソルバーはソルバークライアントの一覧にて Graph というラベルが付与されています。

まず、ソルバークライアントからソルバー固有のグラフ構造を取得します。以下は DWaveSamplerClient の例です。

from amplify import DWaveSamplerClient

client = DWaveSamplerClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

>>> graph = client.graph # DWaveSampler のグラフ構造 
>>> graph.type 
'Pegasus'
>>> len(graph.nodes) 
5627
>>> len(graph.edges) 
40279

DWaveSamplerClient に対応するソルバーが持つグラフ構造は、ノード 5627 個とエッジ 40279 個からなるペガサスグラフであることが分かります。

Amplify SDK は以下の手順によって 2 次の多項式に対してグラフ埋め込みを行い、ソルバーが扱えるようにします。

グラフ埋め込みの処理手順

  1. 中間モデルのそれぞれの制約条件のペナルティ関数を目的関数に足すことにより、中間モデルを目的関数のみからなる最適化問題 (制約なし中間モデル) に変換する

  2. 制約なし中間モデルの目的関数のグラフ表現からソルバー固有のグラフ (物理グラフ) へのグラフ埋め込みを試みる

  3. 中間モデルと物理グラフの間の変数の対応マップ (チェイン) を作成する

  4. チェインに基づいて 1. で得られた多項式の変換を行い、ソルバーが扱える形式の多項式を得る

ソルバーの実行と結果の取得

以上のモデル変換とグラフ埋め込みによってソルバーの入力可能な形式に変換ができました。その後、Amplify SDK は solve() 関数に与えられたソルバークライアントに対して solve メソッドを呼び出し、ソルバーによる最適化を実行します。ソルバークライアントは、ソルバーの要求するリクエストデータの作成から API や最適化関数の呼び出しを経て、ソルバーのレスポンスの解析までを行います。

Amplify SDK はソルバーから返却された解に対して、グラフ埋め込みによる変数変換処理と中間モデルの構築における変数変換それぞれの逆変換を段階的に行い、入力モデルの解を取得して solutions アトリビュートに格納します。

solve() 関数は返値の Result クラスに一連の変換・逆変換処理やソルバーの実行結果に関する情報を保存します。以下は代表的な情報を取得するためのResult クラスのアトリビュートです。

アトリビュート

データ型

概要

詳細

solutions

SolutionList

入力モデルの解や目的関数の値などの情報を格納

intermediate

ModelConversion

中間モデルとその変数変換情報を格納

embedding

GraphConversion

中間モデルから物理グラフへのグラフ埋め込み情報を格納 (グラフ埋め込みが必要な場合のみ)

client_result

Client.Result

ソルバークライアントの実行結果を格納

参考

中間モデルとグラフ埋め込みの実行結果に関する情報の詳細は、それぞれ 変数変換と次数下げ と グラフ埋め込み を参照してください。

モデル変換のパラメータ

モデル変換の際に使用されるパラメータを以下に示します。これらは、solve() 関数のキーワード引数として与えることができます。

パラメータ名

モデル変換の種類

概要

詳細

integer_encoding_method

変数変換

整数変数をバイナリ変数に変換変換するアルゴリズム

real_encoding_method

変数変換

実数変数をバイナリ変数に変数変換するアルゴリズム

quadratization_method

次数下げ

次数下げに使用するアルゴリズム

substitution_multiplier

次数下げ

次数下げで生成される制約条件の重み

embedding_method

グラフ埋め込み

グラフ埋め込みに使用するアルゴリズム

embedding_timeout

グラフ埋め込み

グラフ埋め込みのタイムアウト値 (秒)

chain_strength

グラフ埋め込み

多項式のグラフ埋め込みの際のパラメータ

たとえば、solve() 関数の中で、整数変数をバイナリ変数に変換変換する際に使用するアルゴリズムを Unary に設定したい場合は、以下のようにします。

result = solve(model, client, integer_encoding_method="Unary")

また、以下のパラメータは、不等式制約のペナルティ生成方法を指定します。不等式制約を表す制約条件オブジェクト Constraint を less_equal() などのヘルパー関数や Constraint クラスのコンストラクタを使って構築する際に、キーワード引数 method により指定できます。

パラメータ名

モデル変換の種類

概要

詳細

penalty_formulation

ペナルティ生成

ペナルティ生成のアルゴリズム

たとえば、solve() 関数の中で、不等式制約のペナルティを生成する際に使用するアルゴリズムを IntegerVariable に設定したい場合は、以下のようにします。

le_constraint = less_equal(
    q[0] + q[1] + q[2], 2, penalty_formulation="IntegerVariable"
)

次のステップ

以下のページでは、Amplify の変換処理をより詳しく知りたい方のために、Amplify の行うモデル変換処理・ペナルティ関数の生成による制約条件の実現・グラフ埋め込み処理について説明しています。

変数変換と次数下げ

解きたいモデルをソルバーの扱える変数の種類や多項式の次数に合わせるために Amplify SDK の実装している変数変換と次数下げの方法を説明します。

Learn more »

変数変換と次数下げ
制約条件とペナルティ関数

制約条件を扱えないソルバーに対して Amplify SDK がどのようなペナルティ関数を生成し、制約条件を実現しているかを説明します。

Learn more »

制約条件とペナルティ関数
グラフ埋め込み

ソルバーに入力可能な二次多項式にソルバー固有の構造を持つ場合に、任意の入力を可能にするために行われるグラフ埋め込みの処理について解説します。 特に、D-Wave の例を用いて Amplify SDK で実装されるグラフ埋め込みの詳細を説明します。

Learn more »

グラフ埋め込み