🕸️

QUBO++入門:多倍長整数(桁数の多い分割問題)

2025/01/27に公開

多倍長整数

QUBO++では,デフォルトでQUBO式の各項の係数は32ビット整数(int32_t),エネルギー値は64ビット整数(int64_t)として定義されています.しかし,扱える整数の範囲を超えるとオーバーフローが発生し,正確な結果が得られなくなります.この問題を回避するため,これらの整数のビット数を変更したり,桁数制限のない多倍長整数を使用することが可能です.その実装にはBoost.Multiprecisionライブラリを利用しています.

QUBO++のソースコードqbpp.hppでは,次の2つの型定義を用いて係数とエネルギー値の型を指定します.

  • COEFF_TYPE: 係数の型(デフォルトはint32_t)
  • ENERGY_TYPE: 定数項およびエネルギー値の型(デフォルトはint64_t)
    これらの型は以下のように変更できます:
  1. C++が標準でサポートしている整数型:int8_t,int16_t,int32_t,int64_t
  2. Boost.Multiprecisionがサポートする128ビットから1024ビットまでの整数型: qbpp::int128_t,qbpp::int256_t,qbpp::int512_t,qbpp::int1024_t
  3. Boost.Multiprecisionがサポートする桁数制限のない整数型:qbpp::cpp_int

例えば,係数とエネルギー値の型をqbpp::cpp_intに変更する場合,以下の方法があります.

  • コンパイル時に指定する方法:コンパイル時に以下のオプションを追加します.
-DCOEFF_TYPE=cpp_int -DENERGY_TYPE=cpp_int
  • ソースコード内で指定する方法:qbpp.hppをインクルードする前に,以下のようにdefine文を使用します.
#define COEFF_TYPE qbpp::cpp_int
#define ENERGY_TYPE qbpp::cpp_int
#include "qbpp.hpp"

桁数の多い分割問題

多倍長整数の例として,桁数の多い分割問題をQUBO++で解きます.QUBO化の手法は次の記事の方法をそのまま用います.

QUBO++入門:分割問題を解く

以下にソースコードを示します.

#define COEFF_TYPE qbpp::cpp_int
#define ENERGY_TYPE qbpp::cpp_int

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

