🕸️
QUBO＋＋入門：行列操作（順列生成）

Koji Nakano
2025/02/10に公開
 変数の行列C++では，ネストしたstd::vector，具体的にはstd::vector<std::vector<int>>を使用して行列を表現することが一般的です．QUBO++も同様に，ネストしたqbpp::Vectorを用いて変数や式の行列を扱うことができます．
QUBO++では，このような行列に対して，和（sum）や積（product）を計算するための関数が用意されています．

qbpp::total_sum(): 全要素の和を返します．

qbpp::sum(): 低次元（行）のベクトルをその和で置き換えたベクトルを返します．

qbpp::total_product(): 全要素の積を返します．

qbpp::product(): 低次元（行）のベクトルをその積で置き換えたベクトルを返します．

qbpp::transpose(): 行列を転置（行と列の入れ替え）します．
以下は，2 \times 3の行列xにおけるインデックスのを表しています．

\left(
\begin{array}{ccc}
x[0][0] & x[0][1] & x[0][2] \\
x[1][0] & x[1][1] & x[1][2] 
\end{array}
\right)
この行列を使って，上述の関数の動作を説明します．
#include "qbpp.hpp"

int main() {
  qbpp::Vector<qbpp::Vector<qbpp::Var>> x = qbpp::var("x", 2, 3);
  qbpp::Expr total_sum = qbpp::total_sum(x).simplify_as_binary();
  qbpp::Vector<qbpp::Expr> sum = qbpp::sum(x).simplify_as_binary();
  std::cout << "total_sum = " << total_sum << std::endl;
  std::cout << str(sum, "sum") << std::endl;

  qbpp::Expr total_product = qbpp::total_product(x).simplify_as_binary();
  qbpp::Vector<qbpp::Expr> product = qbpp::product(x).simplify_as_binary();
  std::cout << "total_product = " << total_product << std::endl;
  std::cout << str(product, "product") << std::endl;

  qbpp::Vector<qbpp::Vector<qbpp::Expr>> t =　qbpp::transpose(x).simplify_as_binary();
  std::cout << str(t, "t") << std::endl;
  qbpp::Vector<qbpp::Expr> sum_t = qbpp::sum(t).simplify_as_binary();
  std::cout << str(sum_t, "sum_t") << std::endl;
}
理解を深めるため，コード中では型を明示して'qbpp::Vector<qbpp::Vectorqbpp::Var>'と記述していますが，autoを使用することで簡略化することも可能です．

変数の生成：

qbpp::varを用いて，大きさ2 \times 3の行列を表す変数xを生成します．引数として行列のサイズを指定します．

全要素の和と行ごとの和の計算：qbpp::total_sumを使って全変数の和を，qbpp::sumを使って行ごとの和を計算し，それぞれを出力します．

全要素の積と行ごとの積の計算：qbpp::total_productを使って全変数の積を，qbpp::productを使って行ごとの積を計算し，それぞれを出力します．

行列の転置：

行列xを転置して新たな行列tを作成します．さらに転置後の行列tに対して行ごとの和を計算し出力します．これにより，元の行列xの列ごとの和が求まります．
以下は，このプログラムを実行した場合の出力です．
total_sum = x[0][0] +x[0][1] +x[0][2] +x[1][0] +x[1][1] +x[1][2]
{sum[0],x[0][0] +x[0][1] +x[0][2]},{sum[1],x[1][0] +x[1][1] +x[1][2]}
total_product = x[0][0]*x[0][1]*x[0][2]*x[1][0]*x[1][1]*x[1][2]
{product[0],x[0][0]*x[0][1]*x[0][2]},{product[1],x[1][0]*x[1][1]*x[1][2]}
{t[0][0],x[0][0]},{t[0][1],x[1][0]},{t[1][0],x[0][1]},{t[1][1],x[1][1]},{t[2][0],x[0][2]},{t[2][1],x[1][2]}
{sum_t[0],x[0][0] +x[1][0]},{sum_t[1],x[0][1] +x[1][1]},{sum_t[2],x[0][2] +x[1][2]}

 one-hotベクトルによる順列表現組合せ最適化問題には，あらゆる順列の中から最適なものを選択するタイプの問題が多く存在します．そのような組合せ最適化問題をQUBO問題として扱うための準備として，QUBO++を用いて順列を生成するQUBO式を記述します．
QUBOでは，整数0, 1, 2, \ldots, n-1の順列を表現するために，n \times nの二値変数の行列を用います．ここで，各行はone-hotベクトルと仮定します．この1が存在する列番号によって，0からn-1までの整数を表現します．さらに，もし各列もone-hotベクトルであるならば，各行で表される整数はすべて異なります．したがって，その整数を並べることで順列となります．
以下の4 \times 4の行列は，各行および各列がone-hotベクトルとなっています．この行列が表す順列は，[2, 0, 3, 1]です．

\left(
\begin{array}{cccc}
0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 \\
\end{array}
\right)
n \times nの二値変数の行列xにおいて，各行および各列がone-hotベクトルとなる条件は，それぞれの行・列の要素の合計が1になることです．この条件は，次のQUBO式で表すことができます．

