【QAP.練習問題2】：ビンパッキング問題【量子コンピュータ/アニーリング@Python/D-Wave】

【はじめに】

「D-Wave」による「CQM」の練習として、簡単な「ビンパッキング問題」を解いてみる。

【練習問題】

「５つのアイテム」と「５つの入れ物（ビン）」がある。
「アイテムの重さ」、「入れ物（ビン）の耐久重量」は次のとおりである。

できるだけ使用する「入れ物（ビン）」を「少なく」しつつ、「５つのアイテム」を「入れ物（ビン）」に詰めていきたい。

最小いくつの入れ物（ビン）が必要だろうか？また、その時の組み合わせはどうなっているだろうか？

---

【解答例】

実行環境は「D-Wave Leap」＋「Google Colab」でやる。

■考え方

考え方のイメージは次の通り。

①：「各アイテムごと」に「入れ物（ビン）」の数だけ「フラグ変数」を用意する。
→　「アイテム：i」を「入れ物：j」に入れるときは「x_i_j =1」としてフラグを立てる

②：使用する「入れ物（ビン）」に対する「フラグ変数」を用意する。
→　「入れ物：j」に何かしらアイテムが入る場合は「y_j=1」としてフラグを立てる

③：使用する「入れ物（ビン）」の数をできるだけ少なくすることが目的
→　②の変数y_jの合算値をできるだけ小さくする

つまり、「x_i_j」という変数と「y_j」という「意味合いが違う２種類のフラグ変数」を用意して数式を作っていく、ということである。

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

#ライブラリのインストール
!pip install dwave-ocean-sdk

（※再掲：ネット上を検索すると「dwave-system」というよく似たライブラリも出てくるので困惑するかもしれないが、「dwave-ocean-sdk」の「pip」時に一緒に入るので気にしなくてよい。）

【２】トークン設定

---

※再掲：
トークンを使ったD-Waveへのアクセスについては以下の通り

Configuring Access to Leap’s Solvers — Ocean Documentation 4.4.0 documentation

上記ドキュメント記載の通り、本来はアクセストークン漏洩防止など、セキュリティの観点から「コンフィグファイル」や「環境変数」に仕込む。

【注意】
今回は簡単なプログラムをちょっと試してみるだけなので、「Samplerオブジェクトに仕込む」というやり方で手抜きをしている。

リリースアプリ、実運用ではSamplerへのトークン埋め込みはしないこと。

---

■トークン設定

# Sampler埋め込み用トークン（本番では行わないこと）
# 各自登録して取得したアクセストークンを指定する
MY_DWAVE_TOKEN = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

トークンを使った接続確認として、使用可能なSolver情報を出力してみる。

from dwave.cloud import Client

# トークンを使った接続確認
# 使用可能なSolver情報を出力する
client = Client.from_config(token=MY_DWAVE_TOKEN)
print(client.get_solvers())

【実行結果例】
[BQMSolver(id='hybrid_binary_quadratic_model_version2'), DQMSolver(id='hybrid_discrete_quadratic_model_version1'), CQMSolver(id='hybrid_constrained_quadratic_model_version1'), StructuredSolver(id='DW_2000Q_6'), StructuredSolver(id='Advantage_system4.1')]

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

items_w = [21.0, 15.0, 29.0, 17.0, 13.0]
bins_w = [45, 45, 45, 45, 45]

【４－１】変数定義１：x_i_jを定義(dimod版)

１種類目の「変数：x_i_j」は次のようにする。

x_i_j：「アイテムｉ」が「入れ物ｊ」に
・入る場合：１
・入らない場合：０

これを踏まえて「Binary変数」を用意する。
→　今回は「dimod.Binary()」を使っていく。