ナップザック問題¶

重さと価値を持つアイテムの集合と、重量制限のあるナップサックが与えられたとき、ナップサック問題は、総重量が容量以内に収まるようにしつつ、総価値を最大化するアイテムの部分集合を選択することを目的とします。 \(w_i\) と \(v_i\) (\(0 \leq i \leq n-1\)) をそれぞれアイテム \(i\) の重さと価値とします。 \(S \subset \{0, \cdots, n-1\}\) を選択されたアイテムの集合とします。

\[\begin{split} \mathrm{max} &\sum_{i \in S}v_i,\\ \mathrm{subject~to} &\sum_{i \in S}w_i \leq W. \end{split}\]

ここで \(W\) はナップサックの重量容量です。

QUBO定式化¶

この問題をQUBOとして定式化するために、\(n\) 個のバイナリ変数 \(x_i \in \{0,~1\}\) (\(0 \leq i \leq n-1\)) の集合 \(X\) を導入します。ここで、アイテム \(i\) が選択されるのは \(x_i=1\) のときかつそのときに限ります。

上記の定式化は次のように書き換えられます：

\[\begin{split} \mathrm{max} &\sum_{i=0}^{n-1}v_ix_i,\\ \mathrm{subject~to} &\sum_{i=0}^{n-1}w_ix_i \leq W. \end{split}\]

QUBO++プログラム

制約はQUBO++が提供する 範囲演算子 を用いて表現できます。結果として得られるQUBO目的関数は次のように定義されます：

PyQBPPプログラム

制約はPyQBPPが提供する 範囲演算子 を用いて表現できます。結果として得られるQUBO目的関数は次のように定義されます：

\[ f(X) = -\sum_{i=0}^{n-1}v_ix_i + P \left( 0 \leq \sum_{i=0}^{n-1}w_ix_i \leq W \right) \]

QUBOソルバーは目的関数を最小化するため、元の最大化目的は符号を反転しています。定数 \(P\) は制約を強制するための十分大きなペナルティパラメータです。

以下のプログラムは、Exhaustive Solverを用いて10個のアイテムのナップサック問題を解きます：

#include <qbpp/qbpp.hpp>
#include <qbpp/exhaustive_solver.hpp>

int main() {
  auto w = qbpp::int_array({10, 20, 30, 5, 8, 15, 12, 7, 17, 18});
  auto v = qbpp::int_array({60, 100, 120, 60, 80, 150, 110, 70, 150, 160});
  int capacity = 50;

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

  auto constraint = 0 <= qbpp::sum(w * x) <= capacity;
  auto objective = qbpp::sum(v * x);

  auto f = -objective + 1000 * constraint;
  f.simplify_as_binary();

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sols = solver.search({{"best_energy_sols", 1}});
  for (size_t i = 0; i < sols.size(); ++i) {
    const auto sol = sols[i];
    std::cout << "[Solution " << i << "]" << std::endl;
    std::cout << "Energy = " << sol.energy() << std::endl;
    std::cout << "Constraint  = " << sol(*constraint) << std::endl;
    std::cout << "Objective  = " << sol(objective) << std::endl;
    for (size_t j = 0; j < w.size(); ++j) {
      if (sol(x[j]) == 1) {
        std::cout << "Item " << j << ": weight = " << w[j]
                  << ", value =  " << v[j] << std::endl;
      }
    }
  }
}

import pyqbpp as qbpp

w = [10, 20, 30, 5, 8, 15, 12, 7, 17, 18]
v = [60, 100, 120, 60, 80, 150, 110, 70, 150, 160]
capacity = 50

x = qbpp.var("x", len(w))

constraint = qbpp.between(qbpp.sum(w * x), 0, capacity)
objective = qbpp.sum(v * x)

f = -objective + 1000 * constraint
f.simplify_as_binary()

solver = qbpp.ExhaustiveSolver(f)
result = solver.search({"best_energy_sols": 0})
for idx, sol in enumerate(result.sols()):
    print(f"[Solution {idx}]")
    print(f"Energy = {sol.energy}")
    print(f"Constraint = {sol(constraint.body)}")
    print(f"Objective = {sol(objective)}")
    for j in range(len(w)):
        if sol(x[j]) == 1:
            print(f"Item {j}: weight = {w[j]}, value = {v[j]}")

このプログラムでは、式 constraint と objective を別々に構築し、ペナルティ係数 1000 を用いて最終的なQUBO式 f に結合しています。次に、Exhaustive Solver を f に適用し、すべての最適解を列挙します。

以下の出力は、エネルギー、制約値、目的関数値を含む最適解を示しています：

[Solution 0]
Energy = -480
Constraint  = 50
Objective  = 480
Item 3: weight = 5, value =  60
Item 5: weight = 15, value =  150
Item 6: weight = 12, value =  110
Item 9: weight = 18, value =  160
[Solution 1]
Energy = -480
Constraint  = 50
Objective  = 480
Item 3: weight = 5, value =  60
Item 4: weight = 8, value =  80
Item 6: weight = 12, value =  110
Item 7: weight = 7, value =  70
Item 9: weight = 18, value =  160

このインスタンスには2つの最適解があり、いずれも総価値 480 を達成しつつ、容量制約をちょうど満たしていることがわかります。