【はじめに】

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

【練習問題】

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

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

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

【解答例】

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

■考え方

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

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

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

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

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

【２】トークン設定

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

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

■トークン設定

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

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

from dwave.cloud import Client

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

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

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」は次のようにする。

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