論文の概要: SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs

• arxiv url: http://arxiv.org/abs/2508.16171v1
• Date: Fri, 22 Aug 2025 07:49:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-25 16:42:36.297334
• Title: SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs
• Title（参考訳）: SPL-LNS:整数線形プログラムのためのサンプリング強化大近傍探索
• Authors: Shengyu Feng, Zhiqing Sun, Yiming Yang,
• Abstract要約: 大規模近傍探索(Large Neighborhood Search, LNS)は、最適化において、現在のソリューションの大きな近傍を反復的に探索し、より良い解を求めることが一般的である。 本稿では,局所的最適解を逃れるために局所的インフォームド提案を利用するサンプリング型ニューラルネットワーク型LSS解法であるSPL-LNSを紹介する。
• 参考スコア（独自算出の注目度）: 59.91461374628034
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large Neighborhood Search (LNS) is a common heuristic in combinatorial optimization that iteratively searches over a large neighborhood of the current solution for a better one. Recently, neural network-based LNS solvers have achieved great success in solving Integer Linear Programs (ILPs) by learning to greedily predict the locally optimal solution for the next neighborhood proposal. However, this greedy approach raises two key concerns: (1) to what extent this greedy proposal suffers from local optima, and (2) how can we effectively improve its sample efficiency in the long run. To address these questions, this paper first formulates LNS as a stochastic process, and then introduces SPL-LNS, a sampling-enhanced neural LNS solver that leverages locally-informed proposals to escape local optima. We also develop a novel hindsight relabeling method to efficiently train SPL-LNS on self-generated data. Experimental results demonstrate that SPL-LNS substantially surpasses prior neural LNS solvers for various ILP problems of different sizes.
• Abstract（参考訳）: 大規模近傍探索(Large Neighborhood Search, LNS)は、組合せ最適化において一般的なヒューリスティックであり、現在の解の大きな近傍を反復的に探索し、より良い解を求める。 近年,ニューラルネットワークをベースとしたLNS解法は,次の近所の提案に対して,局所最適解を強引に予測することを学ぶことで,整数線形プログラム(ILP)の解法において大きな成功を収めている。 しかし、この欲求的アプローチは、(1)この欲求的提案がどの程度局所的な最適性に苦しむか、(2)長期的にはサンプル効率を効果的に改善できるかという2つの主要な懸念を提起する。 これらの問題に対処するために、まずLNSを確率過程として定式化し、次に局所的最適解を逃れるために局所的インフォームド提案を利用するサンプリング強化型ニューラルネットワーク型LNS解法であるSPL-LNSを紹介する。 また、自己生成データに基づいてSPL-LNSを効率よく学習するための、新しい後光レバーベリング手法を開発した。 実験により、SPL-LNSは、異なる大きさの様々なILP問題に対して、以前のLNSソルバをかなり上回っていることが示された。

関連論文リスト

• PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming [36.13745722329505]
  本稿では,大規模線形計画問題の解法として PDHG-Net と呼ばれる FOM-Unrolled Neural Network (NN) を提案する。 提案手法は,大規模LP問題に対するFOMと比較して,最大3ドル以上の高速化を実現することができることを示す。
  論文  参考訳（メタデータ） (2024-06-04T02:39:42Z)
• Learning-Enhanced Neighborhood Selection for the Vehicle Routing Problem with Time Windows [0.0]
  機械学習(ML)をLarge Neighborhood Search(LNS)に統合し、LNSの各イテレーションにおいて、ソリューションのどの部分が破壊され、修復されるべきかを決定する。 我々のアプローチは普遍的に適用可能であり、すなわち、破壊アルゴリズムの動作を増幅するために任意のLSSアルゴリズムに適用することができる。
  論文  参考訳（メタデータ） (2024-03-13T12:08:27Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  本稿では,UnRolled Federated Learning (SURF)を導入する。 提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
  論文  参考訳（メタデータ） (2023-05-24T17:26:22Z)
• Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning [39.40838358438744]
  線形プログラム(ILP)は、多数の最適化問題のモデリングと解決のための強力なツールである。 アルゴリズムとしてLarge Neighborhood Search (LNS)は、ブランチやバウンドよりも高速に、ILPの高品質なソリューションを見つけることができる。 本稿では,メトリクスによって測定された複数のILPベンチマークに対して,最先端のリアルタイム性能を実現する新しいアプローチCL-LNSを提案する。
  論文  参考訳（メタデータ） (2023-02-03T07:15:37Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。 我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
  論文  参考訳（メタデータ） (2023-01-24T12:01:45Z)
• Local Branching Relaxation Heuristics for Integer Linear Programs [39.40838358438744]
  LNS(Large Neighborhood Search)は最適化問題の解法として一般的なアルゴリズムである。 本稿では,整数プログラム(ILP)におけるLNSの効率的かつ効率的な線形性の設計に焦点をあてる。 提案した緩和 LB-RELAX とその変種は,LB の線形計画法を用いて近傍を選択する。
  論文  参考訳（メタデータ） (2022-12-15T22:53:09Z)
• Learning from Images: Proactive Caching with Parallel Convolutional Neural Networks [94.85780721466816]
  本稿では,プロアクティブキャッシングのための新しいフレームワークを提案する。 モデルベースの最適化とデータ駆動技術を組み合わせて、最適化問題をグレースケールのイメージに変換する。 数値計算の結果,提案手法は71.6%の計算時間を0.8%のコストで削減できることがわかった。
  論文  参考訳（メタデータ） (2021-08-15T21:32:47Z)
• Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
  ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。 その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
  論文  参考訳（メタデータ） (2021-04-09T14:50:59Z)
• Resource Allocation via Model-Free Deep Learning in Free Space Optical Communications [119.81868223344173]
  本稿では,自由空間光学(FSO)通信におけるチャネルフェージング効果の緩和のための資源配分の一般的な問題について検討する。 本フレームワークでは,FSO資源割り当て問題を解決する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-27T17:38:51Z)

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

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