分割問題の3通りの定式化

PyQBPP では、同じ問題を従来の 2 乗ペナルティ（sqr）、 非線形関数（abs）、ネイティブ制約（cons()）の いずれでも定式化できます。このケーススタディでは 分割問題を題材に 3 通りの定式化を並べて書き、 エネルギーの意味・モデルの大きさ・得られる情報の違いを比較します。 非線形関数とネイティブ制約そのものの説明は 非線形関数とネイティブ制約を参照してください。

分割問題は、$n$ 個の正の数 $w_0, w_1, \ldots, w_{n-1}$ を 2 つの集合に分割し、両集合の和 $P$ と $Q$ ができるだけ近くなるように する問題です（詳細は分割問題）。 バイナリ変数 $x_i$ を用いると、2 つの和は

\[P = \sum_{i=0}^{n-1} w_i x_i, \qquad Q = \sum_{i=0}^{n-1} w_i \overline{x_i}\]

と書けます。ここで $\overline{x_i}$ は $x_i$ の否定リテラルです。 以下の 3 つのプログラムは、式 p・q の構築までは共通で、 目的関数 f を作る 1 行だけが異なります。

定式化 1: 2 乗ペナルティ sqr

差の 2 乗 $(P - Q)^2$ を最小化する、従来の QUBO 定式化です:

import pyqbpp as qbpp

w = qbpp.array([64, 27, 47, 74, 12, 83, 63, 40])
x = qbpp.var("x", shape=len(w))
p = qbpp.sum(w * x)
q = qbpp.sum(w * ~x)
f = qbpp.sqr(p - q)
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(f"(P - Q)^2 = {sol.energy}")
print(f"P = {sol(p)}, Q = {sol(q)}")

プログラムの出力は以下の通りです:

(P - Q)^2 = 0
P = 205, Q = 205

simplify_as_binary() により、f は 2 乗が展開された 2 次の QUBO 多項式になります（展開後の式は 分割問題のページに示されています）。 展開後は通常の 2 次式なので、QUBO++ のすべてのソルバーはもちろん、 ネイティブ制約に対応しない外部の QUBO ツールでもそのまま扱える、 最も汎用的な形です。一方、エネルギーは差の 2 乗であり、 差そのものを知るには p・q を評価する必要があります。

定式化 2: 絶対値 abs

非線形関数 qbpp.abs を使うと、分割問題の目的関数 $|P - Q|$ をそのまま書けます:

import pyqbpp as qbpp

w = qbpp.array([64, 27, 47, 74, 12, 83, 63, 40])
x = qbpp.var("x", shape=len(w))
p = qbpp.sum(w * x)
q = qbpp.sum(w * ~x)
f = qbpp.abs(p - q)
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(f"|P - Q| = {sol.energy}")
print(f"P = {sol(p)}, Q = {sol(q)}")

プログラムの出力は以下の通りです:

|P - Q| = 0
P = 205, Q = 205

エネルギーが差 $|P - Q|$ そのものになり、解の質を 直接読み取れます。2 乗の展開は起きず、線形式 $P - Q$ は 展開されないまま関数の本体として扱われます。 abs を含む式は、QUBO++ にバンドルされているソルバーが 関数値を直接扱って探索します（対応ソルバーの一覧は 非線形関数とネイティブ制約を参照）。

定式化 3: ネイティブ制約 cons

「$P - Q = 0$（等分割）」を制約として宣言する書き方です。 目的関数はなく、モデルは制約だけからなります:

import pyqbpp as qbpp

w = qbpp.array([64, 27, 47, 74, 12, 83, 63, 40])
x = qbpp.var("x", shape=len(w))
p = qbpp.sum(w * x)
q = qbpp.sum(w * ~x)
f = qbpp.cons(p - q == 0)
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(f"Energy = {sol.energy}")
print(f"P = {sol(p)}, Q = {sol(q)}")
print(f"violated constraints = {f.cons(sol)}")

プログラムの出力は以下の通りです:

Energy = 0
P = 205, Q = 205
violated constraints = 0

cons() で宣言した等式制約の値は違反量の 2 乗 $(P - Q)^2$ なので、 エネルギーの値は定式化 1 と同じです。違いは意味論です — 式は制約として宣言されているため、違反本数を返す f.cons(sol) や 制約ごとの違反量を報告する violations() が使え、 target_energy は「エネルギーが target 以下かつ全制約充足」の ときに探索を停止します。大きなインスタンスを EasySolver で解くときに target_energy に 0 を 指定すると、完全分割が見つかった時点で探索を打ち切れます。

モデルの大きさの比較

3 通りの定式化でソルバーに渡されるモデルの大きさを比べてみます。 sol.info の var_count・term_count が、それぞれモデルの 変数数と目的関数の多項式の項数です:

