ナップサック問題
与えられた物品の集合（各物品には重量と価値が設定されている）と、重量制限のあるナップサックがある。ナップサック問題では、総重量を制限内に収めつつ総価値を最大化する物品のサブセットを選択することを目的とする。
$i$ 番目の物品の重量と価値をそれぞれ $w_i$ と $v_i$ ($0\leq i\leq n-1$) で表す。 選択された物品の集合を $S\in \lbrace 0, 1, \ldots n-1\rbrace$ とする。
\[\begin{aligned} \text{最大化対象:} & \sum_{i\in S} v_i \\ \text{制約条件:} & \sum_{i\in S} w_i \leq W \end{aligned}\]ここで $W$ はリュックサックの重量容量である。
QUBO定式化
この問題をQUBOとして定式化するため、$n$個の二値変数$x_i\in\lbrace 0,1\rbrace$（$0\leq i\leq n-1$）の集合$X$を導入する。 ここで、$x_i=1$である場合に限りアイテム$i$が選択される。
上記の定式化は以下のように書き換えられる：
\[\begin{aligned} \text{最大化:} & \sum_{i=0}^{n-1} v_ix_i \\ \text{制約条件:} & \sum_{i=0}^{n-1} w_ix_i \leq W \end{aligned}\]QUBO++プログラム
制約はQUBO++が提供する範囲演算子を用いて表現できる。 結果として得られるQUBO目的関数は以下のように定義される：
\[\begin{aligned} f(X) &= -\sum_{i=0}^{n-1} v_ix_i + P\times (0\leq \sum_{i=0}^{n-1} w_ix_i \leq W) \end{aligned}\]QUBOソルバーは目的関数を最小化するため、元の最大化目的関数は否定される。 定数$P$は制約を強制するのに十分な大きさのペナルティパラメータである。
以下のQUBO++プログラムは、全探索ソルバーを用いて10個のアイテムを持つナップサック問題を解く：
#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"
int main() {
qbpp::Vector<int> w = {10, 20, 30, 5, 8, 15, 12, 7, 17, 18};
qbpp::Vector<int> v = {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_optimal_solutions();
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;
}
}
}
}
このプログラムでは、式 constraint および objective は個別に構築され、最終的なQUBO式 f に結合されます。ペナルティ係数は 1000を用いて結合されます。
その後、網羅的ソルバーを適用し 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 を達成しつつ、容量制約を厳密に満たしている。