部分和問題#
このページでは、Amplify SDK を用いた定式化と求解の簡単な例として、部分和問題を扱います。
部分和問題とは、以下のような問題です。
\(N\), \(K\) を正の整数とします。\(N\) 個の正の整数からなる数列 \(A_0, A_1, \ldots, A_{N - 1}\) があります。 この数列の部分列であって、要素の総和が \(K\) に最も近くなるものを求めてください。
あるいは、以下のような言い換えが考えられます。
\(N\) 本の動画があり、その長さはさまざまです。これらの中からいくつかを選んで、合計時間が \(K\) 分に最も近くなるようにするには、どの動画を選ぶべきでしょうか?
問題の作成#
Amplify SDK を用いて部分和問題を解く前に、まずは部分和問題を作成し、プログラムコード上で表現します。今回は例題として、要素数 \(N=10\) の簡単な問題を扱います。
import numpy as np
N = 10
K = 27
A = np.array([2, 10, 3, 8, 5, 7, 9, 5, 3, 2])
Amplify SDK による定式化#
Amplify SDK による定式化を行うためには、部分和問題を多項式の最小化問題に言い換える必要があります。
まず、「部分列の要素の和が \(K\) に最も近いもの」は、「部分列の要素の和と \(K\) の差を 2 乗した値が最小となるもの」に言い換えられます。また、「部分列の要素の和」は、数列の \(i\) 番目の要素が選ばれるなら \(1\), そうでないなら \(0\) をとる変数 \(q_i\) を用いて、\(q_0 A_0 + q_1 A_1 + \cdots + q_{N-1} A_{N-1}\) と書くことができます。
したがって、部分和問題は以下のように定式化されます。
変数 \(q_0, q_1, \ldots, q_{N-1}\) が \(0\) または \(1\) の値をとるとき、
を最小化してください。
上記の \(\quad (q_0 A_0 + q_1 A_1 + \cdots + q_{N-1} A_{N-1} - K)^2\) のことを目的関数とよびます。
以上を Amplify SDK 上で表現していきましょう。
決定変数 (組合せ最適化において最適化対象の変数) を作成します。まず、変数を発行するためのクラス VariableGenerator をインスタンス化します。必要な変数は、 \(0\) または \(1\) の値をとる変数が \(N\) 個です。\(0\) または \(1\) の値をとる変数はバイナリ変数といい、Amplify SDK では簡単に作成できます。
from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", N) # 第一引数に変数の種類を、第二引数に変数の数を与える
q
目的関数 \(\quad (q_0 A_0 + q_1 A_1 + \cdots + q_{N-1} A_{N-1} - K)^2\) を作成します。NumPy-like な記法を用いて、以下のように書くことができます。
objective = ((q * A).sum() - K) ** 2
print(objective)
40 q_0 q_1 + 12 q_0 q_2 + 32 q_0 q_3 + 20 q_0 q_4 + 28 q_0 q_5 + 36 q_0 q_6 + 20 q_0 q_7 + 12 q_0 q_8 + 8 q_0 q_9 + 60 q_1 q_2 + 160 q_1 q_3 + 100 q_1 q_4 + 140 q_1 q_5 + 180 q_1 q_6 + 100 q_1 q_7 + 60 q_1 q_8 + 40 q_1 q_9 + 48 q_2 q_3 + 30 q_2 q_4 + 42 q_2 q_5 + 54 q_2 q_6 + 30 q_2 q_7 + 18 q_2 q_8 + 12 q_2 q_9 + 80 q_3 q_4 + 112 q_3 q_5 + 144 q_3 q_6 + 80 q_3 q_7 + 48 q_3 q_8 + 32 q_3 q_9 + 70 q_4 q_5 + 90 q_4 q_6 + 50 q_4 q_7 + 30 q_4 q_8 + 20 q_4 q_9 + 126 q_5 q_6 + 70 q_5 q_7 + 42 q_5 q_8 + 28 q_5 q_9 + 90 q_6 q_7 + 54 q_6 q_8 + 36 q_6 q_9 + 30 q_7 q_8 + 20 q_7 q_9 + 12 q_8 q_9 - 104 q_0 - 440 q_1 - 153 q_2 - 368 q_3 - 245 q_4 - 329 q_5 - 405 q_6 - 245 q_7 - 153 q_8 - 104 q_9 + 729
注釈
もちろん、古典的な Python 風に
objective = sum(x * a for x, a in zip(q, A))
などと書くこともできます。ただし、このような書き方は問題やデータサイズによっては時間がかかる場合があるため、objective = (q * A) ** 2 のような NumPy-like な書き方を推奨しています。詳しくは 定式化の高速化 を参照してください。
作成した目的関数を使って、組合せ最適化モデルを構築します。
from amplify import Model
model = Model(objective)
print(model)
minimize:
40 q_0 q_1 + 12 q_0 q_2 + 32 q_0 q_3 + 20 q_0 q_4 + 28 q_0 q_5 + 36 q_0 q_6 + 20 q_0 q_7 + 12 q_0 q_8 + 8 q_0 q_9 + 60 q_1 q_2 + 160 q_1 q_3 + 100 q_1 q_4 + 140 q_1 q_5 + 180 q_1 q_6 + 100 q_1 q_7 + 60 q_1 q_8 + 40 q_1 q_9 + 48 q_2 q_3 + 30 q_2 q_4 + 42 q_2 q_5 + 54 q_2 q_6 + 30 q_2 q_7 + 18 q_2 q_8 + 12 q_2 q_9 + 80 q_3 q_4 + 112 q_3 q_5 + 144 q_3 q_6 + 80 q_3 q_7 + 48 q_3 q_8 + 32 q_3 q_9 + 70 q_4 q_5 + 90 q_4 q_6 + 50 q_4 q_7 + 30 q_4 q_8 + 20 q_4 q_9 + 126 q_5 q_6 + 70 q_5 q_7 + 42 q_5 q_8 + 28 q_5 q_9 + 90 q_6 q_7 + 54 q_6 q_8 + 36 q_6 q_9 + 30 q_7 q_8 + 20 q_7 q_9 + 12 q_8 q_9 - 104 q_0 - 440 q_1 - 153 q_2 - 368 q_3 - 245 q_4 - 329 q_5 - 405 q_6 - 245 q_7 - 153 q_8 - 104 q_9 + 729
これで組合せ最適化モデルの構築が完了しました。
ソルバーの設定#
Amplify SDK を用いて、さまざまな組合せ最適化ソルバーに求解を行わせることができます。このページでは、例として、クラウドサービスとして提供されている Fixstars Amplify AE を使用します。
まず、どのソルバーを使用するかを指定するために、Amplify AE に対応する Amplify SDK のソルバークライアント FixstarsClient を作成します。
from amplify import FixstarsClient
client = FixstarsClient()
ソルバーで求解を行うために必要なトークンと、ソルバーのパラメータを設定します。
from datetime import timedelta
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = timedelta(milliseconds=1000)
これでソルバーの設定は完了です。
Amplify SDK による求解#
上記で作成した組合せ最適化モデルとソルバークライアントを使用して、求解を実行します。以下のコードを実行することで、Amplify AE で部分和問題を求解することができます。
from amplify import solve
result = solve(model, client)
変数 \(q = (q_0, q_1, \ldots, q_{N-1})\) の値は、以下のように得ることができます。
q_values = q.evaluate(result.best.values)
print(q_values)
[1. 0. 1. 1. 1. 1. 0. 0. 0. 1.]
バイナリ変数 \(q_i\) は、数列 \(A\) の \(i\) 番目の要素が選ばれるなら \(1\)、そうでないときは \(0\) をとるので、部分和問題の最適解は以下のように表示できます。
print(f"selected numbers: {[a for x, a in zip(q_values, A) if x == 1]}")
selected numbers: [2, 3, 8, 5, 7, 2]
和が \(K=27\) と近い値になっていることを確かめます。
print(
f"{K=}, sum of selected numbers = {sum(a for x, a in zip(q_values, A) if x == 1)}"
)
K=27, sum of selected numbers = 27