Evaluating the Performance of Direct Higher-Order Formulations in Combinatorial Optimization Problems

技術要約：組合せ最適化問題における直接的な高次形式（Direct Higher-Order Formulations）の性能評価

問題提起
組合せ最適化問題は、物流、材料設計、ポートフォリオ最適化などの分野で頻繁に遭遇するものである。これらの問題の多くはNP困難であり、ヒューリスティックなアプローチを必要とするが、多くの既存のハードウェアプラットフォーム（量子アニーリング・ハードウェアや物理学に着想を得たソルバーを含む「イジングマシン」）への実装において、大きな障壁が存在する。ほとんどの既存ハードウェアは、二次形式（線形および二次のバイナリ変数の項）に限定された二次無制約バイナリ最適化（QUBO）形式でのみ入力を受け付けるためである。

しかし、ポリマーサンプリング、タンパク質折り畳み、特定のルーティング・タスクなど、多くの実世界の課題は、本質的に高次の相互作用（3次、4次など）を含んでいる。これらを標準的なハードウェアで解決するために、研究者は多項式無制約バイナリ最適化（PUBO）問題をQUBO形式へと変換する「次数低減（order-reduction）」技術を適用しなければならない。このプロセスでは、論理的一貫性を維持するために補助変数とペナルティ項が導入される。著者らは、この変換が必然的に問題のサイズと構造的複雑さを増大させ、結果として解の質と安定性を低下させる可能性があると考えているが、高次の項を直接扱うことと、それらを低減することとの具体的な影響については、実用的な大規模インスタンスを用いて統一されたプラットフォーム上で詳細に定量化されていない。

手法
このギャップに対処するため、本研究では**Fixstars Amplify Annealing Engine (Amplify AE)**を用いた比較評価フレームワークを採用している。この高性能ソルバーは、アニーリング法（SA）と大規模なGPU並列化に基づいており、以下の2つの異なるモードを提供する：

1. PUBOソルバー: 修正を加えることなく、最大4次の項を含む目的関数を直接最適化する。
2. QUBOソルバー: 置換法（substitution method）を用いて次数を低減した後、同一の問題を解決する。この手法では、バイナリ変数の積を新しい補助変数に置き換え、ペナルティ項（具体的には $x_1x_2 = y_{1,2}$）によって制約を強制する。

本研究では、高次の項を自然に含む2つのベンチマーク問題を用いて、これら2つのアプローチを比較する：

• 低自己相関バイナリ列 (LABS): 自己相関エネルギーを最小化するバイナリ列を探索する問題。エネルギー関数は自己相関の二乗項を含み、その結果、4次の相互作用（$s_i s_{i+k} s_j s_{j+k}$）が生じる。
• 距離バランスを伴う車両配送問題 (VRP): 総移動距離を最小化すると同時に、車両間の距離の分散を最小化する多目的問題。分散項を展開すると、4次の相互作用が導入される。

実験は、固定された計算時間（60秒）を用いて、様々な問題サイズに対して実施された。LABSについては、配列長（$N$）を5から99まで変化させた。VRPについては、顧客地点数（$P$）および車両数（$V$）を変化させた。QUBOソルバーは、置換法のために固定されたペナルティ係数（$p=1$）を利用したが、PUBOソルバーはこのようなパラメータ調整を必要としなかった。

主な貢献と結果
本論文は、直接的なPUBO定式化と低減されたQUBO定式化の間のトレードオフに関する定量的な分析を提供している：

1. 解の質と安定性:

   • LABS: PUBOソルバーは、QUBOソルバーと比較して、正規化されたエネルギー値が常に低く（最適解に近い）、標準偏差も有意に小さかった。性能の差は、配列長 $N$ が増加するにつれて拡大した。
   • VRP: 単一インスタンス分析において、PUBOソルバーは総移動距離と距離分散の間のより安定したトレードオフを実現した。散布図の結果、QUBOの解は広く分散しており、真の最小分散領域に到達できていないことが示されたのに対し、PUBOの解はパレートフロント付近に集中していた。
   • ハイパーボリューム分析: ランダムに生成された30個のVRPインスタンス全体を通じて、PUBOソルバーはQUBOソルバーよりも一貫して大きなハイパーボリューム指標（解集合の多様性と質の尺度）を達成し、多目的最適化における優位性を確認した。

2. 変数の膨張:

   • 本研究では、次数低減によって引き起こされる「変数の爆発」を定量化した。LABSとVRPの両方において、QUBO定式化におけるバイナリ変数の数は問題のサイズとともに急速に増加し、大規模なインスタンスでは直接的なPU型定式化の変数の数の数十倍に達した。この膨張は探索空間を拡大させ、観察された解の安定性の低下に寄与している。

3. ペナルティ係数への感度:

   • 著者らは、置換法で使用されるペナルティ係数（$p$）に対するQUBOアプローチの感度を調査した。LABS問題に対するヒートマップ分析により、最適なペナルティ係数は問題サイズ（$N$）によって大きく変化することが示された。単一の $p$ の値がすべてのスケールにおいて一貫したパフォーマンスを提供することはないという事実は、一般的な適用に向けて低減された定式化をチューニングすることの難しさを示している。

意義と主張
本論文は、現代のイジング型ハードウェア上で組合せ最適化問題を解く際、PUBO定式化を通じて高次の項を直接扱うことは、従来の次数低減手法と比較して明確な利点を提供すると主張している。主な意義は、以下の実証にある：

• 構造的完全性: 元の問題の構造を保持する（PUBO）ことで、補助変数による探索空間の人工的な拡大を回避できる。
• 堅牢性: 直接的な定式化は、問題のスケールに敏感であり、探索プロセスを不安定にさせる可能性のあるペナルティ係数のチューニングを不要にする。
• スケーラビリティ: PUBOアプローチは、問題のサイズが増加しても優れた解の質と安定性を維持するが、QUBOアプローチは変数の膨張と制約強制の累積的な影響を受ける。

著者らは、次数低減は様々な問題に対して有効であったものの、直接的なPUBO定式化は、構造的な簡潔さと計算上の安定性の両方を提供することで、実用的な大規模最適化シナリオにおける有望なアプローチとなる、と結論付けている。本研究は、将来のハードウェアおよびソルバーの開発において、これらの利点を最大限に活用するために、直接的な高次実行を継続してサポートすべきであることを示唆している。