\sum_{i=0}^{n-1}\left(1-\sum_{j=0}^{n-1}x_{i,j}\right)^2+\sum_{j=0}^{n-1}\left(1-\sum_{i=0}^{n-1}x_{i,j}\right)^2
この式は，QUBO++の等価演算子==を用いて次のように表すことができます．

\sum_{i=0}^{n-1}\left(\sum_{j=0}^{n-1}x_{i,j}==1\right)+\sum_{j=0}^{n-1}\left(\sum_{i=0}^{n-1}x_{i,j}==1\right)

 順列生成QUBO＋＋プログラムn \times nの変数行列xを生成し、各行および各列がone-hotベクトルのとき、エネルギー値が最小となるQUBO式fを作成します。以下は、4 \times 4の行列の場合のコードです。
#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"

int main() {
  auto x = qbpp::var("x", 4, 4);
  auto f = qbpp::sum(qbpp::sum(x) == 1) +
           qbpp::sum(qbpp::sum(qbpp::transpose(x)) == 1);
  f.simplify_as_binary();
  std::cout << "f = " << f << std::endl;

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sol = solver.search();
  auto result = sol.get(x);
  auto onehot = qbpp::onehot_to_int(result);

  std::cout << sol << std::endl;
  std::cout << str(result, "result") << std::endl;
  std::cout << str(onehot, "onehot") << std::endl;
}
式fは1行で生成されています．

qbpp::sum(x)は，行列xの各行をその和で置き換えたベクトルを返します．

qbpp::sum(x) == 1は，そのベクトルの各要素が1である場合に最小値0を取るQUBO式を返します．

qbpp::sum(qbpp::sum(x) == 1)は，そのQUBO式の和を返します．

qbpp::sum(qbpp::sum(qbpp::transpose(x)) == 1)は，行列xの転置行列に対して同じ処理を行います．

以上により，式fは各行および各列がone-hotベクトルとなる場合にエネルギーが最小値0を取るQUBO式となります．
Exhaustive Solverを用いて最適解solを求めます．そして，メンバ関数get()を使用して，solからxの値を取得し，それをresultとします．xが行列であるため，resultも同様に行列形式になります．さらに，関数qbpp::onehot_to_int()を用いて，resultの各行をone-hotベクトルから整数に変換し，onehotとして格納します．最後に，std::coutを用いてsol，result，およびonehotを出力します．
このプログラムを実行すると，下の出力が得られます．
f = 8 -2*x[0][0] -2*x[0][1] -2*x[0][2] -2*x[0][3] -2*x[1][0] -2*x[1][1] -2*x[1][2] -2*x[1][3] -2*x[2][0] -2*x[2][1] -2*x[2][2] -2*x[2][3] -2*x[3][0] -2*x[3][1] -2*x[3][2] -2*x[3][3] +2*x[0][0]*x[0][1] +2*x[0][0]*x[0][2] +2*x[0][0]*x[0][3] +2*x[0][0]*x[1][0] +2*x[0][0]*x[2][0] +2*x[0][0]*x[3][0] +2*x[0][1]*x[0][2] +2*x[0][1]*x[0][3] +2*x[0][1]*x[1][1] +2*x[0][1]*x[2][1] +2*x[0][1]*x[3][1] +2*x[0][2]*x[0][3] +2*x[0][2]*x[1][2] +2*x[0][2]*x[2][2] +2*x[0][2]*x[3][2] +2*x[0][3]*x[1][3] +2*x[0][3]*x[2][3] +2*x[0][3]*x[3][3] +2*x[1][0]*x[1][1] +2*x[1][0]*x[1][2] +2*x[1][0]*x[1][3] +2*x[1][0]*x[2][0] +2*x[1][0]*x[3][0] +2*x[1][1]*x[1][2] +2*x[1][1]*x[1][3] +2*x[1][1]*x[2][1] +2*x[1][1]*x[3][1] +2*x[1][2]*x[1][3] +2*x[1][2]*x[2][2] +2*x[1][2]*x[3][2] +2*x[1][3]*x[2][3] +2*x[1][3]*x[3][3] +2*x[2][0]*x[2][1] +2*x[2][0]*x[2][2] +2*x[2][0]*x[2][3] +2*x[2][0]*x[3][0] +2*x[2][1]*x[2][2] +2*x[2][1]*x[2][3] +2*x[2][1]*x[3][1] +2*x[2][2]*x[2][3] +2*x[2][2]*x[3][2] +2*x[2][3]*x[3][3] +2*x[3][0]*x[3][1] +2*x[3][0]*x[3][2] +2*x[3][0]*x[3][3] +2*x[3][1]*x[3][2] +2*x[3][1]*x[3][3] +2*x[3][2]*x[3][3]
0:{{x[0][0],0},{x[0][1],0},{x[0][2],1},{x[0][3],0},{x[1][0],0},{x[1][1],1},{x[1][2],0},{x[1][3],0},{x[2][0],0},{x[2][1],0},{x[2][2],0},{x[2][3],1},{x[3][0],1},{x[3][1],0},{x[3][2],0},{x[3][3],0}}
{onehot[0][0],0},{onehot[0][1],0},{onehot[0][2],1},{onehot[0][3],0},{onehot[1][0],0},{onehot[1][1],1},{onehot[1][2],0},{onehot[1][3],0},{onehot[2][0],0},{onehot[2][1],0},{onehot[2][2],0},{onehot[2][3],1},{onehot[3][0],1},{onehot[3][1],0},{onehot[3][2],0},{onehot[3][3],0}
{perm[0],2},{perm[1],1},{perm[2],3},{perm[3],0}
この出力では，順列[2, 1, 3, 0]が得られています．

 全ての順列を求めるExhaustive Solverは，メンバ関数search_optimal_solutions()を使用することで，全ての最適解を列挙することができます．以下は，この機能を利用して全ての順列を表示するQUBO++プログラムです．
