Zenn
広島大学コンピューティングラボ
🕸️

QUBO＋＋入門：分割問題を解く

Koji Nakano
2024/12/23に公開
C++
数理最適化
量子アニーリング
qubo
tech

分割問題

分割問題とは，整数のリストが与えられたとき，それを合計がなるべく等しくなるように2つの集合に分割する問題です．例えば，次のリストが与えられたとします．

w = [ 15, 10, 24, 1, 14, 12, 8, 6];

この場合の最適解は，次のように2つのリストLと\overline{L}に分割することで，それぞれのリストの合計が35となり等しくなります．

\begin{align*} L &= [24, 1, 14, 6] \\ \overline{L} &= [15, 10, 12, 8] \end{align*}

一般に，整数のリストw_0, w_1, \ldots, w_{n-1}が与えられたとき，Lに含まれる整数のインデックスの集合をlとすると，リストの合計の差は次のように表されます．

| \sum_{i\in l}w_i-\sum_{i\not\in l}w_i |

すなわち，Lの合計の2倍から全整数の合計を引いた値の絶対値を最小化することが，分割問題です．

分割問題をQUBO問題として表す

n個の変数x=[x_0, x_1, \ldots, x_{n-1}]を用いて，リストLに含まれる整数を表します．具体的には，x_i=0のとき，w_i\in Lつまりi\in lとします．このとき，分割問題は次の式で表されます．

(2\sum_{i=0}^{n-1}(1-x_i)-\sum_{i=0}^{n-1}w_i)^2

この式の値を最小化するxへの0/1の割当てを求めることで，分割問題の最適解が得られます．さらに，この式を展開し整理すると，xの2次式となるため，QUBO問題として取り扱うことができます．QUBO++を利用して，この2次式を生成し，最適解を求めることができます．

以下はQUBO++を用いた具体的なプログラムの例です．

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

int main() {
  std::vector<int> w = {15, 10, 24, 1, 14, 12, 8, 6};

  auto x = qbpp::var("x", w.size());
  auto f = qbpp::expr();
  for (size_t i = 0; i < w.size(); i++) {
    f += w[i] * (1 - x[i]) - w[i] * x[i];
  }
  f *= f;
  f.simplify_as_binary();
  std::cout << "f = " << f << std::endl;

  qbpp::exhaustive_solver::ExhaustiveSolver solver(f);
  auto sol = solver.search();
  std::cout << sol << std::endl;
}

このプログラムでは，std::vectorを用いて整数のリストwを生成しています．まず，2値変数の配列xをqbpp::var()関数で生成します．配列の大きさはw.size()で指定します．

次に，空の式fをqbpp::expr()で生成し，forループ内でQUBO問題の式を構築します．複合代入演算を使用して式を更新し，simplify_as_binary()メンバ関数を用いて整理します．この整理された式をコンソールに出力します．

最後に，式fを引数としてExhaustive Solverのオブジェクトを作成し，search()メンバ関数を呼び出して最適解をsolに格納します．この最適解もコンソールに出力されます．

このプログラムをコンパイルして実行すると，次のような出力が得られます．

f = 8100 -4500*x[0] -3200*x[1] -6336*x[2] -356*x[3] -4256*x[4] -3744*x[5] -2624*x[6] -2016*x[7] +1200*x[0]*x[1] +2880*x[0]*x[2] +120*x[0]*x[3] +1680*x[0]*x[4] +1440*x[0]*x[5] +960*x[0]*x[6] +720*x[0]*x[7] +1920*x[1]*x[2] +80*x[1]*x[3] +1120*x[1]*x[4] +960*x[1]*x[5] +640*x[1]*x[6] +480*x[1]*x[7] +192*x[2]*x[3] +2688*x[2]*x[4] +2304*x[2]*x[5] +1536*x[2]*x[6] +1152*x[2]*x[7] +112*x[3]*x[4] +96*x[3]*x[5] +64*x[3]*x[6] +48*x[3]*x[7] +1344*x[4]*x[5] +896*x[4]*x[6] +672*x[4]*x[7] +768*x[5]*x[6] +576*x[5]*x[7] +384*x[6]*x[7]
0:{{x[0],1},{x[1],1},{x[2],0},{x[3],0},{x[4],0},{x[5],1},{x[6],1},{x[7],0}}

