論文の概要: Regularized Large Neighborhood Search

• arxiv url: http://arxiv.org/abs/2606.02294v1
• Date: Mon, 01 Jun 2026 14:16:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:32.207894
• Title: Regularized Large Neighborhood Search
• Title（参考訳）: 正規化大規模近傍探索
• Authors: Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier, Mathieu Blondel,
• Abstract要約: 大規模地域探索(LNS)を用いたNP難問の運用研究実践者 正規化LSS(RLNS)によりこのギャップを埋める。 アンダートロピック正規化では、RLNSが正確なブロックギブスサンプリングを行う。
• 参考スコア（独自算出の注目度）: 11.54620327711825
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Operations research practitioners typically tackle NP-hard combinatorial problems using large neighborhood search (LNS), a scalable heuristic that iteratively refines a current solution by locally re-optimizing subsets of its variables. In contrast, most existing approaches for integrating combinatorial optimization layers into neural networks still assume access to an exact global solution, which is computationally intractable. We bridge this gap by introducing regularized LNS (RLNS). By regularizing or perturbing local subproblems, we turn the LNS heuristic into an efficient MCMC sampler over the combinatorial set of feasible solutions, with associated Fenchel-Young losses. Under entropic regularization, we prove that RLNS performs exact block Gibbs sampling. Furthermore, adjusting the number of RLNS iterations allows us to interpolate between pseudolikelihood and exact maximum likelihood estimation, for end-to-end learning without global solvers. We demonstrate our approach on $k$-subset selection, generalized assignment, and stochastic vehicle scheduling problems.
• Abstract（参考訳）: オペレーションリサーチ実践者は一般に、局所的に変数のサブセットを最適化することによって現在の解を反復的に洗練するスケーラブルなヒューリスティックである大近傍探索(LNS)を用いてNPハード組合せ問題に取り組む。 対照的に、組合せ最適化層をニューラルネットワークに統合する既存のアプローチは、計算的に難解な正確なグローバルソリューションへのアクセスを前提としている。 正規化LSS(RLNS)を導入することで、このギャップを埋める。 局所的なサブプロブレムを正規化または摂動することにより、LNSヒューリスティックを、Fenchel-Young の損失を伴う実現可能な解の組合せ上の効率的なMCMCサンプリングに変換する。 エントロピー正規化の下では、RLNSが正確なブロックギブスサンプリングを行うことを示す。 さらに,RLNS反復数を調整することにより,大域的解法を伴わないエンドツーエンド学習において,擬似的類似度と最大推定値との補間が可能となる。 提案手法は,$k$-subset selection, Generalized assignment, and stochastic vehicle schedule problemである。

関連論文リスト

• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
  State-of-the-art Large Language Model (LLM) プルーニング手法は階層的に動作し、階層ごとのプルーニングエラーを最小限に抑え、完全な再トレーニングを回避する。 既存の手法は、刈り上げ対象の重量相互作用を無視する欲求凸に依存する。 提案手法は, 層ごとのプルーニング誤差を大幅に低減し, 最先端のGPTアーキテクチャにおいて高いベースラインを達成し, メモリ効率を保っている。
  論文  参考訳（メタデータ） (2025-10-15T16:13:44Z)
• SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs [59.91461374628034]
  大規模近傍探索(Large Neighborhood Search, LNS)は、最適化において、現在のソリューションの大きな近傍を反復的に探索し、より良い解を求めることが一般的である。 本稿では,局所的最適解を逃れるために局所的インフォームド提案を利用するサンプリング型ニューラルネットワーク型LSS解法であるSPL-LNSを紹介する。
  論文  参考訳（メタデータ） (2025-08-22T07:49:33Z)
• Learning with Local Search MCMC Layers [12.613397606663801]
  不正確な解法による学習に理論的に根ざしたアプローチを導入する。 局所探索で使用される問題固有近傍系を提案分布に変換する。 時間窓を用いた大規模動的車両ルーティング問題に対する我々のアプローチを実証する。
  論文  参考訳（メタデータ） (2025-05-20T11:47:42Z)
• A Random-Key Optimizer for Combinatorial Optimization [0.0]
  本稿では,最適化問題に適した汎用的で効率的な局所探索手法を提案する。 ランダムキーの概念を用いて、RKOは解をランダムキーのベクトルとしてエンコードし、後に実行可能な解に復号する。 RKOフレームワークは古典的メタヒューリスティクスの多元体を組み合わせ、それぞれが独立して、あるいは並列に動作可能であり、エリートソリューションプールを通じてソリューション共有が促進される。
  論文  参考訳（メタデータ） (2024-11-06T22:23:29Z)
• Ant Colony Sampling with GFlowNets for Combinatorial Optimization [68.84985459701007]
  Generative Flow Ant Colony Sampler (GFACS)は、階層的に償却推論と並列探索を組み合わせた新しいメタヒューリスティック手法である。 提案手法はまず,生成フローネットワーク(GFlowNets)を利用して,解空間上のエンフルティモーダル事前分布を補正する。 この前者は、Ant Colony Optimization (ACO) の精神で並列探索によって更新され、後部分布がほぼ最適解を生成する。
  論文  参考訳（メタデータ） (2024-03-11T16:26:06Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。 L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
  論文  参考訳（メタデータ） (2022-06-06T09:25:40Z)
• Improved Training of Physics-Informed Neural Networks with Model Ensembles [81.38804205212425]
  我々は、PINNを正しい解に収束させるため、解区間を徐々に拡大することを提案する。 すべてのアンサンブルのメンバーは、観測されたデータの近くで同じ解に収束する。 提案手法は, 得られた解の精度を向上させることができることを示す。
  論文  参考訳（メタデータ） (2022-04-11T14:05:34Z)
• Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming [0.0]
  離散データからベイズネットワーク(BNSL)の構造を学習することはNPハードタスクであることが知られている。 本研究では,可能なクラスタカットのサブセットを発見するための新しい時間アルゴリズムを提案する。 最適ではないにもかかわらず、性能は桁違いに向上することを示す。 結果として得られる解法は、BNSL問題に対する最先端の解法である GOBNILP と好意的に比較できる。
  論文  参考訳（メタデータ） (2021-06-23T09:46:11Z)
• DeepSplit: Scalable Verification of Deep Neural Networks via Operator Splitting [70.62923754433461]
  入力摂動に対するディープニューラルネットワークの最悪の性能を分析することは、大規模な非最適化問題の解決につながる。 解析解を持つ小さなサブプロブレムに分割することで,問題の凸緩和を直接高精度に解ける新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-06-16T20:43:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。