🕸️
QUBO++入門:ナップサック問題を解く
ナップサック問題
ナップサック問題とは,価値と重さが定められた複数のアイテム中から,総重量の上限値がある中で,合計の価値が最大となるようにアイテムを選ぶ問題です.
- 目的関数:価値の最大化
- 制約条件
- 総重量が
以下W
-
は2値変数x_0, x_1, \ldots, x_{n-1}
よって,2値変数
ナップサック問題を解く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
を生成し,values
と weights
のそれぞれとの内積を計算することで,目的関数 (objective
) と総重量 (total_weight
) を導出します.
さらに,total_weight
が 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++情報
- QUBO++ツールとABS2 QUBO Solverの詳細情報:QUBO++に関する公式サイトです.ツールの特徴や使用方法,ABS2 QUBO Solverとの連携について詳しく説明されています.
- 【研究成果】組合せ最適化問題を解くためのプログラミング用ツールQUBO++を無償公開します:広島大学からの公式リリース情報です.QUBO++の開発背景や研究成果について記載されています.
- 利用条件:QUBO++は非商用利用や評価研究目的に限り無償で利用可能です.商用利用や定常的な業務での使用を希望する場合は,ライセンス契約が必要となります.