イントロダクション

ソルバーについて

組合せ最適化問題を解くためのソルバーには様々な種類があります。本資料で紹介するソルバーは以下の通りです。

観点	量子アニーリング	シミュレーテッドアニーリング	Gurobi
対象とする形式	QUBO(イジング)	QUBO含むコスト関数全般	MIPなど様々な形式
解の性質	近似解	近似解	厳密解
スケール	今後に期待	大規模に強い	制約構造次第で強力
得意領域	局所障壁の突破	ヒューリスティック探索	厳密最適化・制約問題

量子アニーリングでは、どんな問題でも 「QUBO（キューボ）」 と呼ばれる以下の数式形式に変換する必要があります。

H = \sum_{i,j} Q_{ij} x_i x_j

難しい式に見えますが、要するに 「二値変数 $x$ 同士の掛け算（二次式）と足し算だけで書いてね」 というルールです。（※ $x$ は 0 か 1 の値しか取れません）

例えば、「必ず1つ選ぶ」という制約を表すには $(x_1 + x_2 + x_3 - 1)^2$ という式を使いますが、これをマシンに渡すには $x_1^2 + x_2^2 + \dots + 2x_1x_2 \dots$ のように展開する必要があります。

QUBO形式に定式化をすることさえできれば、上記のソルバーに問題を投げ込み解を得ることができるようになります。

元々の問題からQUBOへ変換するために、制約項を引っ張りだし、スラック変数で不等式制約を書いて、整数変数はバイナリ表現に変換し……ということを手でやることは(理解には重要ですが)大変な作業です。そんな種々の作業をサポートしてくれるライブラリを紹介します。