【QAP.練習問題1】：0-1ナップサック問題【量子コンピュータ/アニーリング@Python/Fixstars Amplify】

【はじめに】

第(1-2,5-6)回でざっと「Fixstars Amplify」の基本的な使い方をまとめた。
その内容を踏まえてもう「0-1ナップサック問題」を解いてみる。

---

【練習問題１】

６個のアイテム：(x_0,  x_1,  x_2,  x_3,  x_4,  x_5)があり、それぞれ「商品価値」と「重さ」が設定されている。

これらのアイテムを「ナップサック(リュック)」に詰めて運びたいが、ナップザックにも「耐久重量」がある。

６つのアイテムに対する「商品価値」・「重さ」と「ナップザックの耐久重量」の設定値は次のとおりである。

▲ナップサックの重量耐久の範囲で商品を選びつつ、価値を大きくしたい

「ナップサックの耐久重量」の範囲で、６つのアイテムから適当に選びつつ、「詰め込んだアイテムの商品価値の総和」をできるだけ大きくしたい。

どのような組み合わせで選ぶとよいだろうか？

---

【解答例】

実行環境は「Fixstars Amplify」＋「Google Colab」でやる。

【１】ライブラリのインストール

! pip install amplify
! pip install --upgrade amplify

【２】クライアントオブジェクトの作成

from amplify.client import FixstarsClient

client = FixstarsClient()
client.parameters.timeout = 1000 # タイムアウトは1000ミリ秒（1秒）
client.parameters.outputs.duplicate = True # みつかった解が複数あってもOK
client.parameters.outputs.num_outputs = 0  # 0: 見つかった解を全て出力

# トークン設定
client.token = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" # 無料登録して取得したトークンを指定する

※トークンは掲載上「XXX... ...XXX」としているが、実際は「Fixstars Amplify」に無料登録して取得したトークンを設定する。

【３】サンプルデータを用意する

今回は
・商品価値：p
・重量：w
・ナップザックの耐久重量：c
とおく。

# サンプルデータ
p = [10, 13, 18, 31, 7, 15] # 価値
w = [11, 15, 20, 35, 10, 33] # 重さ
c = 47 # 耐久重量
I = range(len(w))

【４】QUBO/イジング変数を用意する

今回の場合は「６つのアイテム」にそれぞれ対し、

リュックに入れない/入れるのフラグを「0 or 1」で表す

■フラグのイメージ図

これを踏まえて、「0 or 1」のいずれかをとる「QUBO変数」を６つ用意する。

from amplify import BinaryPoly, SymbolGenerator
gen = SymbolGenerator(BinaryPoly)   # BinaryPoly の変数ジェネレータを宣言
q = gen.array(len(w)) 
q

【ここまでの実行結果】
[q_0, q_1, q_2, q_3, q_4, q_5]

▲各アイテムについてナップザックに入れる/入れないを決めるQUBO変数を用意する

【５】目的関数

今回の「目的関数」は「価値の合計値」を「できるだけ大きく」する