import pyqbpp as qbpp

w = qbpp.array([64, 27, 47, 74, 12, 83, 63, 40])
x = qbpp.var("x", shape=len(w))
p = qbpp.sum(w * x)
q = qbpp.sum(w * ~x)

f1 = qbpp.sqr(p - q)
f1.simplify_as_binary()
s1 = qbpp.ExhaustiveSolver(f1).search()

f2 = qbpp.abs(p - q)
f2.simplify_as_binary()
s2 = qbpp.ExhaustiveSolver(f2).search()

f3 = qbpp.cons(p - q == 0)
f3.simplify_as_binary()
s3 = qbpp.ExhaustiveSolver(f3).search()

print(f"sqr : var_count = {s1.info['var_count']}, term_count = {s1.info['term_count']}")
print(f"abs : var_count = {s2.info['var_count']}, term_count = {s2.info['term_count']}")
print(f"cons: var_count = {s3.info['var_count']}, term_count = {s3.info['term_count']}")

プログラムの出力は以下の通りです:

sqr : var_count = 8, term_count = 36
abs : var_count = 8, term_count = 0
cons: var_count = 8, term_count = 0

sqr では 2 乗の展開により、8 個の 1 次項と $\binom{8}{2} = 28$ 個の 2 次項、計 36 項の QUBO 多項式になります。 abs・cons では展開は起きません — 目的関数の多項式は空 （term_count = 0）で、8 項の線形式 $P - Q$ が関数・制約の 本体としてそのまま保持されます。

一般に $n$ 個の数では、sqr の項数は $n(n + 1)/2$ に増えます — $n = 1000$ なら約 50 万項です。abs・cons の本体は $n$ 項の 線形式のままなので、モデルの構築も解 1 つの評価も軽く、 インスタンスが大きいほど差が広がります。

完全分割が存在しない場合

3 通りのエネルギーの意味の違いは、完全分割 （$P = Q$ となる分割）が存在しないインスタンスで はっきり現れます。次のプログラムは、最良の分割でも差が 5 になる 8 個の数で 3 通りの定式化を解きます:

import pyqbpp as qbpp

w = qbpp.array([17, 18, 39, 61, 84, 85, 88, 89])
x = qbpp.var("x", shape=len(w))
p = qbpp.sum(w * x)
q = qbpp.sum(w * ~x)

f1 = qbpp.sqr(p - q)
f1.simplify_as_binary()
print(f"sqr : {qbpp.ExhaustiveSolver(f1).search().energy}")

f2 = qbpp.abs(p - q)
f2.simplify_as_binary()
print(f"abs : {qbpp.ExhaustiveSolver(f2).search().energy}")

f3 = qbpp.cons(p - q == 0)
f3.simplify_as_binary()
sol = qbpp.ExhaustiveSolver(f3).search()
print(f"cons: {sol.energy}, violated constraints = {f3.cons(sol)}")
print(f"P = {sol(p)}, Q = {sol(q)}")

プログラムの出力は以下の通りです:

sqr : 25
abs : 5
cons: 25, violated constraints = 1
P = 243, Q = 238

最適な分割は $P = 243$、$Q = 238$ で、差は 5 です。 sqr と cons のエネルギーは $5^2 = 25$、abs のエネルギーは 5 と、それぞれの定義どおりの値になります。cons では 制約 $P - Q = 0$ を満たす分割が存在しないため違反本数が 1 と 報告されますが、ソルバーはエラーにはならず、違反量が最小の解 （= 最良の分割）を返します。制約が満たせないときは最も制約に 近い解が得られる — これがネイティブ制約のソフトな意味論です。

まとめ

定式化	エネルギー	モデル	特徴
qbpp.sqr(p - q)	$(P - Q)^2$	2 次式に展開（$n(n+1)/2$ 項）	最も汎用的。外部の QUBO ツールでも扱える
qbpp.abs(p - q)	$\lvert P - Q \rvert$	展開なし（$n$ 項の本体）	エネルギーが差そのもの
qbpp.cons(p - q == 0)	$(P - Q)^2$	展開なし（$n$ 項の本体）	制約として宣言。違反の集計・target_energy に参加

どの定式化でも、得られる最適な分割そのものは同じです。 目的の量（差）を直接エネルギーとして読みたいなら abs、 「等分割」という制約を宣言して充足を追跡したいなら cons()、 ネイティブ制約に対応しない外部の QUBO ツールに渡す必要が あるなら sqr が適しています。対応ソルバーの一覧と詳細な 演算規則は非線形関数とネイティブ制約を 参照してください。不等式制約についての同様の比較は、 ナップサック問題を 参照してください。