論文の概要: Learning to Search in Local Branching
- arxiv url: http://arxiv.org/abs/2112.02195v1
- Date: Fri, 3 Dec 2021 23:54:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-07 15:41:03.385963
- Title: Learning to Search in Local Branching
- Title（参考訳）: 地域分枝における探索学習
- Authors: Defeng Liu, Matteo Fischetti and Andrea Lodi
- Abstract要約: 局所分岐(LB)は、混合整数線形プログラミング問題に対する改善された解を生成するために提案されている。
LBアルゴリズムでは, 近傍サイズの選択は性能上重要である。
本研究では,探索近傍の大きさと基礎となるLBアルゴリズムの挙動との関係について検討する。
- 参考スコア（独自算出の注目度）: 3.3946853660795884
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Finding high-quality solutions to mixed-integer linear programming problems
(MILPs) is of great importance for many practical applications. In this
respect, the refinement heuristic local branching (LB) has been proposed to
produce improving solutions and has been highly influential for the development
of local search methods in MILP. The algorithm iteratively explores a sequence
of solution neighborhoods defined by the so-called local branching constraint,
namely, a linear inequality limiting the distance from a reference solution.
For a LB algorithm, the choice of the neighborhood size is critical to
performance. Although it was initialized by a conservative value in the
original LB scheme, our new observation is that the best size is strongly
dependent on the particular MILP instance. In this work, we investigate the
relation between the size of the search neighborhood and the behavior of the
underlying LB algorithm, and we devise a leaning based framework for guiding
the neighborhood search of the LB heuristic. The framework consists of a
two-phase strategy. For the first phase, a scaled regression model is trained
to predict the size of the LB neighborhood at the first iteration through a
regression task. In the second phase, we leverage reinforcement learning and
devise a reinforced neighborhood search strategy to dynamically adapt the size
at the subsequent iterations. We computationally show that the neighborhood
size can indeed be learned, leading to improved performances and that the
overall algorithm generalizes well both with respect to the instance size and,
remarkably, across instances.
- Abstract（参考訳）: 混合整数線形プログラミング問題(MILP)に対する高品質な解を見つけることは、多くの実用アプリケーションにとって非常に重要である。
この点に関して,改良型局所分岐法(LB)が提案され,MILPにおける局所探索法の発展に大きく影響している。
このアルゴリズムは、いわゆる局所分岐制約によって定義される解近傍の列、すなわち基準解からの距離を制限する線形不等式を反復的に探索する。
LBアルゴリズムでは, 近傍サイズの選択は性能上重要である。
元のLB方式の保守的な値によって初期化されているが、我々の新しい観察では、最良のサイズは特定のMILPインスタンスに強く依存している。
本研究では,探索近傍の大きさと基礎となるLBアルゴリズムの挙動の関係を考察し,LBヒューリスティックの近傍探索を導くための傾き型フレームワークを提案する。
この枠組みは二段階戦略から成り立っている。
第1フェーズでは、回帰タスクを通じて第1イテレーションにおけるLB近傍のサイズを予測するために、スケールされた回帰モデルを訓練する。
第2フェーズでは、強化学習を活用して、強化された近隣探索戦略を考案し、次のイテレーションでサイズを動的に適応させる。
計算によって、近隣の規模が実際に学習できることが示され、性能が向上し、全体的なアルゴリズムがインスタンスサイズとインスタンス全体の両方に関してうまく一般化される。
関連論文リスト
- Offline RL via Feature-Occupancy Gradient Ascent [9.983014605039658]
大規模無限水平割引マルコフ決定過程(MDP)におけるオフライン強化学習の研究
我々は,特徴占有空間における勾配上昇の形式を実行する新しいアルゴリズムを開発した。
結果として得られた単純なアルゴリズムは、強い計算とサンプルの複雑さの保証を満たすことを示す。
論文 参考訳（メタデータ） (2024-05-22T15:39:05Z) - PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback [106.63518036538163]
我々は、強化学習におけるポリシーアライメントの最近強調された重要な問題に対処するために、新しい統合された二段階最適化ベースのフレームワーク、textsfPARLを提案する。
本フレームワークは, 上向きの目標(逆設計)の分布を, 下向きの最適変数で明示的にパラメータ化することにより, これらの問題に対処する。
その結果,提案したtextsfPARL が RL のアライメントの懸念に対処できる可能性が示唆された。
論文 参考訳（メタデータ） (2023-08-03T18:03:44Z) - Non-stationary Reinforcement Learning under General Function
Approximation [60.430936031067006]
まず,非定常MDPに対する動的ベルマンエルダー次元(DBE)と呼ばれる新しい複雑性指標を提案する。
提案する複雑性指標に基づいて,SW-OPEAと呼ばれる新しい信頼度セットに基づくモデルフリーアルゴリズムを提案する。
SW-OPEAは,変動予算がそれほど大きくない限り,有効に有効であることを示す。
論文 参考訳（メタデータ） (2023-06-01T16:19:37Z) - New Characterizations and Efficient Local Search for General Integer
Linear Programming [17.80124240223163]
本研究では境界解の概念を用いた線形プログラミング(ILP)の新たな特徴付けを提案する。
そこで我々は,局所探索アルゴリズムのLocal-ILPを開発した。
MIPLIBデータセットで行った実験は、大規模ハードILP問題の解法におけるアルゴリズムの有効性を示した。
論文 参考訳（メタデータ） (2023-04-29T07:22:07Z) - DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean
Optimization [10.513103815142731]
PBO(Pseudo-Boolean Optimization)の解法における局所探索アルゴリズムの改良法について検討する。
我々のアルゴリズムであるDeciLS-PBOは最先端のアルゴリズムと比較して有望な性能を持つ。
論文 参考訳（メタデータ） (2023-01-28T17:03:56Z) - Local Branching Relaxation Heuristics for Integer Linear Programs [39.40838358438744]
LNS(Large Neighborhood Search)は最適化問題の解法として一般的なアルゴリズムである。
本稿では,整数プログラム(ILP)におけるLNSの効率的かつ効率的な線形性の設計に焦点をあてる。
提案した緩和 LB-RELAX とその変種は,LB の線形計画法を用いて近傍を選択する。
論文 参考訳（メタデータ） (2022-12-15T22:53:09Z) - GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP,
and Beyond [101.5329678997916]
対話型意思決定の一般的な枠組みの下で, サンプル高能率強化学習(RL)について検討した。
本稿では,探索とエクスプロイトの基本的なトレードオフを特徴付ける,新しい複雑性尺度である一般化エルダー係数(GEC)を提案する。
低 GEC の RL 問題は非常にリッチなクラスであり、これは低ベルマン楕円体次元問題、双線型クラス、低証人ランク問題、PO-双線型クラス、一般化正規PSR を仮定する。
論文 参考訳（メタデータ） (2022-11-03T16:42:40Z) - A General Framework for Sample-Efficient Function Approximation in
Reinforcement Learning [132.45959478064736]
モデルベースとモデルフリー強化学習を統合した汎用フレームワークを提案する。
最適化に基づく探索のための分解可能な構造特性を持つ新しい推定関数を提案する。
本フレームワークでは,OPERA (Optimization-based Exploration with Approximation) という新しいサンプル効率アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-30T17:59:16Z) - 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 the Step-size Policy for the Limited-Memory
Broyden-Fletcher-Goldfarb-Shanno Algorithm [3.7470451129384825]
本稿では,L-BFGSアルゴリズムのステップサイズポリシの学習方法について考察する。
入力として電流勾配の局所的な情報を用いたニューラルネットワークアーキテクチャを提案する。
ステップ長ポリシは、同様の最適化問題のデータから学習され、目的関数のさらなる評価を回避し、出力ステップが予め定義された間隔内に留まることを保証します。
論文 参考訳（メタデータ） (2020-10-03T09:34:03Z) - FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity
to Non-IID Data [59.50904660420082]
フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。
クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
論文 参考訳（メタデータ） (2020-05-22T23:07:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。