🕸️

QUBO++入門:ナップサック問題を解く

2025/02/03に公開

ナップサック問題

ナップサック問題とは,価値と重さが定められた複数のアイテム中から,総重量の上限値がある中で,合計の価値が最大となるようにアイテムを選ぶ問題です.n個のアイテムの価値をv_0, v_1, \ldots, v_{n-1},重さをw_0, w_1, \ldots, w_{n-1},重量制限をWとします.ナップサック問題は次のように整数計画問題として記述することができます.

  • 目的関数:価値の最大化
\sum_{i=0}^{n-1} v_0 x_0
  • 制約条件
  1. 総重量がW以下
\sum_{i=0}^{n-1} w_0 x_0 \leq W
  1. x_0, x_1, \ldots, x_{n-1}は2値変数

よって,2値変数x_0, x_1, \ldots, x_{n-1}のQUBO式でナップサック問題をそのまま記述することができます.

ナップサック問題を解くQUBO++プログラム

ナップサック問題を整数計画問題として記述できたため,その形式をそのままQUBO++で表現します.以下がソースコードです.

#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"

int main() {
  qbpp::Vector<int> values = {20, 30, 50, 60, 40, 10, 25, 35};
  qbpp::Vector<int> weights = {4, 5, 8, 7, 6, 3, 4, 5};

  auto x = qbpp::var("x", values.size());

  auto objective = qbpp::sum(x * values);
  auto total_weight = qbpp::sum(x * weights);
  auto constraint = 0 <= total_weight <= 20;
  auto f = -objective + constraint * 1000;
  f.simplify_as_binary();
  std::cout << "f = " << f << std::endl;

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sol = solver.search();

  std::cout << sol << std::endl;
  for (size_t i = 0; i < values.size(); i++) {
    if (sol.get(x[i]) == 1) {
      std::cout << "Item " << i << " with value " << values[i] << " and weight "
                << weights[i] << " is selected" << std::endl;
    }
  }
  std::cout << "Total value: " << qbpp::eval(objective, sol) << std::endl;
  std::cout << "Total weight: " << qbpp::eval(total_weight, sol) << std::endl;
}

上記のプログラムでは,qbpp::Vector<int>で価値 (values) と重さ (weights) をそれぞれ配列として定義しています.次に,二値変数のベクトルx を生成し,valuesweights のそれぞれとの内積を計算することで,目的関数 (objective) と総重量 (total_weight) を導出します.

さらに,total_weight[0, 20] の範囲内に収まる条件をconstraintとして生成します.この制約を考慮して,ナップサック問題を解くためのQUBO式fを次のように構築します:

  • 最大化問題なので,QUBO式には -objective を使用します.
  • 制約を目的関数より優先させる必要があるため,制約に優先度として1000を掛け合わせています.
    最後に,f を整理(simplify_as_binary()) し,Exhaustive Solverを使用して最適解を求めます.
    選択されたアイテムの詳細や,総価値と総重量を出力することで,結果を確認できます.
    このプログラムを実行すると次の結果が表示されます.
f = 5980*x[0] +9970*x[1] +27950*x[2] +20940*x[3] +14960*x[4] +2990*x[5] +5975*x[6] +9965*x[7] +3000*{0}[0] +10000*{0}[1] +36000*{0}[2] +15000*{0}[3] +20000*x[0]*x[1] +32000*x[0]*x[2] +28000*x[0]*x[3] +24000*x[0]*x[4] +12000*x[0]*x[5] +16000*x[0]*x[6] +20000*x[0]*x[7] -8000*x[0]*{0}[0] -16000*x[0]*{0}[1] -32000*x[0]*{0}[2] -20000*x[0]*{0}[3] +40000*x[1]*x[2] +35000*x[1]*x[3] +30000*x[1]*x[4] +15000*x[1]*x[5] +20000*x[1]*x[6] +25000*x[1]*x[7] -10000*x[1]*{0}[0] -20000*x[1]*{0}[1] -40000*x[1]*{0}[2] -25000*x[1]*{0}[3] +56000*x[2]*x[3] +48000*x[2]*x[4] +24000*x[2]*x[5] +32000*x[2]*x[6] +40000*x[2]*x[7] -16000*x[2]*{0}[0] -32000*x[2]*{0}[1] -64000*x[2]*{0}[2] -40000*x[2]*{0}[3] +42000*x[3]*x[4] +21000*x[3]*x[5] +28000*x[3]*x[6] +35000*x[3]*x[7] -14000*x[3]*{0}[0] -28000*x[3]*{0}[1] -56000*x[3]*{0}[2] -35000*x[3]*{0}[3] +18000*x[4]*x[5] +24000*x[4]*x[6] +30000*x[4]*x[7] -12000*x[4]*{0}[0] -24000*x[4]*{0}[1] -48000*x[4]*{0}[2] -30000*x[4]*{0}[3] +12000*x[5]*x[6] +15000*x[5]*x[7] -6000*x[5]*{0}[0] -12000*x[5]*{0}[1] -24000*x[5]*{0}[2] -15000*x[5]*{0}[3] +20000*x[6]*x[7] -8000*x[6]*{0}[0] -16000*x[6]*{0}[1] -32000*x[6]*{0}[2] -20000*x[6]*{0}[3] -10000*x[7]*{0}[0] -20000*x[7]*{0}[1] -40000*x[7]*{0}[2] -25000*x[7]*{0}[3] +8000*{0}[0]*{0}[1] +16000*{0}[0]*{0}[2] +10000*{0}[0]*{0}[3] +32000*{0}[1]*{0}[2] +20000*{0}[1]*{0}[3] +40000*{0}[2]*{0}[3]
-145:{{x[0],0},{x[1],0},{x[2],1},{x[3],1},{x[4],0},{x[5],0},{x[6],0},{x[7],1},{{0}[0],1},{{0}[1],1},{{0}[2],1},{{0}[3],1}}
Item 2 with value 50 and weight 8 is selected
Item 3 with value 60 and weight 7 is selected
Item 7 with value 35 and weight 5 is selected
Total value: 145
Total weight: 20

アイテム2,3,7を選び,総価値が145,総重量が20となります.

QUBO++情報

広島大学コンピューティングラボ
設定によりコメント欄が無効化されています