Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size

技術要約：柔軟に調整可能なサブ問題サイズを備えたイジングマシン支援型ラージ・ネイバーフッド探索

問題提起
イジングマシンは、イジングモデルまたは二次無制約バイナリ最適化（QUBO）モデルの低エネルギー状態を探索することにより、組合せ最適化問題に対するヒューリスティックなソルバーとして機能します。しかし、大規模な制約付き問題に対してこれらを直接適用すること（「ナイーブな手法」）は、主に以下の2つの困難に直面します。

1. スケーラビリティ： QUBO定式化におけるバイナリ変数の数が、現在のイジングマシンのハードウェア容量を超えてしまうことがよくあります。
2. 実行可能（フィジビリティ）： 制約は通常、ペナルティ項として組み込まれます。その結果、探索空間には実行不可能な解が含まれることになり、低エネルギー状態が必ずしも元の問題の高品質な実行可能解になるとは限りません。

変数固定や分割統治法のような既存のアプローチは、問題サイズの縮小を試みていますが、サブ問題のサイズと、元の問題に対する実行可能解を再構成する能力とのバランスを取ることに苦慮することがよくあります。ラージ・ネイバーフッド探索（LNS）は、実行可能な現在の解を、サブ問題（「ネイバーフッド」）を再最適化することで反復的に改善するフレームワークを提供します。LNSは、サブ問題生成方法が適切に設計されていれば実行可能性を維持しますが、イジングマシン支援型LNSの性能は、サブ問題のサイズに対して非常に敏感です。サブ問題が小さすぎると、1回の反復あたりの改善の可能性が制限され、大きすぎると、探索空間の拡大によりイジングマシンの解の質が低下します。

手法
本論文では、車両配送問題（VRP）と二次多重ナップサック問題（QMKP）の2つの問題に焦点を当てています。

• 既存の手法 (LNS-V): VRPに関して、著者らは以前の手法（LNS-V）を分析しています。これは、車両のサブセットを選択し、それらのルート全体を再最適化するものです。これは実行可能性を維持しますが、サブ問題のサイズは選択された車両の数（$V'$）のみによって制御されます。選択された車両の全ルートを再最適化するため、変数の数は $(V')^2(T-2)^2$ （$T$ は総ステップ数）となります。これは粒度が粗いことを意味し、$V'$ を1つ変えるだけで変数カウントが劇的に跳ね上がるため、サブ問題のサイズをイジングマシンに適した範囲に微調整することが困難になります。

• 提案手法 (LNS-VT): 粒度の問題を解決するために、著者らはLNS-VTを提案しています。LNS-VTでは、$V'$ 個の車両を選択することに加え、新たにパラメータとして、各選択された車両に対して再最適化する連続ステップ数（$T'$）を導入しています。

  • メカニズム: 各車両について、ルートの連続するセグメント（長さ $T_{seg} = \min(T', \text{実際の有効なステップ数})$）を抽出します。サブ問題は、残りのルートを固定したまま、これらの特定のセグメント内での地点の割り当てと順序を再最適化します。
  • 実行可能性: 抽出された区間の外側にある地点を固定し、抽出されたセグメントがデポ（拠点）以外の地点のみを扱うようにすることで、抽出されたセグメントの実行可能な解を元のVRPに再挿入することが、元の問題の実行可能な解となることが保証されます。
  • 変数制御: LNS-VTにおける自由変数の数は、近似的に $(V'T')^2$ です。これにより、総ステップ数 $T$ とは独立して、サブ問題のサイズをきめ細かく制御することが可能になります。

• QMKPへの拡張: 著者らは、同じ設計原理をQMKPに適用しています。彼らは、再最適化する対象として、ナップサックのサブセット（$K'$）とアイテムのサブセット（$N'$）を選択するサブ問題生成方法を構築しています。この手法は、選択されたセットに含まれないアイテムを固定し、選択されたナップサックの残余容量に対して容量制約を調整することで、実行可能性を維持します。

主な結果
数値実験は、Fixstars Amplify AE イジングマシンを用いて、300地点・5車両のVRP、および200アイテム・5ナップサックのQMKPに対して行われました。

• VRPの性能:

  • LNS-VTは、ナイーブな手法および既存のLNS-Vの両方を上回りました。
  • 最良のLNS-VTの設定（具体的には $V'=2, T'=40$）は、100回の反復後、LNS-Vと比較して目的関数値を約**10%**減少させました。
  • LNS-VTは、LNS-Vの最終的な解の品質に、わずか約**30%**の反復回数で到達しました。
  • 変数の感度: 非デポ地点の割り当て変数の最適なサブ問題サイズは、6,000から10,000の間であることが判明しました。既存のLNS-Vは、$V' \ge 2$ の場合、この範囲（最小でも約14,400変数）に到達できなかったため、劣った性能を示す原因となりました。
  • 動的な必要性: 適切なサブ問題サイズは、探索プロセス中に変化しました。初期の反復（目的関数値が大きい段階）ではより大きなサブ問題が効果的であり、後半の反復（高品質な解の精緻化段階）ではより小さなサブ問題が効果的でした。

• QMKPの性能:

  • QMKPに適用されたLNSも、ナイーブな手法を上回りました。
  • QMKPにおける最適なサブ問題サイズは、著しく小さく、約100から150個の変数であることが判明しました。
  • このVRP（6,000–10,000）との極端な差は、最適なサブ問題サイズが、単にイジングマシンの能力だけでなく、特定のクラスやQUBO定式化に依存していることを示しています。

意義と主張
本論文は、イジングマシン支援型LNSが大規模な制約付き問題に対して効果的であるためには、実行可能性の維持だけでは不十分であると主張しています。イジングマシンの性能のスイートスポットに一致するように、サブ問題のサイズを柔軟に調整できることが、極めて重要な設計因子です。

研究は以下のことを実証しています：

1. 追加の制御パラメータ（VRPにおける連続ステップ数、またはQMKPにおけるアイテム数/ナップサック数）を導入することで、選択されたエンティティの数のみを変化させる手法では不可能な、サブ問題サイズのきめ細かな調整が可能になります。
2. 解の品質を最大化する変数の最適な範囲が存在し、その範囲は異なる問題クラス間（VRP vs QMKP）で大きく異なります。
3. 最適なサブ問題サイズは、現在の解の品質にも依存する可能性があり、これは静的なパラメータ設定が探索プロセス全体を通じて最適ではない可能性を示唆しています。

著者らは、結果がテストされたインスタンスやマシン設定に特有のものであることを認めつつも、構造を考慮した、柔軟に調整可能なサブ問題生成の原理は、制約付き組合せ最適化における有望な方向性であると結論付けています。今後の課題として、探索段階や問題の構造に基づいてサブ問題のパラメータを自動的に選択する適応戦略の開発に注力すべきであると述べています。