QUBO++入門：整数を扱う（おつり問題）

おつり問題

アメリカでは，1セント（Penny），5セント（Nickel），10セント（Dime），25セント（Quarter）のコインが使用されています．ここでは，与えられたおつりの金額に対して，必要なコインの枚数を最小化する問題を QUBO++ を用いて解きます．この問題は，整数計画問題として定式化することができます．

1セント，5セント，10セント，25セントのコインの枚数をそれぞれ $p$，$n$，$d$，$q$ とします．
このとき，目的関数は以下のように表され，コイン枚数の合計を最小化します：

$$p + n + d + q$$

おつりの金額を $c$ セントとすると，次の制約条件が課されます：

$$\begin{align*} p + 5 n + 10 d + 25 q &= c \end{align*}$$

以上の整数計画問題を解いていきます．

おつり問題をQUBO++で記述

$p$，$n$，$d$，$q$を整数変数としてQUBO++で記述する際，下限値と上限値を指定する必要があります．明らかに，下限値は0です．上限値については，すべての金額をそのコインで支払った場合を基準に設定します．したがって，おつりの金額を$c$とすると，次のように範囲を定め，QUBO++の整数変数を生成します：

$$\begin{align*} 0 &\leq p \leq c\\ 0 &\leq n \leq c/5\\ 0 &\leq d \leq c/10\\ 0 &\leq q \leq c/25 \end{align*}$$

なお，$p$については，4以下に制限しても問題ありませんが，コインの構成が1，5，10，25以外の任意の値に変更される場合にも対応できるよう，ここでは範囲を一般的に表現しています．

QUBO式は目的関数と制約式の合計として記述します．制約式の影響を強調するため，制約式には$c$倍の重みをかけます．これをQUBO++で書くと次のようになります：

$$\begin{align*} f(p,n,d,q) &= (p + n + d + q)+c(p + 5 n + 10 d + 25 q==c)^2\\ &= (p + n + d + q)+c(p + 5 n + 10 d + 25 q-c)^2 \end{align*}$$

Exhaustive Solverで解く

以上を踏まえて，Exhaustive Solverを用いてこの問題を解くQUBO++プログラムは次のようになります．

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

int main() {
  int c;
  std::cout << "Enter the amount (non-negative integer): ";
  std::cin >> c;

  // Define variables for each coin type
  auto p = 0 <= qbpp::var_int("p") <= c;
  auto n = 0 <= qbpp::var_int("n") <= c / 5;
  auto d = 0 <= qbpp::var_int("d") <= c / 10;
  auto q = 0 <= qbpp::var_int("q") <= c / 25;

  // Objective: Minimize the total number of coins
  auto obj = p + n + d + q;

  // Constraint: Total value of coins equals the c
  auto total = p + 5 * n + 10 * d + 25 * q;
  auto constraint = (total == c);

  // QUBO formulation
  auto f = obj + constraint * c;

  // Simplify the QUBO expression
  f.simplify_as_binary();

  // Define the solver
  qbpp::exhaustive_solver::ExhaustiveSolver solver(f);

  // Search for a solution
  auto sol = solver.search();

  // Print the solution
  std::cout << "Optimal solution found:\n" << sol << std::endl;
  std::cout << "Total number of coins: " << sol.get(obj) << std::endl;
  std::cout << "Details:\n";
  std::cout << "  Penny(1): " << sol.get(p) << std::endl;
  std::cout << "  Nickel(5): " << sol.get(n) << std::endl;
  std::cout << "  Dime(10): " << sol.get(d) << std::endl;
  std::cout << "  Quarter(25): " << sol.get(q) << std::endl;
}

このプログラムを実行し，おつりを67セントとした場合の出力は次の通りです．

