Residual-Guided Simulated Annealing for Multi-Dimensional Subset Sum

技術要約：多次元部分集合和問題のための残差誘導型焼きなまし法（RGSA）

問題定義
本論文は、多次元部分集合和問題（別名：マーケット・スプリット問題）を扱う。形式的には、属性ベクトル $A \in \mathbb{Z}_{\ge 0}^{m \times N}$ とターゲットベクトル $b \in \mathbb{Z}_{\ge 0}^m$ が与えられたとき、$Ax = b$ を満たすバイナリベクトル $x \in \{0, 1\}^N$ を見つけることを目的とする。この問題は $m=1$ の場合でもNP完全である。評価対象となったインスタンスは、**量子最適化ベンチマーク・ライブラリ（QOBLIB）**のものであり、これらは汎用整数計画法の弱点を露呈させるために設計された「意図的に小さく、かつ困難な」システムを特徴としている。これらのインスタンスは、高密度の正の係数と、局所的には妥当であってもグローバルには矛盾を生じさせる等式ターゲットによって特徴付けられる。本研究は、選択されるアイテム数が $q \approx N/2$ である固定容量のスライスに焦点を当てている。

手法：残差誘導型焼きなまし法（RGSA）
核心となる貢献は、容量保存型の局所探索ヒューリスティックである**残差誘導型焼きなまし法（RGSA）**である。盲目的なランダムスワップに依存することが多い標準的な焼きなまし法（SA）とは異なり、RGSAは現在の残差ベクトル $\Delta = Ax - b$ を組み込んで探索を誘導する。

1. 幾何学的スワップ提案： 現在の集合 $S$ からアイテム $i$ が取り除かれる際、本手法は「理想的な補償者（ideal compensator）」ベクトル $w^* = w_i - \Delta$ を計算する。その後、未選択のアイテム集合 $\bar{S}$ の中から、$m$ 次元の属性空間において $w^*$ に幾何学的に最も近いベクトル $w_j$ を探索する。
2. ハイブリッド近傍： アルゴリズムは、この誘導された提案を確率 $p_g$（実験では0.65に設定）で用い、確率 $1-p_g$ で一様ランダムスワップと混合する。これにより、理想的な補償者が観測された点群の外にある場合でも、解空間の探索が保証される。
3. 受理規則： 本手法は、二乗ではなく、ユークリッド残差ノルム $R(x) = \|Ax - b\|_2$ に基づくメトロポリス受理基準を使用し、温度の大きさを解釈可能な状態に保つ。
4. 補助コンポーネント：
   • ラグランジュ・ウォームスタート： 焼きなましを開始する前に、ラグランジュ双対投影を用いて実行可能な容量分割を生成するオプションの初期化ステップ。
   • 決定論的ポリッシング： 調査された近傍内で局所最適解に到達するための、網羅的な1対1および2対2の交換を含む後処理フェーズ。
   • フルパイプライン： ラグランジュ・ウォームスタート、RGSA、および決定論的ポリッシングの組み合わせを「フルRGSAパイプライン」と呼ぶ。

実験設定
本研究では、次元 $m \in \{9, \dots, 15\}$ および係数範囲 $D \in \{50, 200\}$ を持つ8つのQOBLIBマーケット・スプリット・インスタンスに対してRGSAを評価している。評価は以下の3段階で行われる：

1. 制御されたベンチマーク： 160回の実行（8インスタンス $\times$ 4構成 $\times$ 5シード）を行い、RGSAの各バリアントを「ブラインドSA」のベースラインと比較する。
2. 25秒予算： 厳格な25秒のウォールクロック制限の下、8つの手法（RGSAバリアント、ブラインドSA、およびSCIP、CP-SAT、pymoo GA、QUBOサンプラーを含む6つの外部ソルバー）を用いた1,554回の実行を含む比較。
3. 300秒予算： 収束性と可用性を分析するための、中間チェックポイント（25秒、60秒、120秒、300秒）を含む長時間の実験。

主な結果

• 残差の減少： RGSAは、ブラインドSAと比較して一貫してユークリッド残差を低下させている。主要なインスタンス $(m=15, D=200)$ において、フルRGSAパイプラインは平均残差 100.37 を達成した。これはRGSA単体での 104.06 よりも低く、ブラインドSAによる値はこれよりも大幅に高かった。
• 外部ソルバーとの比較：
  • 厳密ソルバー： 厳密ソルバー（SCIP、CP-SAT）および線形計画法サロゲート（HiGHS）は、これら特定のインスタンスにおいて、25秒および300秒の予算内で実行可能なベクトルを一つも返せず、25秒のウィンドウにおける有効なインカンベント（現行解）の可用性は0%であった。
  • ヒューリスティック： 300秒時点において、フルRGSAパイプラインは最小の中央値残差 36.54 を達成した。これは、安定したエニータイム・トラジェトリを提供するChampion構成（フルポリッシングなしの誘導型SA）の 38.00 や、ブラインドSAの 42.25 を上回った。Champion構成は安定した推移を示したが、フルパイプラインの方が最終的なエンドポイントの残差はわずかに低かった。
  • QUBOサンプラー： 標準的なQUBO焼きなましサンプラー（Neal）は、中央値残差 263.46 という低い性能を示し、RGSAの特有の残差誘導型幾何学の有用性を浮き彫りにした。
• 実行可能性： テストされたインスタンスにおいて、今回の研究のどの構成も、指定された時間予算内で厳密な実行可能性（$Ax=b$）を達成できなかった。主要なベンチマークにおいて、厳密な解を見つけた実行は0/160であったことが明記されている。

意義と主張
本論文は、RGSAを厳密ソルバーの代替品としてではなく、透明性の高い古典的ベースライン、およびハイブリッド探索のためのインカンベント生成候補として位置付けている。

• 初の制御された研究： 著者の知る限り、これは $m \ge 12$ のQOBLIBマーケット・スプリット・クラスに対する、初の制御されたマルチシード・スケーリング研究である。
• 方法論的貢献： 従来のペナルティベースや単一変数ジャンプ手法とは異なり、残差方程式そのものを用いて最近傍の提案を定義する、特定の容量保存型幾何学的スワップ・ヒューリスティックを導入している。
• 実用的有用性： RGSAは、$m=15$ の境界領域において、厳密ソルバーが現在実用的ではない状況下でも、数秒で低残差かつ実行可能に近い割り当てを生成する。これらの結果は、不可能性を証明するものではなく、厳密またはハイブリッド探索の出発点および「再現可能な古典的ベースライン」としての価値を提供するものである。
• 謙虚な姿勢： 著者は、結果は記述的なものであることを強調している。非ゼロの残差は不可能性を証明するものではなく、本研究は普遍的な優位性を主張するものではない。主な価値は、残差の質、可用性、および実行時間を厳密に報告することにある。