knapsack

ナップザック

ナップザック問題はよく知られた最適化問題です。たとえば、輸送用コンテナの梱包時に発生します。輸送用コンテナには、それが保持できる重量があります。出荷する品目のコレクションがあり、各品目に価値と重量がある場合、問題は、出荷用コンテナに梱包する最適な品目を選択することです。この最適化問題は、制約のある目的として定義できます。

• 目的:運賃額 (選択したアイテムの合計額) を最大化します。
• 制約:貨物の総重量 (選択したアイテムの重量の合計) は、コンテナの容量以下である必要があります。

この例では、このようなナップザック問題を制約付き 2 次モデル (CQM) として再定式化して Leap ハイブリッド CQM ソルバーに送信することで解決します。

使用法

デフォルトのデモを実行するには、次のコマンドを入力します。

python knapsack.py

利用可能なオプションを表示するには、次のコマンドを入力します。

python knapsack.py --help

コマンドライン引数を使用すると、複数のデータ セット ( /dataフォルダーの下) から 1 つを選択し、貨物輸送量を設定できます。データ ファイルは項目の行として形式化され、それぞれが重量と値のペアとして定義されます。

コードの概要

knapsack.pyのコードには、次の 3 つの主要な関数が含まれています。

• build_knapsack_cqm()次のように目的と制約を設定して CQM を作成します。

  • 目的: アイテムごとにバイナリ変数が作成され、アイテムの値の負の値に等しい線形バイアスが割り当てられます。最適な品目のセットを選択してこの目的を最小限に抑えることは、貨物の合計価値を最大化することと同じです。ソリューションでは、選択された項目に値 1 を設定し、選択されていない項目に値 0 を設定します。
  • 制約: 事前に作成したバイナリ変数を使用した 2 次モデル (線形バイアスが各アイテムの重量に等しく設定されている) は、総重量がコンテナの容量を超えてはならないという要件で作成されます。

• parse_inputs()サンプル ファイルからデータを読み取るユーティリティ関数です。

• parse_solution() 、ソルバーから返された結果を解析して表示します。

ライセンス

Apache License 2.0 に基づいてリリースされています。 LICENSE ファイルを参照してください。