部分和問題#

このページでは、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 \]

を最小化してください。

上記の \(\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
\[\displaystyle [q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_7, q_8, q_9]\]

目的関数 \(\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)
[0. 0. 1. 0. 1. 1. 1. 0. 1. 0.]

バイナリ変数 \(q_i\) は、数列 \(A\)\(i\) 番目の要素が選ばれるなら \(1\)、そうでないときは \(0\) をとるので、部分和問題の最適解は以下のように表示できます。

print(f"selected numbers: {[a for x, a in zip(q_values, A) if x == 1]}")
selected numbers: [3, 5, 7, 9, 3]

和が \(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