7. 組合せ最適化問題の求解¶
このページでは、「モデルの定式化」と「クライアントの作成」で作成したモデル Model およびソルバークライアントを使用して、組合せ最適化問題を求解する方法を解説します。
7.1. Solve 関数¶
組合せ最適化を実行するために、solve() 関数が用意されています。この関数は第一引数に Model を、第二引数にソルバークライアントオブジェクトを受け取り、
ソルバークライアントに対応するソルバーを用いてモデルの最適化を行います。
次の例を Amplify AE を用いて最適化します。
目的関数と制約条件を構築して、モデルを作成します。
from amplify import VariableGenerator, one_hot, AmplifyAEClient, solve
gen = VariableGenerator()
q = gen.array("Binary", 3)
objective = q[0] * q[1] - q[2]
constraint = one_hot(q)
model = objective + constraint
Amplify AE のソルバークライアントを作成して、タイムアウト時間を 1000 ミリ秒に設定します。
from datetime import timedelta
client = AmplifyAEClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.time_limit_ms = timedelta(milliseconds=1000)
次のようにモデルとソルバークライアントを solve() 関数に与え、求解します。
result = solve(model, client)
得られた結果は、以下のようにして確かめることができます。詳細は結果の取得を参照してください。
>>> print(f"objective = {result.best.objective}")
objective = -1.0
>>> print(f"q = {q.evaluate(result.best.values)}")
q = [0. 0. 1.]
参考
Amplify SDK は、入力されたモデルをクライアントが受け取れる形へ自動で変換します。この変換には、ペナルティ関数の計算、変数変換や次数下げ、グラフ埋め込みがあり、必要なものだけを適用します。solve() 関数には、このモデル変換で使用するいくつかのパラメータを指定できます。各パラメータの詳細については「モデル変換のパラメータ」下の各ページを参照してください。
7.1.1. モデル構築の省略¶
モデルが目的関数のみ、または制約条件のみから構成される場合、solve() 関数の第 1 引数にオブジェクトを直接渡せます。渡せるのは Poly、Constraint、ConstraintList クラスのオブジェクトです。
from amplify import VariableGenerator, one_hot, AmplifyAEClient, solve
from datetime import timedelta
gen = VariableGenerator()
q = gen.array("Binary", 3)
objective = q[0] * q[1] - q[2]
constraint1 = one_hot(q[0] + q[1])
constraint2 = one_hot(q[1] + q[2])
client = AmplifyAEClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.time_limit_ms = timedelta(milliseconds=1000)
制約条件のない組合せ最適化問題を解く:
result = solve(objective, client)
単一の制約条件からなる組合せ最適化問題を解く:
result = solve(constraint1, client)
制約条件のみからなる組合せ最適化問題を解く:
result = solve(constraint1 + constraint2, client)
7.2. 結果の取得¶
solve() 関数が返す Result オブジェクトには、ソルバーが返した解の情報や実行にかかった時間の情報が含まれています。
from amplify import VariableGenerator, one_hot, AmplifyAEClient, solve
from datetime import timedelta
gen = VariableGenerator()
q = gen.array("Binary", 3)
objective = q[0] * q[1] - q[2]
constraint = one_hot(q)
model = objective + constraint
client = AmplifyAEClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.time_limit_ms = timedelta(milliseconds=1000)
result = solve(model, client)
Result に含まれる解の個数は len() 関数により取得できます。デフォルトでは、制約条件を全てみたす解のみが Result に含まれています。
>>> len(result)
1
Result に 1 個以上の解が含まれている場合、best プロパティにより最良解を取得できます。
>>> type(result.best)
<class 'amplify.Result.Solution'>
best プロパティにより取得できる最良解は Solution クラスのインスタンスです。このクラスは以下のアトリビュートを持ちます。
以下のようにして、最良解における目的関数の値、変数の値、制約条件が全てみたされているかどうか、解が得られた時刻をそれぞれ取得できます。
>>> result.best.objective
-1.0
>>> result.best.values
Values({Poly(q_0): 0, Poly(q_1): 0, Poly(q_2): 1})
>>> result.best.feasible
True
>>> result.best.time
datetime.timedelta(microseconds=27965)
変数配列の evaluate() メソッドに values を渡すことで、変数配列の各変数に対応する解の値を変数配列と同じ形の ndarray として得ることができます。
>>> print(q.evaluate(result.best.values))
[0. 0. 1.]
注意
使用したソルバーによっては、解が得られた時刻を取得できない場合があります。その場合、time アトリビュートにはソルバーの実行時間 execution_time と同じ値が入ります。詳しくは 実行時間情報の取得 を参照してください。
Result には最良解だけでなく複数の解が含まれている場合があります。それぞれの解は、Result に対するインデックスアクセスにより Solution クラスのインスタンスを取得できます。
>>> result[0].objective
-1.0
>>> result[0].feasible
True
イテレートによるアクセスも可能です。
>>> for r in result:
... print(r.objective)
... print(r.values)
... print(r.feasible)
... print(r.time)
-1.0
amplify.Values({Poly(q_0): 0.0, Poly(q_1): 0.0, Poly(q_2): 1.0})
True
0:00:00.028060
7.3. 実行結果の出力オプション¶
デフォルトでは、solve() 関数が返す Result オブジェクトには、制約条件をみたす解のみが目的関数の値が小さい順に入っています。solve() 関数に filter_solution キーワード引数および sort_solution キーワード引数を指定すると、この動作を変更できます。
7.3.1. 解のフィルタ¶
solve() 関数の filter_solution キーワード引数に False を指定すると、制約条件をみたさない解も Result に含めることができます。
from amplify import VariableGenerator, equal_to, Model, AmplifyAEClient, solve
from datetime import timedelta
gen = VariableGenerator()
q = gen.array("Binary", 3)
constraint1 = equal_to(q, 1)
constraint2 = equal_to(q, 2)
model = Model(constraint1 + constraint2)
client = AmplifyAEClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.time_limit_ms = timedelta(milliseconds=1000)
>>> result1 = solve(model, client)
>>> len(result1)
0
>>> result2 = solve(model, client, filter_solution=False)
>>> len(result2)
1
>>> result2.best.feasible
False
solve() 関数を呼んだあとでも、この動作を変更できます。Result の filter_solution プロパティを False に指定すると、制約条件をみたさない解も Result に含まれます。
>>> result = solve(model, client)
>>> len(result)
0
>>> result.filter_solution = False
>>> len(result)
1
7.3.2. 解のソート¶
デフォルトでは、Result に含まれる解は良い順にソートされています。solve() 関数の sort_solution キーワード引数に False を指定すると、Result に入る解の順番はソルバーが返した解の順番のままになります。
result = solve(model, client, sort_solution=False)
Result の sort() メソッドにより、あとからでも解をソートできます。
result.sort()
注釈
Amplify SDK では、解の良さを以下の順に判定します。
制約条件をみたしているかどうか
目的関数の値が小さいかどうか
したがって、Result の best プロパティは、制約条件をみたしている解のうち、最も目的関数の値が小さいものを返します。制約条件をみたしている解がない場合、filter_solution を False にしてあれば、最も目的関数の値の小さい解を返します。
7.4. dry-run オプション¶
solve() 関数の dry_run キーワード引数に True を指定すると、Amplify SDK はソルバーにモデルを送る直前までの処理を実行します。多くのソルバークライアントでは、API トークンを指定しなくても dry_run を指定した solve() 関数を実行できます。
このオプションを使うと、ソルバーへ接続する前に次の 3 点を確認できます。求解したいモデルをソルバーへ入力できるか、どのようなモデル変換やグラフ埋め込みを適用するか、どのようなリクエストデータを送るかです。
from amplify import VariableGenerator, equal_to, Model, AmplifyAEClient, solve
from datetime import timedelta
gen = VariableGenerator()
q = gen.array("Binary", 3)
constraint1 = equal_to(q, 1)
constraint2 = equal_to(q, 2)
model = Model(constraint1 + constraint2)
client = AmplifyAEClient()
result = solve(model, client, dry_run = True)
dry_run オプションを指定して実行した場合、solve() 関数が返す Result オブジェクトには解は入っていません。
>>> len(result)
0
注釈
dry_run オプションを指定して実行しても、Result の intermediate プロパティと embedding プロパティは変わりません。オプションを指定せずに実行した場合と同じ結果になります。これは、モデル変換とグラフ埋め込みがどのように行われるかを知りたい場合に便利です。各プロパティの詳細についてはモデルの変換をご覧ください。
注釈
dry_run オプションを指定して実行すると、Amplify SDK は実際のリクエストをソルバーへ送りません。ただし、ソルバークライアントの write_request_data を設定してあれば、リクエストデータをファイルへ書き込みます。write_request_data の詳細については 送受信データの保存 ☁️ Cloud 💻 Localをご覧ください。