#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"

int main() {
  auto x = qbpp::var("x", 4, 4);
  auto f = qbpp::sum(qbpp::sum(x) == 1) +
           qbpp::sum(qbpp::sum(qbpp::transpose(x)) == 1);
  f.simplify_as_binary();
  std::cout << "f = " << f << std::endl;

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sol = solver.search();
  auto onehot = sol.get(x);
  auto perm = qbpp::onehot_to_int(onehot);

  std::cout << sol << std::endl;
  std::cout << str(onehot, "onehot") << std::endl;
  std::cout << str(perm, "perm") << std::endl;
}
search_optimal_solutions()を使用して，全ての最適解をoptimal_solsに保存します．それをforループで取り出し，表示しています．
プログラムを実行すると，次のような出力が得られ，全24通りの順列が表示されます．
0:{perm[0],3},{perm[1],2},{perm[2],1},{perm[3],0}
1:{perm[0],3},{perm[1],2},{perm[2],0},{perm[3],1}
2:{perm[0],3},{perm[1],1},{perm[2],2},{perm[3],0}
3:{perm[0],3},{perm[1],1},{perm[2],0},{perm[3],2}
4:{perm[0],3},{perm[1],0},{perm[2],2},{perm[3],1}
5:{perm[0],3},{perm[1],0},{perm[2],1},{perm[3],2}
6:{perm[0],2},{perm[1],3},{perm[2],1},{perm[3],0}
7:{perm[0],2},{perm[1],3},{perm[2],0},{perm[3],1}
8:{perm[0],2},{perm[1],1},{perm[2],3},{perm[3],0}
9:{perm[0],2},{perm[1],1},{perm[2],0},{perm[3],3}
10:{perm[0],2},{perm[1],0},{perm[2],3},{perm[3],1}
11:{perm[0],2},{perm[1],0},{perm[2],1},{perm[3],3}
12:{perm[0],1},{perm[1],3},{perm[2],2},{perm[3],0}
13:{perm[0],1},{perm[1],3},{perm[2],0},{perm[3],2}
14:{perm[0],1},{perm[1],2},{perm[2],3},{perm[3],0}
15:{perm[0],1},{perm[1],2},{perm[2],0},{perm[3],3}
16:{perm[0],1},{perm[1],0},{perm[2],3},{perm[3],2}
17:{perm[0],1},{perm[1],0},{perm[2],2},{perm[3],3}
18:{perm[0],0},{perm[1],3},{perm[2],2},{perm[3],1}
19:{perm[0],0},{perm[1],3},{perm[2],1},{perm[3],2}
20:{perm[0],0},{perm[1],2},{perm[2],3},{perm[3],1}
21:{perm[0],0},{perm[1],2},{perm[2],1},{perm[3],3}
22:{perm[0],0},{perm[1],1},{perm[2],3},{perm[3],2}
23:{perm[0],0},{perm[1],1},{perm[2],2},{perm[3],3}

 まとめ
順列の表現方法：n \times n の二値行列を用いることで0, 1, \ldots, n-1 の順列を表現できます．

順列を求めるQUBO式：n \times n の二値変数行列において，各行および各列が one-hot ベクトルとなるように制約を設定することで，最適解が順列を表すQUBO 式を構築できます．

 QUBO++情報
QUBO＋＋ツールとABS2 QUBO Solverの詳細情報：QUBO++に関する公式サイトです．ツールの特徴や使用方法，ABS2 QUBO Solverとの連携について詳しく説明されています．

【研究成果】組合せ最適化問題を解くためのプログラミング用ツールQUBO＋＋を無償公開します：広島大学からの公式リリース情報です．QUBO++の開発背景や研究成果について記載されています．

利用条件：QUBO++は非商用利用や評価研究目的に限り無償で利用可能です．商用利用や定常的な業務での使用を希望する場合は，ライセンス契約が必要となります．
広島大学コンピューティングラボPublication
広島大学のコンピューティング関連分野で研究を行う研究者が情報を発信します．主に，量子化学計算や数理最適化に関する技術や研究成果についての記事を掲載しています．
変数の行列

one-hotベクトルによる順列表現

順列生成QUBO＋＋プログラム

全ての順列を求める

まとめ

QUBO++情報

Discussion
