ペナルティ項

制約違反に与える罰。係数 $P$ の設定が QUBO 化の成否を決める。

$$f_{\text{QUBO}}(x)=f_{\text{目的}}(x)+P\cdot g_{\text{違反}}(x)$$

綱引き#

$P$	起きること
小さすぎ	制約を破った方が得になる。実行不可能解が返る
大きすぎ	目的関数の差が相対的に潰れ、実行可能解の中での優劣が見えなくなる

後者が特に厄介。制約は満たすが質の悪い解ばかり返る、という形で現れる。

決め方#

理屈の上での下限は、制約を 1 つ破って得られる最大の利得より 大きく取ればよい。

$$P>\underset{x}{\max }(f_{\text{目的}}(x)-f_{\text{目的}}(x^{\prime }))$$

実務では目的関数の係数の最大値やレンジから見積もり、 実行可能解が返るまで段階的に上げる。

数値精度という制約#

量子アニーラやイジングマシンは、 結合係数を有限の精度でしか表現できない。 $P$ を大きくすると目的関数側の係数が相対的に小さくなり、 量子化の分解能に埋もれてしまう。

つまり「$P$ を十分大きく取れば安全」は成り立たない。 ハードウェアのダイナミックレンジが実質的な上限を課す。 これは QUBO 定式化がうまくいかない主要な原因のひとつ。

診断#

結果がおかしいとき、次の順で確かめる。

1. 返った解は制約を満たしているか → 満たさないなら $P$ が小さい
2. 満たすが質が悪いか → $P$ が大きすぎる可能性
3. 係数の最大値と最小値の比は？ → ダイナミックレンジ超過の疑い

参考文献#

• Fred Glover, Gary Kochenberger, Yu Du. A Tutorial on Formulating and Using QUBO Models. 2019. https://arxiv.org/abs/1811.11538
• Andrew Lucas. Ising formulations of many NP problems. Frontiers in Physics 2, 2014. https://doi.org/10.3389/fphy.2014.00005