制約なし二次二値最適化

概要

QUBOは、値が0か1の二値変数からなる二次形式を目的関数とし、明示的な制約条件を持たない最適化問題の形式である。Glover、Kochenberger、Duによるチュートリアル論文は、この形式が多様な組合せ最適化問題を統一的に表現できると述べている。問題ごとに異なる定式化を用いる代わりに、単一の標準形へ変換しておくことで、同じソルバーや同じハードウェアを使い回せる点が利点である。

技術的な要点

「制約なし」という名称は、制約が扱えないという意味ではない。等式・不等式の制約は、違反したときに目的関数値が悪化するペナルティ項として二次式に組み込む。同論文は、この扱いが近似ではなく厳密な表現になる点を強調している。ペナルティ係数の設定が実用上の要点で、小さすぎると制約違反の解が最適とみなされ、大きすぎると係数の桁差が広がって探索が難しくなる。不等式制約はスラック変数を二値変数で展開して等式に直すため、変数の個数が増える。整数変数を二値変数の重み付き和で表現する場合も同様である。QUBOはイジングモデルと変数変換で相互に移せるため、イジング形式を入力とするハードウェアにもそのまま適用できる。

産業での位置づけ

同論文は、QUBOが量子アニーリングやニューロモルフィックハードウェアを用いた実験の中心的な形式になっていると述べている。実務では、生産計画、配送計画、シフト作成といった問題を業務要件から数理モデルへ落とし込み、QUBOへ変換し、古典ソルバーと専用ハードウェアの双方で解いて比較する流れが取られる。モデリング支援ツールや変換ライブラリは、この定式化工程を担う層にあたる。