7. 組合せ最適化問題の求解#
このページでは、「モデルの定式化」と「クライアントの作成」で作成したモデル Model およびソルバークライアントを使用して、組合せ最適化問題の求解を行う方法を解説します。
7.1. Solve 関数#
組合せ最適化を実行するために、solve() 関数が用意されています。この関数は第一引数に Model を、第二引数にソルバークライアントオブジェクトを受け取り、
ソルバークライアントに対応するソルバーを用いてモデルの最適化を行います。
次の例を Amplify AE を用いて最適化します。
目的関数と制約条件を構築して、モデルを作成します。
from amplify import VariableGenerator, one_hot, FixstarsClient, 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 = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 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, FixstarsClient, 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 = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 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, FixstarsClient, 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 = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 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, FixstarsClient, 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 = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 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 を指定することで、ソルバーにモデルを送る直前までの処理が行われます。多くのソルバークライアントでは、API トークンを指定しなくても dry_run を指定した solve() 関数の実行が可能です。
このオプションにより、求解したいモデルがソルバーに入力可能なのか、また、その際にどのようなモデル変換やグラフ埋め込みが行われ、どのようなリクエストデータが送られるのかを、ソルバーに接続する前に確認することができます。
from amplify import VariableGenerator, equal_to, Model, FixstarsClient, 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 = FixstarsClient()
result = solve(model, client, dry_run = True)
dry_run オプションを指定して実行した場合、solve() 関数が返す Result オブジェクトには解は入っていません。
>>> len(result)
0
注釈
dry_run オプションを指定して実行した場合、Result の intermediate プロパティおよび embedding プロパティは dry_run オプションを指定せずに実行した場合と同じ結果になります。これは、モデル変換とグラフ埋め込みがどのように行われるかを知りたい場合に便利です。各プロパティの詳細についてはモデルの変換をご覧ください。
注釈
dry_run オプションを指定して実行した場合、実際のリクエストはソルバーには送られませんが、ソルバークライアントの write_request_data が設定されていればリクエストデータのファイル書き込みが行われます。write_request_data の詳細については 送受信データの保存 ☁️ Cloud 💻 Localをご覧ください。