Enter the amount (non-negative integer): 67
f = 300763 -8910*p[0] -17686*p[1] -34836*p[2] -67528*p[3] -126480*p[4] -218656*p[5] -34836*p[6] -43214*n[0] -83078*n[1] -152756*n[2] -209034*n[3] -83079*d[0] -152758*d[1] -209037*d[2] -182574*q[0] -182574*q[1] +268*p[0]*p[1] +536*p[0]*p[2] +1072*p[0]*p[3] +2144*p[0]*p[4] +4288*p[0]*p[5] +536*p[0]*p[6] +670*p[0]*n[0] +1340*p[0]*n[1] +2680*p[0]*n[2] +4020*p[0]*n[3] +1340*p[0]*d[0] +2680*p[0]*d[1] +4020*p[0]*d[2] +3350*p[0]*q[0] +3350*p[0]*q[1] +1072*p[1]*p[2] +2144*p[1]*p[3] +4288*p[1]*p[4] +8576*p[1]*p[5] +1072*p[1]*p[6] +1340*p[1]*n[0] +2680*p[1]*n[1] +5360*p[1]*n[2] +8040*p[1]*n[3] +2680*p[1]*d[0] +5360*p[1]*d[1] +8040*p[1]*d[2] +6700*p[1]*q[0] +6700*p[1]*q[1] +4288*p[2]*p[3] +8576*p[2]*p[4] +17152*p[2]*p[5] +2144*p[2]*p[6] +2680*p[2]*n[0] +5360*p[2]*n[1] +10720*p[2]*n[2] +16080*p[2]*n[3] +5360*p[2]*d[0] +10720*p[2]*d[1] +16080*p[2]*d[2] +13400*p[2]*q[0] +13400*p[2]*q[1] +17152*p[3]*p[4] +34304*p[3]*p[5] +4288*p[3]*p[6] +5360*p[3]*n[0] +10720*p[3]*n[1] +21440*p[3]*n[2] +32160*p[3]*n[3] +10720*p[3]*d[0] +21440*p[3]*d[1] +32160*p[3]*d[2] +26800*p[3]*q[0] +26800*p[3]*q[1] +68608*p[4]*p[5] +8576*p[4]*p[6] +10720*p[4]*n[0] +21440*p[4]*n[1] +42880*p[4]*n[2] +64320*p[4]*n[3] +21440*p[4]*d[0] +42880*p[4]*d[1] +64320*p[4]*d[2] +53600*p[4]*q[0] +53600*p[4]*q[1] +17152*p[5]*p[6] +21440*p[5]*n[0] +42880*p[5]*n[1] +85760*p[5]*n[2] +128640*p[5]*n[3] +42880*p[5]*d[0] +85760*p[5]*d[1] +128640*p[5]*d[2] +107200*p[5]*q[0] +107200*p[5]*q[1] +2680*p[6]*n[0] +5360*p[6]*n[1] +10720*p[6]*n[2] +16080*p[6]*n[3] +5360*p[6]*d[0] +10720*p[6]*d[1] +16080*p[6]*d[2] +13400*p[6]*q[0] +13400*p[6]*q[1] +6700*n[0]*n[1] +13400*n[0]*n[2] +20100*n[0]*n[3] +6700*n[0]*d[0] +13400*n[0]*d[1] +20100*n[0]*d[2] +16750*n[0]*q[0] +16750*n[0]*q[1] +26800*n[1]*n[2] +40200*n[1]*n[3] +13400*n[1]*d[0] +26800*n[1]*d[1] +40200*n[1]*d[2] +33500*n[1]*q[0] +33500*n[1]*q[1] +80400*n[2]*n[3] +26800*n[2]*d[0] +53600*n[2]*d[1] +80400*n[2]*d[2] +67000*n[2]*q[0] +67000*n[2]*q[1] +40200*n[3]*d[0] +80400*n[3]*d[1] +120600*n[3]*d[2] +100500*n[3]*q[0] +100500*n[3]*q[1] +26800*d[0]*d[1] +40200*d[0]*d[2] +33500*d[0]*q[0] +33500*d[0]*q[1] +80400*d[1]*d[2] +67000*d[1]*q[0] +67000*d[1]*q[1] +100500*d[2]*q[0] +100500*d[2]*q[1] +83750*q[0]*q[1]
Optimal solution found: 6:{{p[0],0},{p[1],1},{p[2],0},{p[3],0},{p[4],0},{p[5],0},{p[6],0},{n[0],1},{n[1],0},{n[2],0},{n[3],0},{d[0],1},{d[1],0},{d[2],0},{q[0],1},{q[1],1}}
Total number of coins: 6
Details:
  Penny(1): 2
  Nickel(5): 1
  Dime(10): 1
  Quarter(25): 2

この結果から，67セントをお釣りとして返す場合，ペニー2枚，ニッケル1枚，ダイム1枚，クォーター2枚の合計6枚が最適解であることが確認できます．