論文の概要: Local Branching Relaxation Heuristics for Integer Linear Programs

• arxiv url: http://arxiv.org/abs/2212.08183v2
• Date: Wed, 31 May 2023 18:16:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-03 01:03:39.322008
• Title: Local Branching Relaxation Heuristics for Integer Linear Programs
• Title（参考訳）: 整数線形プログラムのための局所分岐緩和ヒューリスティックス
• Authors: Taoan Huang, Aaron Ferber, Yuandong Tian, Bistra Dilkina, Benoit Steiner
• Abstract要約: LNS(Large Neighborhood Search)は最適化問題の解法として一般的なアルゴリズムである。 本稿では,整数プログラム(ILP)におけるLNSの効率的かつ効率的な線形性の設計に焦点をあてる。 提案した緩和 LB-RELAX とその変種は,LB の線形計画法を用いて近傍を選択する。
• 参考スコア（独自算出の注目度）: 39.40838358438744
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Large Neighborhood Search (LNS) is a popular heuristic algorithm for solving combinatorial optimization problems (COP). It starts with an initial solution to the problem and iteratively improves it by searching a large neighborhood around the current best solution. LNS relies on heuristics to select neighborhoods to search in. In this paper, we focus on designing effective and efficient heuristics in LNS for integer linear programs (ILP) since a wide range of COPs can be represented as ILPs. Local Branching (LB) is a heuristic that selects the neighborhood that leads to the largest improvement over the current solution in each iteration of LNS. LB is often slow since it needs to solve an ILP of the same size as input. Our proposed heuristics, LB-RELAX and its variants, use the linear programming relaxation of LB to select neighborhoods. Empirically, LB-RELAX and its variants compute as effective neighborhoods as LB but run faster. They achieve state-of-the-art anytime performance on several ILP benchmarks.
• Abstract（参考訳）: large neighborhood search (lns) は組合せ最適化問題を解くための一般的なヒューリスティックアルゴリズムである。 問題に対する最初のソリューションから始まり、現在の最良のソリューションの周りに大きな近所を探すことで反復的に改善します。 LNSは、検索する地区を選択するためにヒューリスティックに頼っている。 本稿では,多種多様な cop を ilp として表現できるため,整数線形プログラム (ilp) における lns の効率的かつ効率的なヒューリスティックの設計に着目する。 局所分岐(Local Branching、LB)は、LNSの各イテレーションにおいて、現在のソリューションよりも最大の改善をもたらす近傍を選択するヒューリスティックである。 LBは入力と同じ大きさのILPを解く必要があるため、しばしば遅い。 提案するヒューリスティックス LB-RELAX とその変種は,LB の線形プログラミング緩和を利用して地区を選択する。 実証的には、LB-RELAXとその変種はLBと同じくらいに効率的な近傍を計算するが、より速く走る。 彼らはいくつかのILPベンチマークで常に最先端のパフォーマンスを達成する。

関連論文リスト

• 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)
• Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search [30.364955687049292]
  MAPFはLarge Neborhood Search(LNS)に基づいている 探索を併用したBandit-based Adaptive LArge Neighborhood Search(BALANCE)を提案する。 大規模シナリオでは、最先端のMAPFと比較して、少なくとも50%のコスト改善が実証的に実証されている。
  論文  参考訳（メタデータ） (2023-12-28T01:24:42Z)
• 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)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Learning to Search in Local Branching [3.3946853660795884]
  局所分岐(LB)は、混合整数線形プログラミング問題に対する改善された解を生成するために提案されている。 LBアルゴリズムでは, 近傍サイズの選択は性能上重要である。 本研究では,探索近傍の大きさと基礎となるLBアルゴリズムの挙動との関係について検討する。
  論文  参考訳（メタデータ） (2021-12-03T23:54:29Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• A General Large Neighborhood Search Framework for Solving Integer Linear Programs [46.62993477453986]
  我々は整数プログラムの解法に重点を置いており、我々のアプローチは大規模近傍探索(SLN)パラダイムに根ざしている。 我々のLSSフレームワークは、Gurobiのような最先端の商用解法と比較して、大幅に性能が向上することを示した。
  論文  参考訳（メタデータ） (2020-03-29T23:08:14Z)

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

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