Large Neighborhood Search と反復的ニューラル制約ヒューリスティクスの融合
arXiv cs.LG / 2026/3/24
💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisModels & Research
要点
- 本論文は、反復的なニューラル制約充足ヒューリスティクスを Large Neighborhood Search（LNS）に結び付け、標準的な LNS の destroy／repair オペレータを用いてニューラル手法を組み直す（再定式化する）。
- ConsFormer を LNS 手順として適応し、モデル内部のスコアを活用して近傍（ネイバーフッド）を選択する、古典的な destroy オペレータと予測ガイド付き destroy オペレータの両方を追加する。
- repair では、ニューラル repair オペレータとして ConsFormer を使用し、割り当て（assignment）生成におけるサンプリングベースのデコードと貪欲デコード（greedy decoding）を比較する。
- Sudoku、Graph Coloring、MaxCut に関する実験により、ニューラル手法の素の設定よりも大幅な改善が示され、古典手法や他のニューラル基線に対してもより強い競争力を持つことが分かる。
- 著者らは反復的な設計パターンを特定している。すなわち、「確率的な destroy は貪欲な destroy より優れる」が、「貪欲な repair は、高品質な実行可能解を素早く 1 つ見つける点でより良い」。