int main() {
  qbpp::Vector<qbpp::cpp_int> w = {qbpp::cpp_int("58274310984651293847"),
                                   qbpp::cpp_int("48318786913688664554"),
                                   qbpp::cpp_int("90536217483910257649"),
                                   qbpp::cpp_int("32785041960278314958"),
                                   qbpp::cpp_int("57491836204712038956"),
                                   qbpp::cpp_int("21980475632419876532"),
                                   qbpp::cpp_int("86321504789214367501"),
                                   qbpp::cpp_int("30284715609382147658"),
                                   qbpp::cpp_int("74961830529487162034"),
                                   qbpp::cpp_int("61839427501038476925")};
  auto x = qbpp::var("x", w.size());
  auto f = qbpp::sqr(qbpp::sum(w * (1 - x) - 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;

  std::cout << "sum0 = " << eval(qbpp::sum(w * (1 - x)), sol) << std::endl;
  std::cout << "sum1 = " << eval(qbpp::sum(w * x), sol) << std::endl;
}

このプログラムは,10進20桁の10個の整数を入力とする分割問題をQUBO式に変換し,Exhaustive Solverで解いています.入力はqbpp::cpp_intを要素とするqbpp::Vector型で定義されています.分割問題を解くためのQUBO式fを生成し,Exhaustive Solverで最適解を求めます.

実行結果の例を以下に示します.

f = 316737252582696178212611867326345033176996 -117602183429440364618692814402181666250596*x[0] -99435301303077441623274651112979457668960*x[1] -171025786681146944733952310529709770357140*x[2] -69505483072063181913799868635140678569792*x[3] -116203030884420883679906239852421183796192*x[4] -47549366954223828422900645345542492174496*x[5] -164519342076315943789248777256753677042452*x[6] -64507586829661856834318898122821098308192*x[7] -146275213918820761221583883655862219486880*x[8] -123915012381623459370874695335021489505300*x[9] +22525952120075140267094745667469337593904*x[0]*x[1] +42207485544251280415706522311383827085624*x[0]*x[2] +15284205846704801577250855868893387707408*x[0]*x[3] +26802377136576189787708219808662936829856*x[0]*x[4] +10247176580753485648177439414350330388832*x[0]*x[5] +40242609717997952685817066244011184530776*x[0]*x[6] +14118567484022868717237077789706406882608*x[0]*x[7] +34946792194032499531109005777233889638384*x[0]*x[8] +28829200234466510607284695922652031843800*x[0]*x[9] +34996801604611470633530907258374989388368*x[1]*x[2] +12673067651480236855437991169123380789856*x[1]*x[3] +22223486262817377972634224414672514924992*x[1]*x[4] +8496559346755376825148685823429158773824*x[1]*x[5] +33367603167832036516441315926547746076432*x[1]*x[6] +11706565762171175571530847957491669716256*x[1]*x[7] +28976517728114653608628500170662962742688*x[1]*x[8] +23904048962297414996102083838187155331600*x[1]*x[9] +23745869513079048043707114408586804909936*x[2]*x[3] +41640747089433238815753428248400679795552*x[2]*x[4] +15920232978052446426769824911591108746144*x[2]*x[5] +62521780249077702870291165845611858121192*x[2]*x[6] +21934908790795151117228295207069935488336*x[2]*x[7] +54294084734477386607913536397686007184528*x[2]*x[8] +44789662858516164537003826470714329994600*x[2]*x[9] +15078978098759457478946175234273068030784*x[3]*x[4] +5765046527326085468736769952762950125248*x[3]*x[5] +22640433252710068479480418700032299039664*x[3]*x[6] +7943085376069514959962502932091088546912*x[3]*x[7] +19661014074628068986251410271224255236576*x[3]*x[8] +16219265803369081977826498733294122753200*x[3]*x[9] +10109583238085982469226714025339953444736*x[4]*x[5] +39702254514286225890891312035996898951648*x[4]*x[6] +13928991274567075008645916627643521320384*x[4]*x[7] +34477546259253266042636803560048737572032*x[4]*x[8] +28442097895062953893369685749804056722400*x[4]*x[9] +15179101860585136602783519642103147092256*x[5]*x[6] +5325379627894321348281348101418823696448*x[5]*x[7] +13181573514519847487842122790570863888704*x[5]*x[8] +10874080234474974568834866029518648192800*x[5]*x[9] +20913777788122209369558648618475667701264*x[6]*x[7] +51766544104475214748103533204502485256272*x[6]*x[8] +42704579497545340415130574296226067315400*x[6]*x[9] +18161581753153752630339427260946876930976*x[7]*x[8] +14982315802527644945853731750798206333200*x[7]*x[9] +37084773474986832800343427878848360523600*x[8]*x[9]
0:{{x[0],0},{x[1],1},{x[2],1},{x[3],1},{x[4],1},{x[5],1},{x[6],0},{x[7],1},{x[8],0},{x[9],0}}
sum0 = 281397073804391300307
sum1 = 281397073804391300307

配列xのうち,値が0となるものの合計(sum0)と値が1となるものの合計(sum1)が一致しており,最適解が得られていることがわかります.

ベクトル・スカラー演算

前述のコード中の以下の行では,ベクトル・スカラー演算を行っています.

std::cout << "sum0 = " << eval(qbpp::sum(w * (1 - x)), sol) << std::endl;

ここで,1はスカラー値,xはベクトル変数です.したがって,この1 - xはスカラー値とベクトル変数の減算演算を表しています.QUBO++では,要素ごとに演算を適用します.そのため,演算結果は,ベクトルの各要素が1 - x[i]となる新しいベクトルになります.結果として,qbpp::sum(w * (1 - x))が返すQUBO式は,次のような数式で表されます.

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

まとめ

  • 係数とエネルギー値の型指定COEFF_TYPE(係数の型.デフォルトはint32_t)とENERGY_TYPE(定数項およびエネルギー値の型.デフォルトはint64_t)は,変更可能です.指定できる型は,int8_tint16_tint32_tint64_tqbpp::int128_tqbpp::int256_tqbpp::int512_tqbpp::int1024_t,およびqbpp::cpp_intです.
  • ベクトル・スカラー演算:QUBO++では,ベクトルとスカラーの二項演算を行う場合,各ベクトル要素に対してスカラーとの二項演算を適用し,結果として新しいベクトルを生成します.

QUBO++情報

広島大学コンピューティングラボ
設定によりコメント欄が無効化されています