この結果から，変数x[0], x[1], x[5], x[6]が1となり，分割問題の最適解が正しく得られていることがわかります．

ベクトルを用いたQUBO++の記述

QUBO++はベクトルを扱うことができ，それを利用することでforループを用いることなく，簡潔に記述できます．以下はその具体例です．

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

int main() {
  qbpp::Vector<int> w = {15, 10, 24, 1, 14, 12, 8, 6};

  auto x = qbpp::var("x", w.size());
  auto f = qbpp::sqr(qbpp::sum(w * (1 - x)) - qbpp::sum(w * x));
  f.simplify_as_binary();
  std::cout << "f = " << f << std::endl;

  qbpp::exhaustive_solver::ExhaustiveSolver solver(f);
  auto sol = solver.search();
  std::cout << sol << std::endl;
}

このプログラムでは，QUBO++でベクトルを扱うためにqbpp::Vectorを用いて整数リストwを生成しています．qbpp::Vectorはstd::vectorを内部的に使用したQUBO++のクラスであり，std::vectorとの互換性があります．

分割問題のQUBO式fを作成する際には，次のような関数を利用しています：

  • qbpp::sqr：与えられた式の2乗を計算します．
  • qbpp::sum：ベクトルの合計を計算します．
  • w * x：2つのベクトルの要素ごとの積を計算します．
    これにより，forループを使うことなく，分割問題の2次式を簡潔に記述することができます．

まとめ

  • 分割問題のQUBO表現：分割問題は，次の式でQUBO問題として表すことができます．
(2\sum_{i=0}^{n-1}(1-x_i)-\sum_{i=0}^{n-1}w_i)^2
  • 変数ベクトル（配列）の生成：変数のベクトルは，第2引数に大きさを指定して生成します．
  auto x = qbpp::var("x", w.size());
  • 式の生成：空の式は関数qbpp::expr()を用いて生成します．
  auto f = qbpp::expr();
  • 式の更新（複合代入演算の利用）：次のように，複合代入演算を用いて式を更新できます．
  f += w[i] * (1 - x[i]) - w[i] * x[i];
  f *= f;
  • ベクトル（配列）の扱い：QUBO++では，ベクトルを扱う際に，std::vectorと互換性のあるqbpp::Vectorクラスを使用します．
  qbpp::Vector<int> w = {15, 10, 24, 1, 14, 12, 8, 6};
  • 変数ベクトルの型指定：前述した変数のベクトルxもqbpp::Vectorクラスです．autoを使わず，明示的に型を指定して次のように記述することも可能です．
  qbpp::Vector<qbpp::Var> x = qbpp::var("x", w.size());
  • 2つのベクトルのアダマール積：2つのベクトルのアダマール積（要素ごとの積）は，演算子*を用いて計算できます．演算結果はqbpp::Vector<qbpp::Expr>，つまりqbpp::Exprの配列となります．
  w * x
  • ベクトルの和の計算：ベクトルの和は，qbpp::sum()関数を使用して計算できます．計算結果はqbpp::Exprになります．
  qbpp::sum(w * (1 - x))
  qbpp::sum(w * x)
  • 式の二乗の計算：式の二乗は，qbpp::sqr()関数を使用して計算できます．
  qbpp::sqr(qbpp::sum(w * (1 - x)) - qbpp::sum(w * x));

QUBO++情報

広島大学コンピューティングラボ
広島大学コンピューティングラボ

広島大学のコンピューティング関連分野で研究を行う研究者が情報を発信します． 主に，量子化学計算や数理最適化に関する技術や研究成果についての記事を掲載しています．

設定によりコメント欄が無効化されています